Fetching the paper…
Reading the bibliography…
It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions.
A tight Ω ( log log n ) \Omega(\log\log n) -bound on the time for parallel RAM’s to compute non-degenerate Boolean functions
H. U. Simon · 1983
Earlier work this paper cites.
The polynomial method in circuit complexity
R. Beigel · 1993
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.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1997
Earlier work this paper cites.
Gaussian Hilbert Spaces
S. Janson · 1997
Earlier work this paper cites.
Quantum oracle interrogation: Getting all information for almost half the price
W. van Dam · 1998
Earlier work this paper cites.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001
Cited alongside, same era.
Communication complexity lower bounds by polynomials
H. Buhrman and R. de Wolf · 2001
Cited alongside, same era.
Quantum amplitude amplification and estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Cited alongside, same era.
Complexity measures and decision tree complexity: A survey
H. Buhrman and R. de Wolf · 2002
Cited alongside, same era.
Quantum lower bounds for the collision and the element distinctness problems
S. Aaronson and Y. Shi · 2004
Cited alongside, same era.
Polynomial degree vs. quantum query complexity
A. Ambainis · 2006
Cited alongside, same era.
Quantum and classical strong direct product theorems and optimal time-space tradeoffs
H. Klauck, R. Špalek, and R. de Wolf · 2007
Later among the works it cites.
Lecture notes for a course “Analysis of Boolean functions”, 2007
R. O’Donnell · 2007
Later among the works it cites.
Some topics in analysis of boolean functions
R. O’Donnell · 2008
Later among the works it cites.
Communication lower bounds using dual polynomials
A. Sherstov · 2008
Later among the works it cites.
A brief introduction to Fourier analysis on the Boolean cube
R. de Wolf · 2008
Later among the works it cites.
Quantum proofs for classical theorems
A. Drucker and R. de Wolf · 2011
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
On the Fourier tails of bounded functions over the discrete cube
I. Dinur, E. Friedgut, G. Kindler, and R. O’Donnell · 2007
Cited alongside, same era.
Optimal quantum query bounds for almost all Boolean functions
A. Ambainis, A. Bačkurs, J. Smotrovs, and R. de Wolf · 2013
Closest in time.