Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
From MaRDI portal
Publication:3990097
DOI10.1137/0221003zbMath0743.68063OpenAlexW2117508909MaRDI QIDQ3990097
Roman Smolensky, Jehoshua Bruck
Publication date: 28 June 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0221003
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Discrete mathematics in relation to computer science (68R99)
Related Items
On small depth threshold circuits, Bounds on the Fourier coefficients of the weighted sum function, Approximate Degree in Classical and Quantum Computing, Breaking the Minsky--Papert Barrier for Constant-Depth Circuits, Evaluating spectral norms for constant depth circuits with symmetric gates, Computing sparse approximations deterministically, A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length, Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky, Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\), Improved approximation of linear threshold functions, Randomization and the computational power of analytic and algebraic decision trees, Counting Solutions to Polynomial Systems via Reductions, Approximate F_2-Sketching of Valuation Functions, Solving hybrid Boolean constraints in continuous space via multilinear Fourier expansions, Extremal properties of polynomial threshold functions, Noise sensitivity of Boolean functions and applications to percolation, Majority gates vs. general weighted threshold gates, Polynomial threshold functions and Boolean threshold circuits, A Lifting Theorem with Applications to Symmetric Functions, Spectral properties of threshold functions
