The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials


Robin Kothari


Microsoft Research
Redmond, USA


Tuesday, 26 February 2019, 16:00 to 17:00


  • A-201 (STCS Seminar Room)


Abstract: The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. Approximate degree is known to be a lower bound on quantum query complexity. We use approximate degree to prove optimal or nearly optimal lower bounds on the quantum query complexity of several problems, resolving open questions from prior work. The problems studied include k-distinctness, image size testing, k-junta testing, approximating statistical distance, approximating Shannon entropy, and surjectivity. This work was presented at QIP 2018 and STOC 2018, and is available at This is joint work with Mark Bun and Justin Thaler.