Hardness of Learning Halfspaces with Noise

DOI10.1137/070685798zbMath1198.68157OpenAlexW2065923584MaRDI QIDQ3558021

Prasad Raghavendra, Venkatesan Guruswami

Publication date: 29 April 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070685798

zbMATH Keywords

perceptroncomputational learninghardness of approximation

Mathematics Subject Classification ID

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

Related Items (10)

Stronger data poisoning attacks break data sanitization defenses ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Complexity and approximability of parameterized MAX-CSPs ⋮ On the hardness of learning intersections of two halfspaces ⋮ Regret minimization in online Bayesian persuasion: handling adversarial receiver's types under full and partial feedback models ⋮ Robust classification via MOM minimization ⋮ Polynomial regression under arbitrary product distributions ⋮ Unnamed Item ⋮ Approximating maximum satisfiable subsystems of linear equations of bounded width

This page was built for publication: Hardness of Learning Halfspaces with Noise