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/ Explicit Vertex Expanders Beyond the Spectral Barrier 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
