A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
From MaRDI portal
Publication:368235
DOI10.1134/S0001434610050263zbMath1317.94168MaRDI QIDQ368235
Alexander A. Sherstov, Vladimir V. Podolskii
Publication date: 18 September 2013
Published in: Mathematical Notes (Search for Journal in Brave)
discrete Fourier transformperceptronBoolean functioncomplexity theoryinteger-valued polynomialBoolean circuitexponential gapsign function
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of a threshold gate at the top
- Learning intersections and thresholds of halfspaces
- Perceptrons of large weight
- On the computational power of Boolean decision lists
- Unconditional lower bounds for learning intersections of halfspaces
- Majority gates vs. general weighted threshold gates
- On the computational power of depth-2 circuits with threshold and modulo gates
- Computing Boolean functions by polynomials and threshold circuits
- The expressive power of voting polynomials
- Approximating threshold circuits by rational functions
- Perceptrons, PP, and the polynomial hierarchy
- Complexity measures and decision tree complexity: a survey.
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- PP is closed under intersection
- Threshold circuits of bounded depth
- Harmonic Analysis of Polynomial Threshold Functions
- A Uniform Lower Bound on Weights of Perceptrons
- On the Power of Threshold Circuits with Small Weights
- Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
- On the Size of Weights for Threshold Gates
- Rational approximation techniques for analysis of neural networks
- New degree bounds for polynomial threshold functions
