Hardness Results for Agnostically Learning Low-Degree Polynomial
  Threshold Functions
  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 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 $\R^n \times \{-1,1\}.$ We prove that
for any constants $d\geq 1, \eps > 0$,
  {itemize}
  Assuming the Unique Games Conjecture, no polynomial-time algorithm can find a
degree-$d$ PTF that is consistent with a $(\half + \eps)$ fraction of a given
set of labeled examples in $\R^n \times \{-1,1\}$, even if there exists a
degree-$d$ PTF that is consistent with a $1-\eps$ fraction of the examples.
  It is $\NP$-hard to find a degree-2 PTF that is consistent with a $(\half +
\eps)$ fraction of a given set of labeled examples in $\R^n \times \{-1,1\}$,
even if there exists a halfspace (degree-1 PTF) that is consistent with a $1 -
\eps$ fraction of the examples.
  {itemize}
  These results immediately imply the following hardness of learning results:
(i) Assuming the Unique Games Conjecture, there is no better-than-trivial
proper learning algorithm that agnostically learns degree-$d$ PTFs under
arbitrary distributions; (ii) There is no better-than-trivial learning
algorithm that outputs degree-2 PTFs and agnostically learns halfspaces (i.e.
degree-1 PTFs) under arbitrary distributions.
