A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
From MaRDI portal
(Redirected from Publication:368235)
Recommendations
- Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length
- Degree-uniform lower bound on the weights of polynomials with given sign function
- Perceptrons of large weight
- Perceptrons of Large Weight
- A Uniform Lower Bound on Weights of Perceptrons
Cites work
- scientific article; zbMATH DE number 446494 (Why is no real title available?)
- scientific article; zbMATH DE number 5605137 (Why is no real title available?)
- scientific article; zbMATH DE number 5485463 (Why is no real title available?)
- scientific article; zbMATH DE number 5485519 (Why is no real title available?)
- A Uniform Lower Bound on Weights of Perceptrons
- Approximating threshold circuits by rational functions
- Complexity measures and decision tree complexity: a survey.
- Computing Boolean functions by polynomials and threshold circuits
- Harmonic Analysis of Polynomial Threshold Functions
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Learning intersections and thresholds of halfspaces
- Majority gates vs. general weighted threshold gates
- New degree bounds for polynomial threshold functions
- On the Power of Threshold Circuits with Small Weights
- On the Size of Weights for Threshold Gates
- On the computational power of Boolean decision lists
- On the computational power of depth-2 circuits with threshold and modulo gates
- On the power of a threshold gate at the top
- PP is closed under intersection
- Perceptrons of large weight
- Perceptrons, PP, and the polynomial hierarchy
- Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
- Rational approximation techniques for analysis of neural networks
- The expressive power of voting polynomials
- Threshold circuits of bounded depth
- Toward attribute efficient learning of decision lists and parities
- Unconditional lower bounds for learning intersections of halfspaces
Cited in
(5)- A Uniform Lower Bound on Weights of Perceptrons
- On XOR lemmas for the weight of polynomial threshold functions
- Degree-uniform lower bound on the weights of polynomials with given sign function
- On XOR lemma for polynomial threshold weight and length
- Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length
This page was built for publication: A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q368235)
