log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Justin Thaler - Georgetown University
Friday, January 26, 2018, 11:00 am-12:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
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.

This talk is organized by Javiera Caceres