Reviews: List-decodable Linear Regression

This paper studies the challenging problem of doing linear regression in the setting where an overwhelming fraction (1-alpha) of the examples are adversarially corrupted. It extends recent work on using the Sum-of-Squares hierarchy for robust estimation. The main contribution is realizing that anti-concentration (and being able to certify anti-concentration) is the key. The algorithm has a high running time (d (1/alpha 8)) but given the challenging nature of the problem, the reviewers felt that the fact that the problem can be solved in polynomial time for any fixed alpha 0 is surprising and an important contribution.