TCS+ Talk
Annenberg 322
Explicit near-Ramanujan graphs of every degree
Ryan O'Donnell,
Professor,
Carnegie Mellon University,
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).
For more information, please contact Bonnie Leung by email at [email protected].
Event Series
TCS+ Talks