Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions

Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio +1

Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper we prove two hardness…