Lunch will be served at 11:45 AM.
Expanders are well-connected graphs that have been extensively studied and have numerous applications in computer science, including error correcting codes, pseudo randomness, and hardness of approximation, among others.
High-dimensional expanders (HDXs) generalize the notion of expansion to hypergraphs. Their importance is continuously growing due to their roles in breakthroughs in locally testable codes, quantum codes, and the matroid basis sampling problem. However, our understanding of HDX constructions remains limited compared to that of expanders. While numerous algebraic, combinatorial, and randomized constructions are known for expanders, only a few algebraic constructions are known for HDXs. These constructions rely on deep number theory results and are difficult to adapt for new applications. A major open question is: Can we find more elementary and/or flexible constructions of HDXs?
In this talk, we will discuss a series of works that introduce new combinatorial, randomized, and algebraic constructions of HDXs, providing partial answers to this question. Additionally, we will explore some applications of HDXs to coding theory and hardness of approximation.
This talk is based on joint work with Yotam Dikstein, Irit Dinur, Tom Gur, Noam Lifshitz, Sidhanth Mohanty, Tselil Schramm, Avi Wigderson, Elizabeth Yang, and Rachel Zhang.
Siqi Liu is a theoretical computer scientist and a postdoctoral researcher at the Institute for Advanced Study. Previously, she was a postdoc at Rutgers University. Before that, she earned her Ph.D. from UC Berkeley, where she was advised by Alessandro Chiesa. Her research focuses on constructing and analyzing combinatorial structures and applying them to computational complexity theory. More specifically, she studies high-dimensional expanders and their connections to error-correcting codes and proof systems.