Fall 2018

Approximate Degree and Quantum Query Lower Bounds via Dual Polynomials

Tuesday, Sep. 11, 2018 12:00 pm12:30 pm PDT

Add to Calendar


Mark Bun (Princeton University)

The epsilon-approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to within error epsilon. Approximate degree has a number of applications throughout theoretical computer science. As one example, a lower bound on the approximate degree of a function automatically implies a lower bound on its quantum query complexity.

I will describe recent progress proving approximate degree lower bounds using the "method of dual polynomials," a framework based on linear programming duality. Our new techniques for constructing dual polynomials yield a nearly tight lower bound on the approximate degree of AC^0, and settle (or nearly settle) the quantum query complexities of several specific functions of interest in quantum computing.

Based on joint works with Robin Kothari and Justin Thaler.