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.