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

zbMATH Keywords

learningapproximationhardnesshalfspaces

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

Cites Work

• scientific article; zbMATH DE number 1304255 (Why is no real title available?)
• scientific article; zbMATH DE number 2062641 (Why is no real title available?)
• scientific article; zbMATH DE number 1391397 (Why is no real title available?)
• A Parallel Repetition Theorem
• A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
• A polynomial-time algorithm for learning noisy linear threshold functions
• A theory of the learnable
• Agnostically Learning Halfspaces
• 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
• Hardness of learning halfspaces with noise
• Learnability and the Vapnik-Chervonenkis dimension
• Learning an intersection of a constant number of halfspaces over a uniform distribution
• Learning intersections and thresholds of halfspaces
• Learning intersections of halfspaces with a margin
• Noise sensitivity of Boolean functions and applications to percolation
• On agnostic learning of parities, monomials, and halfspaces
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• The complexity of properly learning simple concept classes

Cited In (14)

• The hardest halfspace
• 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)