Exponential lower bound for bounded depth circuits with few threshold gates

DOI10.1016/j.ipl.2011.12.011zbMath1237.68091OpenAlexW1982984553MaRDI QIDQ413295

Vladimir V. Podolskii

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

zbMATH Keywords

computational complexitylower boundsthreshold functionsthreshold circuitsBoolean circuit complexitybounded depth circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

New algorithms and lower bounds for circuits with linear threshold gates ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression

Cites Work

• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Majority gates vs. general weighted threshold gates
• The expressive power of voting polynomials
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• Complex polynomials and circuit lower bounds for modular counting
• Complexity measures and decision tree complexity: a survey.
• PP is closed under intersection
• Threshold circuits of bounded depth
• Learning and Lower Bounds for AC 0 with Threshold Gates
• Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Automata, Languages and Programming
• Natural proofs

This page was built for publication: Exponential lower bound for bounded depth circuits with few threshold gates