Exponential lower bound for bounded depth circuits with few threshold gates
DOI10.1016/J.IPL.2011.12.011zbMATH Open1237.68091OpenAlexW1982984553MaRDI QIDQ413295FDOQ413295
Publication date: 4 May 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2011.12.011
Recommendations
computational complexitylower boundsthreshold circuitsBoolean circuit complexitythreshold functionsbounded depth circuits
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The expressive power of voting polynomials
- Majority gates vs. general weighted threshold gates
- Threshold circuits of bounded depth
- Natural proofs
- Complexity measures and decision tree complexity: a survey.
- PP is closed under intersection
- Complex polynomials and circuit lower bounds for modular counting
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- Learning and Lower Bounds for AC 0 with Threshold Gates
- Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
- Automata, Languages and Programming
Cited In (17)
- On the computational power of depth-2 circuits with threshold and modulo gates
- Threshold circuits of small majority-depth
- Title not available (Why is that?)
- Title not available (Why is that?)
- New algorithms and lower bounds for circuits with linear threshold gates
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Title not available (Why is that?)
- Exponential size lower bounds for some depth three circuits
- Exponential lower bounds for depth three Boolean circuits
- Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
- Title not available (Why is that?)
- Lower bounds on threshold and related circuits via communication complexity
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- Lower bounds for constant-depth circuits in the presence of help bits
- Parity, circuits, and the polynomial-time hierarchy
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates
This page was built for publication: Exponential lower bound for bounded depth circuits with few threshold gates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q413295)
