Open Collections

Approximate degree and quantum query lower bounds via dual polynomials

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Computer science; Fourier analysis; Theoretical computer science

video/mp4

Author affiliation: Princeton University

2019-03-28

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/69316

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/