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

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

Ingo Wegener

Publication date: 8 August 1993

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

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90202-k

zbMATH Keywords

lower boundsdivisionthreshold circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

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

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