RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

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

January 26, 2018 - 11:00am
Speaker: 
Justin Thaler
Institution: 
Georgetown University

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.

PSC 3150