Agnostic Learning of Monomials by Halfspaces Is Hard
From MaRDI portal
Publication:4910575
DOI10.1137/120865094zbMath1261.68063arXiv1012.0729MaRDI QIDQ4910575
Yi Wu, Venkatesan Guruswami, Vitaly Feldman, Prasad Raghavendra
Publication date: 19 March 2013
Published in: SIAM Journal on Computing, 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1012.0729
68Q32: Computational learning theory
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)