Tata Institute of Fundamental Research
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
STCS Colloquium
Speaker:
Robin Kothari (Microsoft Research
Redmond, USA)
Organiser:
Pranab Sen
Date:
Tuesday, 26 Feb 2019, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. Approximate degree is known to be a lower bound on quantum query complexity. We use approximate degree to prove optimal or nearly optimal lower bounds on the quantum query complexity of several problems, resolving open questions from prior work. The problems studied include k-distinctness, image size testing, k-junta testing, approximating statistical distance, approximating Shannon entropy, and surjectivity. This work was presented at QIP 2018 and STOC 2018, and is available at https://arxiv.org/abs/1710.09079. This is joint work with Mark Bun and Justin Thaler.
| Speaker: | Robin Kothari (Microsoft Research Redmond, USA) |
| Organiser: | Pranab Sen |
| Date: | Tuesday, 26 Feb 2019, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. Approximate degree is known to be a lower bound on quantum query complexity. We use approximate degree to prove optimal or nearly optimal lower bounds on the quantum query complexity of several problems, resolving open questions from prior work. The problems studied include k-distinctness, image size testing, k-junta testing, approximating statistical distance, approximating Shannon entropy, and surjectivity. This work was presented at QIP 2018 and STOC 2018, and is available at https://arxiv.org/abs/1710.09079. This is joint work with Mark Bun and Justin Thaler.