Fetching the paper…
Reading the bibliography…
We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of $\mathsf{AND}$, $\mathsf{OR}$, and $\mathsf{NOT}$ gates.
Realizations of linear functions by formulas using ∨ \vee , &, ¯ \overline{\ }
Bella Subbotovskaya · 1961
Earlier work this paper cites.
Relativizations of the P
Theodore Baker, John Gill, and Robert Solovay · 1975
Earlier work this paper cites.
A second step toward the polynomial hierarchy
Theodore Baker and Alan Selman · 1979
Earlier work this paper cites.
Relative to a random oracle A A , 𝖯 A ≠ 𝖭𝖯 A ≠ 𝖼𝗈𝖭𝖯 A {\sf P}^{A}\not={\sf NP}^{A}\not={\sf coNP}^{A} with probability 1
Charles Bennett and John Gill · 1981
Earlier work this paper cites.
Parity, circuits, and the polynomial-time hierarchy
Merrick Furst, James Saxe, and Michael Sipser · 1981
Earlier work this paper cites.
Σ 1 1 \Sigma_{1}^{1} -formulae on finite structures
Miklós Ajtai · 1983
Earlier work this paper cites.
Borel sets and circuit complexity
Michael Sipser · 1983
Earlier work this paper cites.
Exponential lower bounds for restricted monotone circuits
Leslie Valiant · 1983
Earlier work this paper cites.
On monotone formulae with restricted depth
Maria Klawe, Wolfgang Paul, Nicholas Pippenger, and Mihalis Yannakakis · 1984
Earlier work this paper cites.
Separating the polynomial-time hierarchy by oracles
Andrew Yao · 1985
Earlier work this paper cites.
With probability one, a random oracle separates PSPACE
Jin-Yi Cai · 1986
Earlier work this paper cites.
Almost optimal lower bounds for small depth circuits
Johan Håstad · 1986
Earlier work this paper cites.
Computational Limitations for Small Depth Circuits
Johan Håstad · 1986
Earlier work this paper cites.
Random oracles separate PSPACE
László Babai · 1987
Earlier work this paper cites.
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
Alexander Razborov · 1987
Earlier work this paper cites.
Algebraic methods in the theory of lower bounds for boolean circuit complexity
Roman Smolensky · 1987
Earlier work this paper cites.
Almost optimal lower bounds for small depth circuits
Johan Håstad · 1989
Earlier work this paper cites.
Query complexity, or why is it difficult to separate 𝖭𝖯 A ∩ 𝖼𝗈𝖭𝖯 A \mathsf{NP}^{A}\cap\mathsf{coNP}^{A} from 𝖯 A \mathsf{P}^{A} by random oracles A A ?
Gábor Tardos · 1989
Earlier work this paper cites.
Pseudorandom bits for constant depth circuits
Noam Nisan · 1991
Earlier work this paper cites.
Threshold circuits of bounded depth
András Hajnal, Wolfgang Maass, Pavel Pudlák, Márió Szegedy, and György Turán · 1993
Earlier work this paper cites.
Constant depth circuits, fourier transform, and learnability
Nathan Linial, Yishay Mansour, and Noam Nisan · 1993
Earlier work this paper cites.
Exponential lower bounds for the pigeonhole principle
Toniann Pitassi, Paul Beame, and Russell Impagliazzo · 1993
Cited alongside, same era.
The independence of the modulo p p counting principles
Miklós Ajtai · 1994
Cited alongside, same era.
A switching lemma primer
Paul Beame · 1994
Cited alongside, same era.
On collapsing the polynomial-time hierarchy
Ronald Book · 1994
Cited alongside, same era.
Complexity theory column 5: the not-ready-for-prime-time conjectures
Lane Hemaspaandra · 1994
Cited alongside, same era.
Worlds to die for
Lane Hemaspaandra, Ajit Ramachandran, and Marius Zimand · 1995
Cited alongside, same era.
An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
Threshold phenomena and influence
Gil Kalai and Shmuel Safra · 2005
Later among the works it cites.
Lecture 29: Open Problems
Ryan O’Donnell · 2007
Later among the works it cites.
Approximation by DNF: examples and counterexamples
Ryan O’Donnell and Karl Wimmer · 2007
Later among the works it cites.
Computational Complexity: a modern approach
Sanjeev Arora and Boaz Barak · 2009
Later among the works it cites.
Polylogarithmic independence can fool DNF formulas
Louay Bazzi · 2009
Later among the works it cites.
A simple proof of Bazzi’s theorem
Alexander Razborov · 2009
Later among the works it cites.
Notes on switching lemmas, 2009
Neil Thapen · 2009
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Jan Krajíček, Pavel Pudlák, and Alan Woods · 1995
Cited alongside, same era.
An O ( n log log n ) O(n^{\log\log n}) learning algorithm for DNF under the uniform distribution
Yishay Mansour · 1995
Cited alongside, same era.
Bounded arithmetic and lower bounds in Boolean complexity
Alexander Razborov · 1995
Cited alongside, same era.
Computational Complexity
David Shmoys and Éva Tardos · 1995
Cited alongside, same era.
On the Fourier spectrum of monotone functions
Nader Bshouty and Christino Tamon · 1996
Cited alongside, same era.
The average sensitivity of bounded-depth circuits
Ravi Boppana · 1997
Cited alongside, same era.
Later among the works it cites.
A counterexample to the generalized Linial-Nisan conjecture
Scott Aaronson · 2010
Later among the works it cites.
Polylogarithmic independence fools 𝖠𝖢 0 {\sf AC}^{0} circuits
Mark Braverman · 2010
Later among the works it cites.
Noise Stability and Threshold Circuits
Gil Kalai · 2010
Later among the works it cites.
Approximating 𝖠𝖢 𝟢 \mathsf{AC^{0}} by small height decision trees and a deterministic algorithm for # 𝖠𝖢 𝟢 \#\mathsf{AC^{0}} - 𝖲𝖠𝖳 \mathsf{SAT}
Paul Beame, Russell Impagliazzo, and Srikanth Srinivasan · 2012
Later among the works it cites.
A satisfiability algorithm for 𝖠𝖢 𝟢 \mathsf{AC^{0}}
Russell Impagliazzo, William Matthews, and Ramamohan Paturi · 2012
Later among the works it cites.
Boolean Function Complexity
Stasys Jukna · 2012
Later among the works it cites.
Answer to the question: Are all functions whose Fourier weight is concentrated on the small sized sets computed by 𝖠𝖢 0 \mathsf{AC}^{0} circuits?
Gil Kalai · 2012
Later among the works it cites.
On the size of depth-three Boolean circuits for computing multilinear functions
Oded Goldreich and Avi Wigderson · 2013
Later among the works it cites.
Challenges in computational lower bounds
Emanuele Viola · 2013
Later among the works it cites.
On the correlation of parity and small-depth circuits
Johan Håstad · 2014
Later among the works it cites.
Scribe notes for the course COMP760: Harmonic Analysis of Boolean Functions
Hamed Hatami · 2014
Later among the works it cites.
Faster all-pairs shortest paths via circuit complexity
Ryan Williams · 2014
Later among the works it cites.
The polynomial method in circuit complexity applied to algorithm design (invited survey)
Ryan Williams · 2014
Later among the works it cites.
More applications of the polynomial method to algorithm design
Amir Abboud, Ryan Williams, and Huacheng Yu · 2015
Closest in time.