Computer Science/Discrete Mathematics Seminar II

I will survey recent results and open problems in several areas of quantum complexity theory, with emphasis on open problems which can be phrased in terms of classical complexity theory or mathematics but have implications for quantum computing: 1. Quantum vs. classical query complexity 2. Quantum vs. classical query complexity for almost all inputs 3. Quantum counterparts of Valiant-Vazirani theorem (reducing NP to unique-NP)