Fetching the paper…
Reading the bibliography…
The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms.
Rapid solution of problems by quantum computation
D. Deutsch and R. Jozsa · 1992
Earlier work this paper cites.
On the degree of Boolean functions as real polynomials
N. Nisan and M. Szegedy · 1994
Earlier work this paper cites.
An O ( n log log n ) {O}(n^{\log\log n}) learning algorithm for DNF under the uniform distribution
Y. Mansour · 1995
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
C. H. Bennett, E. Bernstein, G. Brassard, and U. V. Vazirani · 1997
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. V. Vazirani · 1997
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. Shor · 1997
Earlier work this paper cites.
On the power of quantum computation
D. R. Simon · 1997
Earlier work this paper cites.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001
Earlier work this paper cites.
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Cited alongside, same era.
Exponential algorithmic speedup by a quantum walk
A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman · 2003
Cited alongside, same era.
Learning monotone decision trees in polynomial time
R. O’Donnell and R. A. Servedio · 2007
Cited alongside, same era.
Quantum property testing
H. Buhrman, L. Fortnow, I. Newman, and H. Röhrig · 2008
Cited alongside, same era.
BQP and the polynomial hierarchy
S. Aaronson · 2010
Cited alongside, same era.
Introduction to the non-asymptotic analysis of random matrices
R. Vershynin · 2010
Cited alongside, same era.
An inequality for the fourier spectrum of parity decision trees
E. Blais, L. Tan, and A. Wan · 2015
Later among the works it cites.
Separations in query complexity using cheat sheets
S. Aaronson, S. Ben-David, and R. Kothari · 2016
Later among the works it cites.
Degree and sensitivity: tails of two distributions
P. Gopalan, R. A. Servedio, A. Tal, and A. Wigderson · 2016
Later among the works it cites.
Tight bounds on the fourier spectrum of AC0
A. Tal · 2017
Later among the works it cites.
Pseudorandom generators from polarizing random walks
E. Chattopadhyay, P. Hatami, K. Hosseini, and S. Lovett · 2018
Later among the works it cites.
Improved pseudorandomness for unordered branching programs through local monotonicity
E. Chattopadhyay, P. Hatami, O. Reingold, and A. Tal · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Pseudorandomness for regular branching programs via Fourier analysis
O. Reingold, T. Steinke, and S. Vadhan · 2013
Cited alongside, same era.
Analysis of boolean functions
R. O’Donnell · 2014
Cited alongside, same era.
Forrelation: A problem that optimally separates quantum from classical computing
S. Aaronson and A. Ambainis · 2015
Cited alongside, same era.
Later among the works it cites.
Pseudorandom generators from the second fourier level and applications to AC0 with parity gates
E. Chattopadhyay, P. Hatami, S. Lovett, and A. Tal · 2019
Closest in time.
Oracle separation of BQP and PH
R. Raz and A. Tal · 2019
Closest in time.