Title: The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Abstract: The eps-approximate degree of a Boolean function is the minimum degree of a real polynomial that point-wise approximates f to error eps. Approximate degree has wide-ranging applications in theoretical computer science. As one example, the approximate degree of a function is a lower bound on its quantum query complexity. Despite its importance, the approximate degree of many basic functions has resisted characterization. In this talk, I will describe recent advances in proving both upper and lower bounds on the approximate degree of specific functions.
These advances yield tight (or nearly tight) bounds for a variety of basic functions. Our approximate degree bounds settle (or nearly settle) the quantum query complexity of many of these functions, including k-distinctness, junta testing, approximating the statistical distance of two distributions, and entropy approximation.
Based on joint work with Mark Bun and Robin Kothari.