Theory Lunch Seminar/Computer Science Speaking Skills Talk

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.

Event Website:

http://www.cs.cmu.edu/~theorylunch/abstractsHTML/20191106.html

For More Information, Contact:

Keywords:

Speaking Skills