No abstract available.
Thursday, July 11th, 2019
9:30 am–11:00 am
Speaker: Prahladh Harsha (Tata Institute of Fundamental Research)
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?
11:30 am–12:30 pm
Speaker: Irit Dinur (Weizmann Institute of Science)
We will study simplicial complexes, their links, and the definition of link expansion. We will focus on the local to global nature of these objects: local information on the links is powerful enough for deducing global structure. We will describe some examples of this phenomenon relating to list decoding, agreement testing.
3:00 pm–4:00 pm
Speaker: Yotam Dikstein (Weizmann Institute of Science)
In this lecture we will prove Oppenheim's trickling-down theorem, which says that local spectral expansion in the links implies global expansion of the underlying graph. This is a demonstration of Garland's local to global method.
Friday, July 12th, 2019
9:00 am–11:00 am
Speaker: Prahladh Harsha (Tata Institute of Fundamental Research)
Expander graphs have myriad applications in coding theory giving rise to error-correcting codes with constant relative distance and rate equipped with extremely efficient encoding, unique-decoding and list-decoding procedures. Over the last decade and a half, local versions of these procedures have been extensively studied in theoretical computer science. For instance, Locally testable codes are error-correcting codes that admit super-efficient checking procedures.
We will see why expander based codes are NOT locally testable. This is in contrast to typical "good" error correcting properties which follow from expansion. We will then see that despite this disconnect between expansion and testability, all known construction of locally testable codes follow from the high-dimensional expansion property of a related complex leaving open an intriguing connection between local-testability and high-dimension expanders.
11:30 am–12:30 pm
Speaker: Yotam Dikstein (Weizmann Institute of Science)
In this talk we give an alternative characterization for high dimensional expanders through high dimensional random walks. We will describe the Up and Down operators, and show a spectral condition on them that is equivalent to link expansion. We will discuss an approximate Fourier decomposition for functions on high dimensional expanders.
2:00 pm–3:00 pm
Speaker: Uli Wagner (IST Austria)
Following the work of Linial—Meshulam, Gromov, and others, we will discuss higher-dimensional expansion from the viewpoint of isoperimetric inequalities for coboundary operators (signed incidence matrices between (k-1)-dimensional and k-dimensional faces of a complex) in cohomology.
The resulting notion of expansion depends on the choice of coefficients as well as on the choice of a norm on the cochains.
For instance, for real coefficients and the L_2-norm, we recover the spectral definition of higher-dimensional expansion in terms of high-dimensional Laplacians. For Z/2-coefficients and the Hamming norm, we get combinatorial coboundary expansion.
We will also discuss applications (insofar as time permits), such as Gromov’s topological overlap theorem.
3:30 pm–5:00 pm
Speaker: Mary Wootters (Stanford University)
In this talk I will survey some open questions in error-correcting codes (which hopefully high-dimensional expansion can help solve!) as well as the state-of-the-art on these questions. Topics will include traditional unique decoding, list-decoding, and locality.
