Exploring the Limits of the Efficiently Computable

I'll give a broad overview of my research over the last decade aimed at understanding the relationship between computational complexity and physics—and in particular, the capabilities and limitations of quantum computers. Possible topics, depending on time, will include the BosonSampling model of quantum computing, creating unforgeable 'quantum money' using hidden subspaces, quantum computing versus the polynomial-time hierarchy, maximal separations between classical and quantum query complexity, the need for structure in quantum speedups, and the computational complexity of decoding Hawking radiation.