Depth-$d$ threshold circuits vs. depth-$(d+1)$ and-or trees

Cites Work

Randomness buys depth for approximate counting
On the power of small-depth threshold circuits
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
On the computational power of depth-2 circuits with threshold and modulo gates
Computing Boolean functions by polynomials and threshold circuits
Depth reduction for circuits of unbounded fan-in
On ACC
On the approximability of clique and related maximization problems
A \#SAT algorithm for small constant-depth circuits with PTF gates
An average-case lower bound against $\mathsf{ACC}^0$
$n^{{\Omega{}}(\log{} n)}$ lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
Threshold circuits of bounded depth
Every linear threshold function has a low-weight approximator
Natural Proofs versus Derandomization
BQP and the polynomial hierarchy
Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
Two Sides of the Coin Problem
The Sign-Rank of AC$^0$
Constant depth circuits, Fourier transform, and learnability
Nonuniform ACC Circuit Lower Bounds
The Pattern Matrix Method
PP is as Hard as the Polynomial-Time Hierarchy
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Amplifying lower bounds by means of self-reducibility
Bounds on the Size of Small Depth Circuits for Approximating Majority
Separating ${AC}^0$ from Depth-2 Majority Circuits
Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
A Uniform Circuit Lower Bound for the Permanent
Size--Depth Tradeoffs for Threshold Circuits
The Shrinkage Exponent of de Morgan Formulas is 2
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
Faster All-Pairs Shortest Paths via Circuit Complexity
The Power of Asymmetry in Constant-Depth Circuits
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
Improved Bounds on the Sign-Rank of AC^0
New algorithms and lower bounds for circuits with linear threshold gates
Depth Reduction for Composites
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem]
The Coin Problem for Product Tests
Coin Theorems and the Fourier Expansion
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma
Sharp threshold results for computational complexity
Bootstrapping results for threshold circuits “just beyond” known lower bounds
Quantified derandomization of linear threshold circuits
Hardness Amplification Proofs Require Majority
Bounded Independence Fools Halfspaces
Approximation by DNF: Examples and Counterexamples
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
New degree bounds for polynomial threshold functions
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item

This page was built for publication: Depth-$d$ threshold circuits vs. depth-$(d+1)$ and-or trees

Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees