On the Power of Threshold Circuits with Small Weights

DOI10.1137/0404038zbMath0737.68035OpenAlexW1990284858MaRDI QIDQ3979443

Jehoshua Bruck, Kai-Yeung Siu

Publication date: 26 June 1992

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

Full work available at URL: https://authors.library.caltech.edu/30278/

zbMATH Keywords

linear threshold functionsthreshold circuitscircuit depthpolynomial bounded weights

Mathematics Subject Classification ID

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

Related Items (17)

On small depth threshold circuits ⋮ Powering requires threshold depth 3 ⋮ A note on neural sorting networks with O(1) time complexity ⋮ Evaluating spectral norms for constant depth circuits with symmetric gates ⋮ A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length ⋮ Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\) ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Decomposition of threshold functions into bounded fan-in threshold functions ⋮ Neural networks and complexity theory ⋮ The hardest halfspace ⋮ A weak version of the Blum, Shub, and Smale model ⋮ Majority gates vs. general weighted threshold gates ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ Threshold circuits of small majority-depth ⋮ Computing majority by constant depth majority circuits with low fan-in gates

This page was built for publication: On the Power of Threshold Circuits with Small Weights