Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HARDNESS OF LEARNING:
Reports tagged with Hardness of Learning:
TR10-185 | 2nd December 2010
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

#### Agnostic Learning of Monomials by Halfspaces is Hard

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\epsilon)$ of the examples, it is $\mathrm{NP}$-hard to find a halfspace that is correct on $(1/2+\epsilon)$ of the examples, for arbitrary constants \$\epsilon ... more >>>

TR14-063 | 23rd April 2014