Unconditional lower bounds for learning intersections of halfspaces
DOI10.1007/S10994-007-5010-1zbMATH Open1470.68056OpenAlexW2140283251MaRDI QIDQ1009217FDOQ1009217
Authors: Adam R. Klivans, Alexander A. Sherstov 
Publication date: 31 March 2009
Published in: Machine Learning (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10994-007-5010-1
Recommendations
- Improved Lower Bounds for Learning Intersections of Halfspaces
- Learning intersections and thresholds of halfspaces
- On the hardness of learning intersections of two halfspaces
- A random-sampling-based algorithm for learning intersections of halfspaces
- Learning an intersection of a constant number of halfspaces over a uniform distribution
query learningPAC learningpolynomial threshold functionshalfspace learningharmonic sieveintersections of halfspaceslower bounds for learningSQ learningstatistical queries
Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Learning Decision Trees Using the Fourier Spectrum
- Title not available (Why is that?)
- Title not available (Why is that?)
- Hyperplane cuts of an n-cube
- Noise-tolerant learning, the parity problem, and the statistical query model
- The expressive power of voting polynomials
- Harmonic Analysis of Polynomial Threshold Functions
- A theory of the learnable
- Efficient noise-tolerant learning from statistical queries
- PAC learning intersections of halfspaces with membership queries
- PP is closed under intersection
- On the computational power of depth-2 circuits with threshold and modulo gates
- On the Fourier spectrum of monotone functions
- New degree bounds for polynomial threshold functions
- Learning intersections and thresholds of halfspaces
- Title not available (Why is that?)
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- A polynomial-time algorithm for learning noisy linear threshold functions
- New lower bounds for statistical query learning
- Cryptographic hardness for learning intersections of halfspaces
- Learning Theory
Cited In (17)
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- A Uniform Lower Error Bound for Half-Space Learning
- Learning Theory
- Title not available (Why is that?)
- The unbounded-error communication complexity of symmetric functions
- A complete characterization of statistical query learning with applications to evolvability
- On XOR lemmas for the weight of polynomial threshold functions
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- The average sensitivity of an intersection of half spaces
- A Borsuk-Ulam lower bound for sign-rank and its applications
- Improved Lower Bounds for Learning Intersections of Halfspaces
- A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
- Learning intersections and thresholds of halfspaces
- On the hardness of learning intersections of two halfspaces
- The average sensitivity of an intersection of half spaces
- Learning intersections of halfspaces with a margin
- Cryptographic hardness for learning intersections of halfspaces
This page was built for publication: Unconditional lower bounds for learning intersections of halfspaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1009217)
