On the hardness of learning intersections of two halfspaces
From MaRDI portal
Publication:619909
DOI10.1016/j.jcss.2010.06.010zbMath1213.68496MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68T05: Learning and adaptive systems in artificial intelligence
68R10: Graph theory (including graph drawing) in computer science
Related Items
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
