Expander graphs, over the last few decades, have played a pervasive role in almost all areas of theoretical computer science. Loosely speaking, an expander graph is an extremely well-connected graph despite being sparse. Recently, various high-dimensional analogues of these objects have been studied in mathematics and even more recently, there have been some surprising applications in computer science, especially in the area of property testing, coding theory and approximate counting. In this talk, I'll give a high-level introduction to these high-dimensional expanders (HDXs). In particular, we will view them through the perspective of random walks on graphs. Time permitting, we will then some see applications of these HDXs towards matroid counting and coding theory.
Zoom link: https://icts-res-in.zoom.us/j/88259157313?pwd=MGaYEqfNziEMRJTcFbNb8XrSHeBeau.1
Meeting ID: 882 5915 7313
Passcode: 216072