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

Cites work

$\mathrm{AC}^0[p]$ lower bounds against MCSP via the coin problem
$n^{{\Omega{}}(\log{} n)}$ lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
A \#SAT algorithm for small constant-depth circuits with PTF gates
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
A Uniform Circuit Lower Bound for the Permanent
Amplifying lower bounds by means of self-reducibility
An average-case depth hierarchy theorem for Boolean circuits
An average-case lower bound against $\mathsf{ACC}^0$
Approximation by DNF: Examples and Counterexamples
Average-case lower bounds and satisfiability algorithms for small threshold circuits
Bootstrapping results for threshold circuits ``just beyond known lower bounds
Bounded Independence Fools Halfspaces
Bounds on the Size of Small Depth Circuits for Approximating Majority
BQP and the polynomial hierarchy
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
Coin Theorems and the Fourier Expansion
Computing Boolean functions by polynomials and threshold circuits
Constant depth circuits, Fourier transform, and learnability
Depth reduction for circuits of unbounded fan-in
Depth reduction for composites
Every linear threshold function has a low-weight approximator
Faster all-pairs shortest paths via circuit complexity
Hardness amplification and the approximate degree of constant-depth circuits
Hardness Amplification Proofs Require Majority
scientific article; zbMATH DE number 2081103 (Why is no real title available?)
scientific article; zbMATH DE number 2086623 (Why is no real title available?)
scientific article; zbMATH DE number 3314813 (Why is no real title available?)
scientific article; zbMATH DE number 7650319 (Why is no real title available?)
Improved bounds on the sign-rank of $\mathrm{AC}^0$
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
Multiparty communication complexity and threshold circuit size of AC^0
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
New degree bounds for polynomial threshold functions
Nonuniform ACC circuit lower bounds
On ACC
On the approximability of clique and related maximization problems
On the computational power of depth-2 circuits with threshold and modulo gates
On the power of small-depth threshold circuits
Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms
PP is as Hard as the Polynomial-Time Hierarchy
Quantified derandomization of linear threshold circuits
Randomness buys depth for approximate counting
Satisfiability and derandomization for small polynomial threshold circuits
Separating AC$^0$ from depth-2 majority circuits
Sharp threshold results for computational complexity
Size--Depth Tradeoffs for Threshold Circuits
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
The coin problem for product tests
The large-error approximate degree of $\mathrm{AC}^0$
The pattern matrix method
The power of asymmetry in constant-depth circuits
The Shrinkage Exponent of de Morgan Formulas is 2
The Sign-Rank of AC^0
Threshold circuits of bounded depth
Two sides of the coin problem

Cited in

(2)

A technique for hardness amplification against AC^0
Low-degree polynomials are good extractors

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499273)