\(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
From MaRDI portal
Publication:2365817
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
Related Items (15)
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
This page was built for publication: \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
