Theory Lunch Seminar - Rachel Zhang February 12, 2025 12:00pm — 1:00pm Location: In Person - Gates Hillman 8102 Speaker: RACHEL ZHANG, Ph.D. Student in Computer Science, Electrical Engineering and Computer Science Department, Massachusetts Institute of Technology https://www.rachelyunzhang.com/ We give the first explicit constructions of vertex expanders that pass the spectral barrier. Previously, the strongest known explicit vertex expanders were those given by d-regular Ramanujan graphs, whose spectral properties imply that every small set S of vertices has at least 0.5d|S| distinct neighbors. However, it is possible to construct Ramanujan graphs containing a small set S that has no more than 0.5d|S| distinct neighbors. In fact, no explicit construction was known to beat the 0.5 barrier. In this talk, I will discuss how we construct vertex expanders for which every small set expands by a factor of 0.6d. In fact, our construction satisfies an even stronger property: small sets actually have 0.6d|S| unique neighbors. Event Website: https://www.cs.cmu.edu/~theorylunch/ Add event to Google Add event to iCal
