Learning an intersection of a constant number of halfspaces over a uniform distribution
From MaRDI portal
Publication:1356892
DOI10.1006/jcss.1997.1475zbMath0877.68064OpenAlexW2015194364MaRDI QIDQ1356892
Ravindran Kannan, Avrim L. Blum
Publication date: 8 December 1997
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/b1dbf0bafa741f850ce832121f6fabc9a5bf6bdf
Learning and adaptive systems in artificial intelligence (68T05) Parallel algorithms in computer science (68W10)
Related Items
Fooling Polytopes ⋮ Learning intersections and thresholds of halfspaces ⋮ On the hardness of learning intersections of two halfspaces ⋮ Learning intersections of halfspaces with a margin ⋮ The hardest halfspace ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries ⋮ On the limits of efficient teachability
Cites Work
- Unnamed Item
- On learning a union of half spaces
- Composite geometric concepts and polynomial predictability
- Learnability and the Vapnik-Chervonenkis dimension
- A theory of the learnable
- Efficient noise-tolerant learning from statistical queries
- Geometry. I, II. Transl. from the French by M. Cole and S. Levy
