Agnostic Learning of Monomials by Halfspaces is Hard

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra +1

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-\eps)$…