Fetching the paper…
Reading the bibliography…
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$.
Towards optimal separations between quantum and randomized query complexities
Avishay Tal · 1912
Earlier work this paper cites.
Method of determining lower bounds for the complexity of P-schemes
V. M. Khrapchenko · 1971
Earlier work this paper cites.
On recognizing graph properties from adjacency matrices
Ronald L. Rivest and Jean Vuillemin · 1976
Earlier work this paper cites.
Probabilistic computations: Toward a unified measure of complexity
Andrew Chi-Chih Yao · 1977
Earlier work this paper cites.
A topological approach to evasiveness
Jeff Kahn, Michael Saks, and Dean Sturtevant · 1984
Earlier work this paper cites.
Probabilistic Boolean decision trees and the complexity of evaluating game trees
Michael Saks and Avi Wigderson · 1986
Earlier work this paper cites.
Lower bounds on the complexity of graph properties
Valerie King · 1988
Earlier work this paper cites.
Monotone bipartite graph properties are evasive
Andrew Chi-Chih Yao · 1988
Earlier work this paper cites.
An Ω ( n 4 / 3 ) \Omega(n^{4/3}) lower bound on the randomized complexity of graph properties
Péter Hajnal · 1991
Earlier work this paper cites.
CREW prams and decision trees
Noam Nisan · 1991
Earlier work this paper cites.
Lower bounds to randomized algorithms for graph properties
Andrew Chi-Chih Yao · 1991
Earlier work this paper cites.
Improvements on Khrapchenko’s theorem
Elias Koutsoupias · 1993
Earlier work this paper cites.
On the degree of Boolean functions as real polynomials
Noam Nisan and Mario Szegedy · 1994
Earlier work this paper cites.
On rank vs. communication complexity
Noam Nisan and Avi Wigderson · 1995
Earlier work this paper cites.
Sensitivity vs. block sensitivity of Boolean functions
David Rubinstein · 1995
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani · 1997
Cited alongside, same era.
Bounds for small-error and zero-error quantum algorithms
Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka · 1999
Cited alongside, same era.
Space-time tradeoffs for graph properties
Yevgeniy Dodis and Sanjeev Khanna · 1999
Cited alongside, same era.
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 2001
Cited alongside, same era.
Improved lower bounds on the randomized complexity of graph properties
Amit Chakrabarti and Subhash Khot · 2001
Cited alongside, same era.
Quantum lower bounds by quantum arguments
Andris Ambainis · 2002
Cited alongside, same era.
Matrix computations
Gene H. Golub and Charles F. Van Loan · 2013
Later among the works it cites.
Composition limits and separating examples for some Boolean function complexity measures
Justin Gilmer, Michael Saks, and Srikanth Srinivasan · 2013
Later among the works it cites.
A lower bound for the complexity of monotone graph properties
Robert Scheidweiler and Eberhard Triesch · 2013
Later among the works it cites.
Properties and applications of Boolean function composition
Avishay Tal · 2013
Later among the works it cites.
Separations in query complexity using cheat sheets
Scott Aaronson, Shalev Ben-David, and Robin Kothari · 2016
Later among the works it cites.
Quantum Query Complexity of Subgraph Isomorphism and Homomorphism
Raghav Kulkarni and Supartha Podder · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Complexity measures and decision tree complexity: a survey
Harry Buhrman and Ronald De Wolf · 2002
Cited alongside, same era.
Computing graph properties by randomized subcube partitions
Ehud Friedgut, Jeff Kahn, and Avi Wigderson · 2002
Cited alongside, same era.
Quantum query complexity and semi-definite programming
Howard Barnum, Michael E. Saks, and Mario Szegedy · 2003
Cited alongside, same era.
Exact quantum query complexity for total Boolean functions
Gatis Midrijanis · 2004
Cited alongside, same era.
Every decision tree has an influential variable
Ryan O’Donnell, Michael Saks, Oded Schramm, and Rocco A. Servedio · 2005
Cited alongside, same era.
The quantum adversary method and classical formula size lower bounds
Sophie Laplante, Troy Lee, and Mario Szegedy · 2006
Cited alongside, same era.
On fractional block sensitivity
Raghav Kulkarni and Avishay Tal · 2016
Later among the works it cites.
Separations in query complexity based on pointer functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs · 2017
Later among the works it cites.
Low-sensitivity functions from unambiguous certificates
Shalev Ben-David, Pooya Hatami, and Avishay Tal · 2017
Later among the works it cites.
A nearly optimal lower bound on the approximate degree of AC 0
Mark Bun and Justin Thaler · 2017
Later among the works it cites.
Forrelation: A problem that optimally separates quantum from classical computing
Scott Aaronson and Andris Ambainis · 2018
Later among the works it cites.
Randomized communication versus partition number
Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson · 2018
Later among the works it cites.
Deterministic communication vs. partition number
Mika Göös, Toniann Pitassi, and Thomas Watson · 2018
Later among the works it cites.
Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
Hao Huang · 2019
Later among the works it cites.
Sensitivity lower bounds from linear dependencies
Sophie Laplante, Reza Naserasr, and Anupa Sunny · 2020
Closest in time.