Reviews: Linear regression without correspondence

The article "Linear regression without correspondence" considers the problem of estimation in linear regression model in specific situation where the correspondence between the covariates and the responses is unknown. The authors propose the fully polynomial algorithms for the solution of least squares problem and also study the statistical lower bounds. The main emphasis of the article is on the construction of fully polynomial algorithms for least squares problem in noisy and noiseless case, while previously only the algorithms with exponential complexity were known for the cases with dimension d 1. For the noisy case the authors propose the algorithm which gives a solution of least squares problem with any prespecified accuracy. For noiseless case another algorithm is proposed, which gives the exact solution of the least squares problem.