Exponential lower bound for bounded depth circuits with few threshold gates

DOI10.1016/j.ipl.2011.12.011zbMath1237.68091MaRDI 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 complexity; lower bounds; threshold functions; threshold circuits; Boolean circuit complexity; bounded depth circuits

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

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

Related Items

Unnamed Item, New algorithms and lower bounds for circuits with linear threshold gates, 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