Powering requires threshold depth 3
From MaRDI portal
Publication:845974
DOI10.1016/j.ipl.2006.11.003zbMath1184.68269MaRDI QIDQ845974
Publication date: 29 January 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2006.11.003
computational complexity; threshold circuits; circuit lower bounds; complexity of arithmetic operations
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Cites Work
- Unnamed Item
- Majority gates vs. general weighted threshold gates
- The expressive power of voting polynomials
- Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
- Threshold circuits of bounded depth
- On the Power of Threshold Circuits with Small Weights
- Depth efficient neural networks for division and related problems
- On Optimal Depth Threshold Circuits for Multiplication and Related Problems
- Simulating Threshold Circuits by Majority Circuits
- On small depth threshold circuits