Wednesday, November 6, 2019 - 12:00pm to 1:00pm
Location:6115 Gates Hillman Centers
Speaker:PEDRO PAREDES, Ph.D. Student http://www.cs.cmu.edu/~preisben/
Explicit near-Ramanujan graphs of every degree
For every constant d>3 and ϵ>0, we give a deterministic poly(n)-time algorithm that outputs a d-regular graph on Θ(n) vertices that is ϵ-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by 2√d−1+ϵ (excluding the single trivial eigenvalue of d).
Joint work with Sidhanth Mohanty and Ryan O'Donnell.
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.