  We consider the problem of robust polynomial regression, where one receives
samples $(x_i, y_i)$ that are usually within $\sigma$ of a polynomial $y =
p(x)$, but have a $\rho$ chance of being arbitrary adversarial outliers.
Previously, it was known how to efficiently estimate $p$ only when $\rho <
\frac{1}{\log d}$. We give an algorithm that works for the entire feasible
range of $\rho < 1/2$, while simultaneously improving other parameters of the
problem. We complement our algorithm, which gives a factor 2 approximation,
with impossibility results that show, for example, that a $1.09$ approximation
is impossible even with infinitely many samples.
