The Power of Randomized and Quantum Computation
Shalev Ben-David, Massachusetts Institute of Technology
Randomized and quantum computing offer potential improvements over deterministic algorithms, and challenge our notion of what should be considered efficient computation. A fundamental question in complexity theory is to try to understand when these resources help; on which tasks do randomized or quantum algorithms outperform deterministic ones?
In this talk, I will describe some of my work investigating this question, primarily in the query complexity (blackbox) model.