TITLE: Title: Sparse Polynomial Approximations and their Applications to
Quantum Advantage, Parallel Computation, and Pseudorandomness
This talk is motivated by three seemingly unrelated questions:
1. For which tasks do quantum algorithms outperform classical computation?
2. Can parallel computing accelerate all computational tasks, or are some tasks inherently sequential?
3. Can we de-randomize every algorithm while increasing its space by at most a constant factor?
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 polynomials. As one of the results, we show that relative to an oracle, quantum algorithms can perform decision tasks that are outside the polynomial-time hierarchy (that captures P, NP, coNP and their generalizations). This settles one of the big open questions in the area of quantum complexity.
Looking forward, we conjecture that several other computational devices can be well-approximated by sparse 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 byAvi Wigderson. He obtained his Ph.D. in 2015 from the Weizmann Institute of Science, under the guidance of Ran Raz. His research interests include complexity theory, analysis of Boolean functions, quantum computing, pseudorandomness, and learning theory.