Theory Lunch Seminar/Computer Science Speaking Skills Talk
— 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.
Event Website:
http://www.cs.cmu.edu/~theorylunch/abstractsHTML/20191106.html
For More Information:
deb@cs.cmu.edu