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