Fetching the paper…
Reading the bibliography…
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, $\bullet \quad \mathrm{deg}(f) = O(\widetilde{\mathrm{deg}}(f)^2)$: The degree of $f$ is at most quadratic in the approximate degree of $f$.
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.
On the norm of a schur product
Martin E. Walter · 1986
Earlier work this paper cites.
The singular values of a Hadamard product: a basic inequality
T. Ando, Roger A. Horn, and Charles R. Johnson · 1987
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
Earlier work this paper cites.
Bounds for small-error and zero-error quantum algorithms
Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka · 1999
Earlier work this paper cites.
Space-time tradeoffs for graph properties
Yevgeniy Dodis and Sanjeev Khanna · 1999
Earlier work this paper cites.
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 2001
Earlier work this paper cites.
Improved lower bounds on the randomized complexity of graph properties
Amit Chakrabarti and Subhash Khot · 2001
Cited alongside, same era.
Algebraic Graph Theory
Chris Godsil and Gordon Royle · 2001
Cited alongside, same era.
Quantum lower bounds by quantum arguments
Andris Ambainis · 2002
Cited alongside, same era.
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.
Superlinear advantage for exact quantum algorithms
Andris Ambainis · 2013
Later among the works it cites.
Dual lower bounds for approximate degree and Markov-Bernstein inequalities
Mark Bun and Justin Thaler · 2013
Later among the works it cites.
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.
Approximating the AND-OR tree
Alexander A. Sherstov · 2013
Later among the works it cites.
Making polynomials robust to noise
Alexander A. Sherstov · 2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Scott Aaronson, Shalev Ben-David, Robin Kothari, and Avishay Tal · 2004
Cited alongside, same era.
A lower bound on the quantum query complexity of read-once functions
Howard Barnum and Michael Saks · 2004
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.
All quantum adversary methods are equivalent
Robert Spalek and Mario Szegedy · 2006
Cited alongside, same era.
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.
Hardness amplification and the approximate degree of constant-depth circuits
Mark Bun and Justin Thaler · 2015
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.
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.
Classical lower bounds from quantum upper bounds
Shalev Ben-David, Adam Bouland, Ankit Garg, and Robin Kothari · 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.