Review for NeurIPS paper: Fast and Accurate k -means++ via Rejection Sampling

The paper presents a new algorithm for speeding up k-means algorithms with rigorous theoretical guarantees. It is quite surprising that they can improve the running time to \tilde{O}(nd n {1 \eps}) when even one round of k-means algorithm takes O(ndk) time. The main shortcoming is the performance gain is only visible for large k. However, I think the large k regime is very interesting and does appear in practice. The authors should add discussion about aspect ratio and the new experiments as pointed out by them in the rebuttal.