Powering requires threshold depth 3

DOI10.1016/j.ipl.2006.11.003zbMath1184.68269OpenAlexW2050739958MaRDI QIDQ845974

Alexander A. Sherstov

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

zbMATH Keywords

computational complexitythreshold circuitscircuit lower boundscomplexity of arithmetic operations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ The unbounded-error communication complexity of symmetric functions

Cites Work

• 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
• Unnamed Item

This page was built for publication: Powering requires threshold depth 3