Explicit near-Ramanujan graphs of every degree

November 6, 2019 (GHC 6115)

For every constant $d>3$ and $\epsilon>0$, we give a deterministic poly(n)-time algorithm that outputs a d-regular graph on $\Theta(n)$ vertices that is $\epsilon$-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by $2\sqrt{d-1}+\epsilon$ (excluding the single trivial eigenvalue of d).

Joint work with Sidhanth Mohanty and Ryan O'Donnell.