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 $\sigma$ of a polynomial $y = p(x)$,buthavea$\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\mathrm{/}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.