We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Specifically, we are given a set T of labeled examples (x, y) ∈ℝ^d ×ℝ and a parameter 0< α <1/2 such that an α-fraction of the points in T are i.i.d. samples from a linear regression model with Gaussian covariates, and the remaining (1-α)-fraction of the points are drawn from an arbitrary noise distribution. The goal is to output a small list of hypothesis vectors such that…