Undergraduate Math Club Seminar

Suppose you're interested in solving some computational problems, but you are a puny, polynomially bounded computational agent. You live in a magical realism fiction world, so you have two options to expand your power: either you can have a chat with an infinitely wise wizard, (who may or may not be trying to deceive you) or you can employ the use of a time machine. Which of these options is more powerful? They turn out to be the same, even if you have a quantum computer! Formally, we'll discuss the equality QIP = IP = PSPACE = BPP_CTC = BQP_CTC. Each of these equalities is a marvelous theorem in its own right. The first was proven by Jain, Ji, Upadhyay, and Watrous in 2009, the second by Shamir in 1992, and the last two by Aaronson and Watrous also in 2009. The theorems discussed are deep, but this talk is aimed at those without formal exposure to complexity theory. We'll spend lots of time motivating the definitions and working with examples, while only touching on a few ideas from the proofs of the main theorems. Related classes: CS 21, CS 151.