BIRS Workshop Lecture Videos

Banff International Research Station Logo

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 Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International