On agnostic learning of parities, monomials, and halfspaces
DOI10.1137/070684914zbMATH Open1198.68156OpenAlexW1968540673MaRDI QIDQ3558016FDOQ3558016
Authors: Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami 
Publication date: 29 April 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/7a2f79fb2f5f2a1880cabea71c93350be8e729d0
Recommendations
Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (36)
- Realizable learning is all you need
- Solving the learning parity with noise's open question
- Stronger data poisoning attacks break data sanitization defenses
- Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes
- Approximate resilience, monotonicity, and the complexity of agnostic learning
- Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
- Hardness results for agnostically learning low-degree polynomial threshold functions
- A new column generation algorithm for logical analysis of data
- On the power of membership queries in agnostic learning
- A complete characterization of statistical query learning with applications to evolvability
- Statistical computational learning
- Agnostically Learning Halfspaces
- Agnostic learning of disjunctions on symmetric distributions
- Improper learning by refuting
- Embedding hard learning problems into Gaussian space
- Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
- Self-improved gaps almost everywhere for the agnostic approximation of monomials
- A Lower Bound for Agnostically Learning Disjunctions
- Pseudorandom functions: three decades later
- Improved learning of \(k\)-parities
- Improved learning of \(k\)-parities
- Agnostically learning Boolean functions with finite polynomial representation
- Lower bounds for agnostic learning via approximate rank
- Algorithmic signaling of features in auction design
- New Algorithms for Learning in Presence of Errors
- Testing distributional assumptions of learning algorithms
- Hardness of learning halfspaces with noise
- Title not available (Why is that?)
- Improved approximation of linear threshold functions
- From average case complexity to improper learning complexity
- On the hardness of learning intersections of two halfspaces
- BKW meets Fourier new algorithms for LPN with sparse parities
- Complexity theoretic limitations on learning halfspaces
- Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
- Maximizing agreements and coagnostic learning
- Cryptographic hardness for learning intersections of halfspaces
This page was built for publication: On agnostic learning of parities, monomials, and halfspaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3558016)
