BIRS Workshop Lecture Videos
Approximate degree and quantum query lower bounds via dual polynomials Bun, Mark
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.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International