Sparse Polynomial Approximations and their applications to Quantum Advantage, Parallel Computation, and Pseudorandomness

Avishay Tal - Postdoctoral Research Fellow, Stanford University

Feb. 28, 2019, 10 a.m. - Feb. 28, 2019, 11 a.m.

McConnell 103

---

ABSTRACT:
This talk is motivated by three (seemingly unrelated) questions: 1. For which tasks do quantum algorithms outperform classical computation? 2. Does parallel computing always offer a speed-up, or are some tasks inherently sequential? 3. Do randomized algorithms have deterministic counterparts with similar memory footprint? We make progress on all three questions by exploiting a common phenomenon at the core of their analysis: in all cases, the studied computational devices can be well-approximated by sparse multivariate polynomials. As an application towards the first question above, we show that relative to an oracle, quantum algorithms can efficiently solve tasks that are infeasible for the polynomial hierarchy (that captures P, NP, coNP and their generalizations). This settles an open problem raised by Bernstein and Vazirani in 1993. Looking forward, we conjecture that several other computational devices can be well-approximated by sparse multivariate polynomials. Proving our conjecture would resolve several big open questions in computational complexity that have remained open since the 1980s.
****

Avishay Tal is a Motwani Postdoctoral Research Fellow at Stanford University, hosted by Omer Reingold. Prior to that, he was a postdoctoral researcher at the Institute for Advanced Study, hosted by Avi Wigderson. He obtained his Ph.D. in 2015 from the Weizmann Institute of Science, under the guidance of Ran Raz. His research interests include computational complexity theory, analysis of Boolean functions, quantum computing, pseudorandomness, and learning theory.
ALL ARE WELCOME