The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

QuICS Seminar

Justin Thaler (Georgetown University)
January 26, 2018
PSC 3150

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.