On the hardness of learning intersections of two halfspaces
DOI10.1016/J.JCSS.2010.06.010zbMATH Open1213.68496OpenAlexW2072331102MaRDI QIDQ619909FDOQ619909
Authors: Rishi Saket, Subhash Khot 
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
Recommendations
- Unconditional lower bounds for learning intersections of halfspaces
- Cryptographic hardness for learning intersections of halfspaces
- Improved Lower Bounds for Learning Intersections of Halfspaces
- Learning intersections and thresholds of halfspaces
- A random-sampling-based algorithm for learning intersections of halfspaces
Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Learnability and the Vapnik-Chervonenkis dimension
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- A theory of the learnable
- Agnostic Learning of Monomials by Halfspaces Is Hard
- Noise sensitivity of Boolean functions and applications to percolation
- A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
- A Parallel Repetition Theorem
- Agnostically Learning Halfspaces
- On agnostic learning of parities, monomials, and halfspaces
- Learning intersections and thresholds of halfspaces
- The complexity of properly learning simple concept classes
- Title not available (Why is that?)
- A polynomial-time algorithm for learning noisy linear threshold functions
- Title not available (Why is that?)
- An algorithmic theory of learning: Robust concepts and random projection
- Learning an intersection of a constant number of halfspaces over a uniform distribution
- Learning intersections of halfspaces with a margin
- Cryptographic hardness for learning intersections of halfspaces
- Hardness of Reconstructing Multivariate Polynomials over Finite Fields
- Hardness of learning halfspaces with noise
Cited In (15)
- The hardest halfspace
- Agnostic Learning of Monomials by Halfspaces Is Hard
- Learning Theory
- A random-sampling-based algorithm for learning intersections of halfspaces
- Sign-rank can increase under intersection
- New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries
- Improved Lower Bounds for Learning Intersections of Halfspaces
- Dimension, Halfspaces, and the Density of Hard Sets
- Hardness of learning halfspaces with noise
- Improved approximation of linear threshold functions
- Fooling Polytopes
- Learning intersections and thresholds of halfspaces
- Unconditional lower bounds for learning intersections of halfspaces
- Learning intersections of halfspaces with a margin
- Cryptographic hardness for learning intersections of halfspaces
This page was built for publication: On the hardness of learning intersections of two halfspaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q619909)
