Caltech Logo

TCS+ Talk

Wednesday, November 6, 2019
10:00am to 11:00am
Add to Cal
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 bjleung@caltech.edu.