Robust polynomial regression up to the information theoretic limit

Daniel Kane, Sushrut Karmalkar, Eric Price

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 be…