Powering requires threshold depth 3

DOI10.1016/J.IPL.2006.11.003MaRDI QIDQ845974zbMATHOpenAlexFDO

Authors 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)

Recommendations

• On Optimal Depth Threshold Circuits for Multiplication and Related Problems
• Threshold circuits of small majority-depth
• Upper and lower bounds for some depth-3 circuit classes
• On the power of small-depth threshold circuits
• On the computational power of depth 2 circuits with threshold and modulo gates

Cites work

• scientific article; zbMATH DE number 524134 (Why is no real title available?)
• Depth efficient neural networks for division and related problems
• Majority gates vs. general weighted threshold gates
• On Optimal Depth Threshold Circuits for Multiplication and Related Problems
• On small depth threshold circuits
• On the Power of Threshold Circuits with Small Weights
• Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
• Simulating Threshold Circuits by Majority Circuits
• The expressive power of voting polynomials
• Threshold circuits of bounded depth

Cited in

(6)

• Hilbert's thirteenth problem and circuit complexity
• Threshold Circuits for Iterated Matrix Product and Powering
• The unbounded-error communication complexity of symmetric functions
• On Optimal Depth Threshold Circuits for Multiplication and Related Problems
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
• Circuit complexity of powering in fields of odd characteristic

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845974)