Embedded Files
Update: Video recordings of the talks available below!
Organizers: Mitali Bafna, Yotam Dikstein, Max Hopkins, Dor Minzer.
High-Dimensional Expanders (HDX in short), an emerging field in discrete mathematics and theoretical computer science (TCS in short). The field of HDX can be viewed as the higher dimensional analog of the successful theory of expander graphs, which have been instrumental in TCS since the 70’s, with a myriad of applications in pseudorandomness, PCPs, derandomization, error correcting codes, algorithms, circuit complexity and more.
In contrast to standard expanders, which by now are well understood and can be constructed in many ways, much remains to be explored about HDX. Indeed, the only known constructions of constant degree HDX (which are the analogs of constant degree expander graphs) are group theoretic. Only recently was their full power utilized in advances in fields such as error correcting codes, quantum error correcting codes, explicit integrality gap constructions, PCPs and more.
In this workshop, we plan to give a gentle overview to the field of HDX, explaining the basics, constructions and some applications. We will try to give the high level intuition of what makes HDX useful in each one of the applications, in the hope that the attendees may develop a hunch to whether HDX may be useful for them in their future research.
Program and Abstracts
First Session - June 23rd, 8:45-10:45, Lounge Jupiter
HDX and the 'Local-to-Global' Method
Speaker: Max Hopkins
Abstract: What do quantum error correction, Markov chains, and PCPs have in common? Despite their separate origins, these areas have experienced a shared Renaissance in recent years driven by a somewhat surprising player: high dimensional expanders (HDX) and a set of corresponding techniques called the 'local-to-global' method.
In this talk, we give a gentle introduction to spectral HDX and the local to global method. We will focus in particular on the core connection between (high dimensional) expanders and random walks, and see how the local-to-global method allows us to control the global behavior of complex high dimensional walks via their elementary local components.
Approximate Sampling via HDX, with connections to Log-concave Polynomials
Speaker: Jonathan Leake
Abstract: In this talk, I will discuss how high-dimensional expanders can be used to prove approximate sampling results in various contexts. This includes sampling results for independent sets, matroids/spanning trees, matchings, spin systems, and beyond. Along with demonstrating this in a few concrete examples, I will discuss a number of techniques and theorems which lead to complexity bounds for these algorithms. Finally, I will describe how a particular technique involving log-concave polynomials can be used to obtain a new trickle-down theorem for simplicial complexes associated to distributive, modular, and matroid lattices. Interestingly, this technique leads not only to sampling results, but also to non-trivial log-concavity inequalities.
Talk slides
Talk recording: link
Second Session - June 24th, 8:45-10:45, Congress Hall Sun I + II
Explicit Lossless Vertex Expanders
Speaker: Rachel Zhang
Abstract: In this talk, I will describe our construction of the first explicit lossless vertex expanders. These are d-regular graphs where every small set S of vertices has (1-eps)d|S| distinct neighbors. Previously, the strongest known explicit vertex expanders were those given by Ramanujan graphs, whose spectral properties imply that every small set S of vertices has 0.5d|S| distinct neighbors. A key insight in our work is the crucial role played by high-dimensional expansion in constructing good vertex expanders.
Talk slides
Talk recording: link
Bounded-Degree HDX Constructions (for the Working Computer Scientist)
Speaker: Yotam Dikstein
Abstract: The goal of this talk is to survey two of the main constructions of bounded-degree high-dimensional expanders: quotients of Bruhat-Tits buildings and coset complexes. I will describe how these complexes are constructed at a very high level. Additionally, I will discuss some of their local and global properties. Even though these constructions are algebraic in nature, I will only assume very basic knowledge in group theory.
Further reading:
An elementary note of Kaufman and Oppenheim's coset complexes (by Prahladh Harsha, Ramprasad Saptharishi)
An exposition on Quotients of the Bruhat-Tits buildings (by Ramprasad Saptharishi)
Talk slides
Talk recording: link
Third Session - June 26th, 8:45-10:45, Congress Hall Sun I + II
Coboundary Expansion and Applications to Property Testing
Speaker: Mitali Bafna
Abstract: In this talk, I will introduce coboundary expansion, a notion of high-dimensional expansion that matches spectral expansion on graphs but diverges from it in higher dimensions. After formalizing coboundary expansion, I will sketch its role in recent results on agreement testing, a key ingredient in building PCPs.
Talk slides
Talk recording: link
The impact of HDX on quantum coding theory
Speaker: Chinmay Nirkhe
Abstract: In 2021, there were two major breakthroughs in coding theory. First, was constructions of locally testable codes that are c^3 -- i.e. codes of constant locality, distance, and soundness were first achieved in 2021 by Dinur, Evra, Livne, Lubotzky, and Mozes and independently by Panteleev and Kalachev. Second, quantum error-correcting codes of constant locality and distance. The constructions of these codes were then used to prove complexity lower bounds for quantum codes as well as explicit lower-bounds for Sum-of-Squares.
In this workshop lecture, I'll help explain the connections between these topics and notions of high dimensional expansion and boundary/co-boundary expansion. In particular, I'll emphasize the delicate nature of expansion required to achieve the quantum coding results.
Talk recording: link
Page updated
Google Sites
Report abuse