and exploration, and complements a well-known spectral comparison for regular expanders due to @alon2007non, as well as a recent result by @cooper2014vacant on the cover time of random regular graphs. For other ways of speeding up random walks, see @cooper2011random.

\[thm:lubetzky\] Let $G\sim {\ensuremath{\mathcal{G}}}(n,d)$ be a random regular graph with $d\geq 3$ fixed. Then, for all $0<\varepsilon<1$, **whp**,

1.  the mixing time of the <span style="font-variant:small-caps;">nbrw</span> satisfies $$t_\textsc{mix}^{(n)}(\varepsilon)=\log_{d-1}(dn) +{\ensuremath{\mathcal{O}}}_{\ensuremath{\mathbb{P}}}(1).$$

2.  the mixing time of the <span style="font-variant:small-caps;">srw</span> satisfies $$t_\textsc{mix}^{(n)}(\varepsilon)=\frac{d}{(d-2)}\log_{d-1} n +\left(\Lambda+o(1)\right)\overline{\Phi}^{-1}(\varepsilon)\sqrt{\log_{d-1}n}\, ,$$ where $\Lambda=\frac{2\sqrt{d(d-1)}}{(d-2)^{3/2}}$ and $\overline{\Phi}=1-\Phi$, with $\Phi$ the c.d.f. of the standard normal distribution.

In the non-regular case however, the tight correspondence between the <span style="font-variant:small-caps;">srw</span> and the <span style="font-variant:small-caps;">nbrw</span> breaks down, and there seems to be no direct way of transferring our main result to the <span style="font-variant:small-caps;">srw</span>. We note that the latter should exhibit cutoff since the product condition holds, as can be seen from the fact that the *conductance* of sparse random graphs with a given degree sequence remains bounded away from $0$ (see @abdullah2012cover). Confirming this constitutes a challenging open problem. In particular, it would be interesting to see whether the <span style="font-variant:small-caps;">srw</span> still mixes faster than the <span style="font-variant:small-caps;">nbrw</span>. To the best of our 