file.pdf (277.33 kB)
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
journal contribution
posted on 1992-06-01, 00:00 authored by Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi WuHardness 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 results for the
problem of finding a low degree polynomial threshold function (PTF) which has the maximum possible
agreement with a given set of labeled examples in Rn x {-1; 1}.