*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Tess Malone, Communications Officer
Summary Sentence: Sparse Polynomial Approximations and their Applications to Quantum Advantage, Parallel Computation, and Pseudorandomness
Full Summary: No summary paragraph submitted.
Avishay TalTITLE: Title: Sparse Polynomial Approximations and their Applications to
Quantum Advantage, Parallel Computation, and Pseudorandomness
ABSTRACT:
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.
BIO:
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.
