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 postdoctoral researcher in the Theoretical Computer Science and Discrete Mathematics group at the Institute for Advanced Study. He obtained his Ph.D. in 2015 from the Weizmann Institute of Science, under the guidance of Ran Raz. His thesis title was “Analysis of Boolean Functions in Theoretical Computer Science.”

His research interests include complexity theory, analysis of Boolean functions, circuit and formula lower bounds, decision-tree complexity, pseudorandomness, and the relationship between algorithms and complexity.