  We bound the second eigenvalue of random $d$-regular graphs, for a wide range
of degrees $d$, using a novel approach based on Fourier analysis. Let $G_{n,
d}$ be a uniform random $d$-regular graph on $n$ vertices, and let $\lambda
(G_{n, d})$ be its second largest eigenvalue by absolute value. For some
constant $c > 0$ and any degree $d$ with $\log^{10} n \ll d \leq c n$, we show
that $\lambda (G_{n, d}) = (2 + o(1)) \sqrt{d (n - d) / n}$ asymptotically
almost surely. Combined with earlier results that cover the case of sparse
random graphs, this fully determines the asymptotic value of $\lambda (G_{n,
d})$ for all $d \leq c n$. To achieve this, we introduce new methods that use
mechanisms from discrete Fourier analysis, and combine them with existing tools
and estimates on $d$-regular random graphs - especially those of Liebenau and
Wormald.
