BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

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


For every constant d >= 3 and epsilon > 0, 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).

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International