On the Power of Threshold Circuits with Small Weights

DOI10.1137/0404038zbMATH Open0737.68035OpenAlexW1990284858MaRDI QIDQ3979443FDOQ3979443

Authors: Kai-Yeung Siu, Jehoshua Bruck 

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/

Recommendations

• On the power of small-depth threshold circuits
• Perceptrons of large weight
• 2-1 addition and related arithmetic operations with threshold logic
• Majority gates vs. general weighted threshold gates

zbMATH Keywords

threshold circuitscircuit depthlinear threshold functionspolynomial bounded weights

Mathematics Subject Classification ID

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

Cited In (24)

• The hardest halfspace
• 2-1 addition and related arithmetic operations with threshold logic
• Threshold circuits of small majority-depth
• Powering requires threshold depth 3
• Impossibility results for weak threshold networks
• On the power of small-depth threshold circuits
• Evaluating spectral norms for constant depth circuits with symmetric gates
• Title not available (Why is that?)
• A short list of equalities induces large sign-rank
• Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
• Majority gates vs. general weighted threshold gates
• Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
• A weight-size trade-off for circuits with MOD \(m\) gates
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• A note on neural sorting networks with O(1) time complexity
• Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
• A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
• On small depth threshold circuits
• Decomposition of threshold functions into bounded fan-in threshold functions
• Neural networks and complexity theory
• A weak version of the Blum, Shub, and Smale model
• Title not available (Why is that?)
• On the Power of Threshold Measurements as Oracles
• 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

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