The paper has solid theoretical contributions and is written well. The following are some points that came up during discussions: 1. An additional reviewer pointed out that the proposed adaptive sketch appears to be analogue of leverage score sampling with iid Gaussian sketch - the idea is similar to the intuitions the authors provide in the rebuttal about finding a good approximation of AA^T with AP_SA^T. Although this connection at this point is not rigorously worked out, it would be very useful if the authors can add discussions/connections about this in their revision. The connection could also explain the similarity of the leverage score rates in Table 1. 2. Although the paper was primarily evaluated on theoretical grounds, initial reviews had raised some concerns on the empirical evaluation. The author response provides more elaborate empirical results. Please include these results and discussion in the final version. 3. The following missing reference on sketching for solving system of equations is relevant: https://arxiv.org/pdf/1506.03296.pdf