Computer Science/Discrete Mathematics Seminar I

High-dimensional expanders (HDX) are a generalization of expander graphs which have seen various applications in coding theory, PCPs, pseudorandomness, derandomization, approximate sampling, and beyond. One technique for proving a complex is an HDX is via trickle-down theorems, where expansion of certain small pieces implies expansion properties of the whole complex. In this talk we will discuss old and new trickle-down theorems for HDX, towards the application of approximate sampling. We will also show how these theorems derive from the theory of Lorentzian and log-concave polynomials, which has seen diverse applications in mathematics and TCS.

Joint work with Kasper Lindberg and Shayan Oveis Gharan.