New degree bounds for polynomial threshold functions
From MaRDI portal
Publication:5894427
DOI10.1007/s00493-010-2173-3zbMath1240.05303OpenAlexW2610386774MaRDI QIDQ5894427
Ryan O'Donnell, Rocco A. Servedio
Publication date: 19 December 2011
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-010-2173-3
Computational learning theory (68Q32) Algebraic combinatorics (05E99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of computing (68Q99)
Related Items
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ Fooling Polytopes ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Decision functions for chain classifiers based on Bayesian networks for multi-label classification ⋮ Unnamed Item ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Algorithmic Polynomials ⋮ The hardest halfspace ⋮ On XOR lemmas for the weight of polynomial threshold functions ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Unnamed Item ⋮ On neuronal capacity ⋮ Unnamed Item ⋮ Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of a threshold gate at the top
- 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.
- PP is closed under intersection
- Boosting a weak learning algorithm by majority
- Threshold circuits of bounded depth
- Minimization of decision trees is hard to approximate
- Rational approximation to \(|x|\)
- Constant depth circuits, Fourier transform, and learnability
- Harmonic Analysis of Polynomial Threshold Functions
- A theory of the learnable
- Learning DNF in time
- New degree bounds for polynomial threshold functions
