On agnostic learning of parities, monomials, and halfspaces

DOI10.1137/070684914MaRDI QIDQ3558016zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

random noisemonomialsparitiesagnostic learninghalfspaces

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Agnostically Learning Halfspaces
• Complexity theoretic limitations on learning halfspaces
• Hardness of learning halfspaces with noise
• On the difficulty of approximately maximizing agreements.

Cited in

(36)

• Cryptographic hardness for learning intersections of halfspaces
• 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]\)
• A new column generation algorithm for logical analysis of data
• Hardness results for agnostically learning low-degree polynomial threshold functions
• A complete characterization of statistical query learning with applications to evolvability
• On the power of membership queries in agnostic learning
• Agnostically Learning Halfspaces
• Statistical computational learning
• Agnostic learning of disjunctions on symmetric distributions
• Improper learning by refuting
• Embedding hard learning problems into Gaussian space
• Self-improved gaps almost everywhere for the agnostic approximation of monomials
• Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
• A Lower Bound for Agnostically Learning Disjunctions
• Pseudorandom functions: three decades later
• Agnostically learning Boolean functions with finite polynomial representation
• Improved learning of \(k\)-parities
• Improved learning of \(k\)-parities
• 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
• Improved approximation of linear threshold functions
• scientific article; zbMATH DE number 2089368 (Why is no real title available?)
• 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
• Maximizing agreements and coagnostic learning
• Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
• Complexity theoretic limitations on learning 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)