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 (11)

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

This page was built for publication: Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions