Abstract
Expander graphs, over the last few decades, have played a pervasive role in almost all areas of theoretical computer science. 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 coding theory.
In this introductory talk, we will begin by looking at some classical objects in theoretical computer science (especially coding theory) such as PCPs, agreement tests, low-degree testing and see how implicit in these objects is a high-dimensional expanding phenomena. We will try to abstract this phenomena which will eventually lead to the following questions?
(a) What is a high-dimensional expander (HDX)?
(b) What is a sparse HDX?
(c) Are they useful?