\(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.68046MaRDI 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 bounds; threshold circuit

Mathematics Subject Classification ID

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

Related Items

One-way multiparty communication lower bound for pointer jumping with applications, Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates, On the correlation between parity and modular polynomials, Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity, Upper and lower bounds for some depth-3 circuit classes, Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates

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