Exponential lower bound for bounded depth circuits with few threshold gates

DOI10.1016/J.IPL.2011.12.011MaRDI QIDQ413295zbMATHOpenAlexFDO

Authors 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 circuitsBoolean circuit complexitythreshold functionsbounded 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)

Recommendations

• Size--Depth Tradeoffs for Threshold Circuits
• Exponential sums and circuits with a single threshold gate and mod-gates
• Upper and lower bounds for some depth-3 circuit classes
• scientific article; zbMATH DE number 1559525
• Exponential lower bounds for depth three Boolean circuits

Cites work

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

Cited in

(20)

• A nonuniform circuit class with multilayer of threshold gates having super quasi polynomial size lower bounds against NEXP
• Lower bounds on threshold and related circuits via communication complexity
• Lower bounds for constant-depth circuits in the presence of help bits
• scientific article; zbMATH DE number 1559525 (Why is no real title available?)
• Exponential lower bounds for depth three Boolean circuits
• On the power of a threshold gate at the top
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• scientific article; zbMATH DE number 773999 (Why is no real title available?)
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• scientific article; zbMATH DE number 7204282 (Why is no real title available?)
• Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates
• Threshold circuits of small majority-depth
• On the computational power of depth-2 circuits with threshold and modulo gates
• scientific article; zbMATH DE number 1405686 (Why is no real title available?)
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Parity, circuits, and the polynomial-time hierarchy
• Cosmological lower bound on the circuit complexity of a small problem in logic
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Exponential size lower bounds for some depth three circuits
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom

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)