Explicit Lossless Vertex Expanders
CSAIL, EECS
Add to Calendar
2025-09-23 16:15:00
2025-09-23 17:15:00
America/New_York
Explicit Lossless Vertex Expanders
We give the first explicit construction of lossless vertex expanders. These are d-regular graphs where every small set S of vertices has (1-eps)d|S| distinct neighbors. Previously, the strongest known explicit vertex expanders were those given by Ramanujan graphs, whose spectral properties imply that every small set S of vertices has 0.5d|S| distinct neighbors.Based on joint work with Jun-Ting Hsieh, Ting-Chun Lin, Alex Lubotzky, Sidhanth Mohanty, Ryan O'Donnell, and Assaf Reiner.
TBD