Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates

DOI10.1016/0020-0190(95)00137-2MaRDI QIDQ672256zbMATHOpenAlexFDO

Authors Stasys Jukna

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(95)00137-2

zbMATH Keywords

Computational complexityLower boundsThreshold circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Mathematical Foundations of Computer Science 2005
• scientific article; zbMATH DE number 773998
• On the computational power of depth-2 circuits with threshold and modulo gates
• On the computational power of depth 2 circuits with threshold and modulo gates
• Threshold circuits of bounded depth
• Threshold circuits of small majority-depth
• On the power of small-depth threshold circuits
• On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
• The complexity of depth-3 circuits computing symmetric Boolean functions
• Exponential lower bound for bounded depth circuits with few threshold gates

Cites work

• scientific article; zbMATH DE number 3889430 (Why is no real title available?)
• scientific article; zbMATH DE number 1142303 (Why is no real title available?)
• scientific article; zbMATH DE number 3328173 (Why is no real title available?)
• On small depth threshold circuits
• Pi-sigma-pi threshold formulas
• Top-down lower bounds for depth-three circuits
• \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom

Cited in

(5)

• Non-uniform Turán-type problems
• Threshold circuits of small majority-depth
• On the computational power of depth-2 circuits with threshold and modulo gates
• On set systems with a threshold property
• Circuit complexity before the dawn of the new millennium

This page was built for publication: Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672256)