Robust polynomial regression up to the information theoretic limit

We consider the problem of robust polynomial regression, where one receives samples $(x_i, y_i)$ that are usually within $σ$ of a polynomial $y = p(x)$, but have a $ρ$ chance of being arbitrary adversarial outliers. Previously, it was known how to efficiently estimate $p$ only when ρ< \frac{1}{\log d}. We give an algorithm that works for the entire feasible range of ρ< 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.