On the hardness of learning intersections of two halfspaces
From MaRDI portal
Publication:619909
DOI10.1016/j.jcss.2010.06.010zbMath1213.68496OpenAlexW2072331102MaRDI QIDQ619909
Publication date: 18 January 2011
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.010
Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Graph theory (including graph drawing) in computer science (68R10)
Related Items (4)
Fooling Polytopes ⋮ Improved approximation of linear threshold functions ⋮ The hardest halfspace ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Learning intersections and thresholds of halfspaces
- A polynomial-time algorithm for learning noisy linear threshold functions
- Learning an intersection of a constant number of halfspaces over a uniform distribution
- The complexity of properly learning simple concept classes
- Learning intersections of halfspaces with a margin
- An algorithmic theory of learning: Robust concepts and random projection
- Cryptographic hardness for learning intersections of halfspaces
- Hardness of Reconstructing Multivariate Polynomials over Finite Fields
- Proof verification and the hardness of approximation problems
- Learnability and the Vapnik-Chervonenkis dimension
- Agnostically Learning Halfspaces
- On Agnostic Learning of Parities, Monomials, and Halfspaces
- Hardness of Learning Halfspaces with Noise
- A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
- A theory of the learnable
- Probabilistic checking of proofs
- A Parallel Repetition Theorem
- Agnostic Learning of Monomials by Halfspaces Is Hard
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Noise sensitivity of Boolean functions and applications to percolation
This page was built for publication: On the hardness of learning intersections of two halfspaces
