  While effective in practice, iterative methods for solving large systems of
linear equations can be significantly affected by problem-dependent condition
number quantities. This makes characterizing their time complexity challenging,
particularly when we wish to make comparisons between deterministic and
stochastic methods, that may or may not rely on preconditioning and/or fast
matrix multiplication. In this work, we consider a fine-grained notion of
complexity for iterative linear solvers which we call the spectral tail
condition number, $\kappa_\ell$, defined as the ratio between the $\ell$th
largest and the smallest singular value of the matrix representing the system.
  Concretely, we prove the following main algorithmic result: Given an $n\times
n$ matrix $A$ and a vector $b$, we can find $\tilde{x}$ such that
$\|A\tilde{x}-b\|\leq\epsilon\|b\|$ in time $\tilde{O}(\kappa_\ell\cdot n^2\log
1/\epsilon)$ for any $\ell = O(n^{\frac1{\omega-1}})=O(n^{0.729})$, where
$\omega \approx 2.372$ is the current fast matrix multiplication exponent. This
guarantee is achieved by Sketch-and-Project with Nesterov's acceleration. Some
of the implications of our result, and of the use of $\kappa_\ell$, include
direct improvement over a fine-grained analysis of the Conjugate Gradient
method, suggesting a stronger separation between deterministic and stochastic
iterative solvers; and relating the complexity of iterative solvers to the
ongoing algorithmic advances in fast matrix multiplication, since the bound on
$\ell$ improves with $\omega$.
  Our main technical contributions are new sharp characterizations for the
first and second moments of the random projection matrix that commonly arises
in sketching algorithms, building on a combination of techniques from
combinatorial sampling via determinantal point processes and Gaussian
universality results from random matrix theory.
