LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Explicit Lossless Vertex Expanders
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Explicit Lossless Vertex Expanders

77 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Rachel Zhang of MIT presents a construction of the first explicit lossless vertex expanders, graphs in which every small subset of vertices has nearly as many neighbors as sparsity theoretically allows. She contrasts this with the previous state of the art, Ramanujan graphs, whose spectral properties only guarantee small vertex sets about half the possible neighbor count. The talk centers on the role of high dimensional expanders as local-to-global amplifiers that let local expansion properties scale up to the lossless global bound. Delivered as part of the IAS Computer Science and Discrete Mathematics seminar at Simonyi Hall, the talk draws on joint work with Jun-Ting Hsieh, Ting-Chun Lin, Alex Lubotzky, Sidhanth Mohanty, Ryan O'Donnell, and Assaf Reiner. It is a research-level seminar aimed at those familiar with spectral graph theory and expander constructions, walking through the construction's key ideas and the obstacles it overcomes.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 17 m
Compared with MathematicsLonger than 69%
Source channelInstitute for Advanced Study (YouTube)