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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International