Approximating threshold circuits by rational functions
From MaRDI portal
Publication:1333272
DOI10.1006/inco.1994.1059zbMath0820.68054OpenAlexW1979124844MaRDI QIDQ1333272
Ramamohan Paturi, Michael E. 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
Analysis of algorithms and problem complexity (68Q25) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)
Related Items
When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one, Quantified Derandomization: How to Find Water in the Ocean, Breaking the Minsky--Papert Barrier for Constant-Depth Circuits, The Power of Asymmetry in Constant-Depth Circuits, A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length, Algorithmic Polynomials, New degree bounds for polynomial threshold functions, A size-depth trade-off for the analog computation of Boolean functions, Optimal bounds for sign-representing the intersection of two halfspaces by polynomials, Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$, Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity, Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits, A new theorem in threshold logic and its application to multioperand binary adders
