Summary
The authors give a leverage score approximation algorithm that runs in nearly linear time for dense matrices. Specifically, to find leverage scores for a matrix $A \in \mathbb{R}^{n \times d}$, they give an algorithm based on fast matrix multiplication that runs in time $\widetilde{O}(nd)$. This, combined with a "lazy update" trick, yield a new fast algorithm to approximate the John ellipsoid for a symmetric convex polyhedron represented as the set $\{x \in \mathbb{R}^d \colon \| Ax \|_{\infty} \le 1\}$. The same ideas also transfer to a $\sim \log n$-pass streaming setting to find the John ellipsoid, yielding a new low space complexity algorithm for finding the John ellipsoid that has a stronger approximation guarantee than existing one-pass solutions.
Strengths
The leverage score approximation algorithm the authors give may yield faster algorithms for a class of optimization algorithms that use leverage score computations as a primitive (one example I can think of offhand is the work [JLS21]). In particular, this should imply a $\widetilde{O}(nd)$ time algorithm for finding weights $w$ such that $2w_i \ge \tau_i(W^{1/2-1/p}A)$ for $p \ge 2$ (which is a one-sided Lewis weight approximation that suffices for a large number of applications, including $\ell_p$ row sampling and $\ell_p$ regression for $p \ge 2$). The insight is pretty simple and cleanly presented, which I view as a positive. I suspect a similar result is true (along with a corresponding low-space streaming algorithm) for for $p < 2$ by applying this to the natural contraction mapping that computes the weights.
[JLS21] Improved Iteration Complexities for Overconstrained p-Norm Regression (https://arxiv.org/abs/2111.01848)
Weaknesses
I wish more applications had been discussed. Leverage scores are a pretty fundamental primitive that get used in a lot of problems in optimization and numerical linear algebra, and it would have been nice to write down concrete runtime improvements (if any) that emerge from Theorem 1.3. I alluded to some in the previous section, and I would be happy to raise my score if the authors either confirm the above or present a few more settings in which concrete runtime improvements are realized. Alternately, I'd also raise the score if the authors discussed a bit about the barriers behind extending their approach to these settings.
Mild issues:
I think there are typos in Algorithm 1 and a suboptimal runtime guarantee. I think Line 8 should read:
$w_{i}^{(t)} = \prod_{t'=1}^{t} a_i^{\top}(A^{\top}W^{(t')}A)^{-1}a_i$. In particular, as written, Line 8 multiplies across the first $t$ rows for a fixed quadratic, whereas the loop counter should be running over the quadratics instead.
I also think Line 9 should read:
$Q^{(t)} \gets Q^{(t)} + w_i^{(t)}a_ia_i^{\top}$ (I think you need an outer product and not an inner product, same thing for Line 6)
I think you also need an averaging step at the very end, as the [CCLY19] algorithm returns the weights $w = 1/T \cdot \sum_{t'=1}^{T} w_{t'}$.
Finally, I think this algorithm actually can be implemented in $d^2T \le d^{\omega}T$ time per row. This is because of associativity:
$\prod_{t=1}^t a_i^{\top}Q_{t}^{-1}a_i = \prod_{t=1}^t a_i^{\top}(Q_{t}^{-1}a_i)$
Now, $(Q_{t}^{-1}a_i)$ is a vector that can be formed in time $d^2$ via naive multiplications, and then $a_i^{\top}(Q_{t}^{-1}a_i)$ is a dot product that can be found in $d$ time. We do this $t$ times for each term in the product and then multiply them all together for a total time of $d^2t$ for step $t$.
Questions
See all of the above.