Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions

DOI10.1016/0020-0190(93)90202-KzbMath0770.68076MaRDI QIDQ1802063

Ingo Wegener

Publication date: 8 August 1993

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

zbMATH Keywords

lower bounds; division; threshold circuits

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

Related Items

Threshold Circuits for Iterated Matrix Product and Powering, General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results, Larger lower bounds on the OBDD complexity of integer multiplication, Powering requires threshold depth 3, Approximating Boolean functions by OBDDs, BDDs -- design, analysis, complexity, and applications., On the OBDD complexity of the most significant bit of integer multiplication, Cryptographic hardness for learning intersections of halfspaces, On the OBDD Complexity of the Most Significant Bit of Integer Multiplication, Larger Lower Bounds on the OBDD Complexity of Integer Multiplication

Cites Work

• Majority gates vs. general weighted threshold gates
• On the Power of Threshold Circuits with Small Weights
• Depth efficient neural networks for division and related problems
• On small depth threshold circuits