\(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom

DOI10.1016/0020-0190(93)90041-7zbMath0783.68046OpenAlexW2027328186MaRDI QIDQ2365817

Avi Wigderson, Alexander A. Razborov

Publication date: 29 June 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90041-7

zbMATH Keywords

lower boundsthreshold circuit

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On the power of a threshold gate at the top ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ Unnamed Item ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates ⋮ Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ On the correlation between parity and modular polynomials ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ On the relationship between energy complexity and other Boolean function measures ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Unnamed Item

Cites Work

• On the power of small-depth threshold circuits
• A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
• Majority gates vs. general weighted threshold gates
• Parity, circuits, and the polynomial-time hierarchy
• On small depth threshold circuits