On Optimal Depth Threshold Circuits for Multiplication and Related Problems

DOI10.1137/S0895480192228619zbMATH Open0822.68034OpenAlexW1981703098MaRDI QIDQ4296522FDOQ4296522

Authors: Kai-Yeung Siu, Vwani 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

Recommendations

• Some notes on threshold circuits, and multiplication in depth 4
• On realizing iterated multiplication by small depth threshold circuits
• Threshold circuits of small majority-depth
• Powering requires threshold depth 3
• On the power of small-depth threshold circuits

zbMATH Keywords

threshold circuitslinear threshold functions

Mathematics Subject Classification ID

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

Cited In (20)

• On the computational power of depth-2 circuits with threshold and modulo gates
• 2-1 addition and related arithmetic operations with threshold logic
• Threshold circuits of small majority-depth
• Threshold Circuits for Iterated Matrix Product and Powering
• Powering requires threshold depth 3
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• On Computing Multilinear Polynomials Using Multi- r -ic Depth Four Circuits
• On the power of a threshold gate at the top
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
• Efficient threshold circuits for power series
• Fast and Efficient Circuit Topologies forFinding the Maximum of n k-Bit Numbers
• Depth-efficient threshold circuits for multiplication and symmetric function computation
• On realizing iterated multiplication by small depth threshold circuits
• A new theorem in threshold logic and its application to multioperand binary adders
• General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
• On the size of depth-two threshold circuits for the inner product mod 2 function
• On small depth threshold circuits
• Title not available (Why is that?)
• Decomposition of threshold functions into bounded fan-in threshold functions
• Cryptographic hardness for learning intersections of halfspaces

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

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