Approximating threshold circuits by rational functions

DOI10.1006/INCO.1994.1059MaRDI QIDQ1333272zbMATH OpenOpenAlexFDO

Authors Ramamohan Paturi, Michael Saks

Publication date 27 August 1995

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1994.1059

zbMATH Keywords

boolean functionsthreshold networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Recommendations

• Size--Depth Tradeoffs for Threshold Circuits
• The complexity of computing symmetric functions using threshold circuits
• Exponential lower bound for bounded depth circuits with few threshold gates

Cited in

(23)

• Quantified Derandomization: How to Find Water in the Ocean
• Efficient threshold circuits for power series
• Neural networks with linear threshold activations: structure and algorithms
• Impossibility results for weak threshold networks
• Algebraic Techniques for Constructing Minimal Weight Threshold Functions
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• The rational approximation of circuit design
• On Blocky Ranks Of Matrices
• Rational approximation techniques for analysis of neural networks
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Algorithmic Polynomials
• A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
• New degree bounds for polynomial threshold functions
• A new theorem in threshold logic and its application to multioperand binary adders
• Decomposition of threshold functions into bounded fan-in threshold functions
• A size-depth trade-off for the analog computation of Boolean functions
• Efficient monotone circuits for threshold functions
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
• The power of asymmetry in constant-depth circuits

This page was built for publication: Approximating threshold circuits by rational functions

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