2021 Croucher Summer Course in Information Theory, The Chinese University of Hong Kong
High dimensional expanders are certain generalizations of expander graphs to hypergraphs. They recently appeared in many randomized algorithms and combinatorial constructions in theoretical computer science. A few random sampling algorithms can be seen as random walks on high dimensional expanders, such as nearly uniformly sampling of spanning trees by exchanging edges. High dimensional expanders also appear in locally testable codes and probabilistically checkable proofs. In this talk, I will give a gentle introduction to high dimensional expanders and survey their recent results.