TCS+ Talk
Wednesday
November 6, 2019
10:00 AM
Explicit near-Ramanujan graphs of every degree
Speaker:
Ryan O'Donnell,
Carnegie Mellon University
Location:
Annenberg 322
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).
Series
TCS+ Talks
Contact: Bonnie Leung bjleung@caltech.edu