Ryan O'Donnell: Explicit near-Ramanujan graphs of every degree

Abstract:

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

 

Joint work with Sidhanth Mohanty (Berkeley) and Pedro Paredes (CMU).