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. 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.