On Optimal Depth Threshold Circuits for Multiplication and Related Problems

DOI10.1137/S0895480192228619zbMath0822.68034OpenAlexW1981703098MaRDI QIDQ4296522

Kai-Yeung Siu, Vwani P. Roychowdhury

Publication date: 9 October 1995

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480192228619

zbMATH Keywords

linear threshold functionsthreshold circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ On the power of a threshold gate at the top ⋮ On small depth threshold circuits ⋮ Powering requires threshold depth 3 ⋮ General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results ⋮ Decomposition of threshold functions into bounded fan-in threshold functions ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Cryptographic hardness for learning intersections of halfspaces ⋮ Threshold circuits of small majority-depth ⋮ A new theorem in threshold logic and its application to multioperand binary adders ⋮ Efficient threshold circuits for power series

This page was built for publication: On Optimal Depth Threshold Circuits for Multiplication and Related Problems