Linear regression without correspondence
This article considers algorithmic and statistical aspects of linear regression when the correspondence between the covariates and the responses is unknown. First, a fully polynomial-time approximation scheme is given for the natural least squares optimization problem in any constant dimension. Next, in an average-case and noise-free setting where the responses exactly correspond to a linear function of i.i.d. draws from a standard multivariate normal distribution, an efficient algorithm based on lattice basis reduction is shown to exactly recover the unknown linear function in arbitrary dimension. Finally, lower bounds on the signal-to-noise ratio are established for approximate recovery of the unknown linear function by any estimator.
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. Finally, the authors prove the upper bound for the range of signal to noise ratio values for which the consistent parameter recovery is impossible.
In general, the proposed algorithms, though being not practical, help to make an important step in understanding of computational limits in the linear regression without correspondence. The statistical analysis is limited to lower bound while for the upper bound the authors refer to the paper by Pananjady et al. (2016). What puzzles me a lot is that provided lower bound for parameters recovery is d / log log n, while in Pananjady et al. (2016) the lower bound for permutation recovery is proved to be n^c for some c > 0. Moreover, in another paper Pananjady et al. (2017) the constant upper bound on prediction risk is proved. While all these results consider the different quantities to be analyzed, it is seems that the fundamental statistical limits in this problem is far from being well understood.
To sum up, I think that the paper presents a strong effort in the interesting research direction and the results are sound. However, I believe that the main impact of the paper is on computational side, while some additional statistical analysis is highly desired for this problem. Also I believe that such type of paper, which includes involved theoretical analysis as well as algorithms which are more technical than intuitive, is much more suitable for full journal publication than for short conference paper.