2021 MPS Conference on HighDimensional Expanders
Organizer:
Alex Lubotzky, Hebrew University
The theory of expander graphs has seen increased interaction between mathematics and computer science in the last 50 years with a high dimensional theory emerging in recent years that has shown unexpected applications in both areas.
In October 2019 the Simons Foundation held a firstofitskind meeting on high dimensional expanders, which promoted more interest and interaction around this subject. This current workshop will again bring mathematicians and computer scientists, with a wide range of interests, to report and hear about the developments over the last two years and to discuss future directions of research.

Meeting Report
The second Simons workshop on highdimensional expanders (HDX) took place at the Simons Foundation in New York October 27–29, 2021. This was, in a way, a followup to the first one held at the same place in October 2019.
The workshop was a great success. Besides the fact that the inperson participants were so happy to be once again attending an inperson meeting, the workshop proved how successful the first one was in creating a community of mathematicians and computer scientists from diverse areas who do not usually meet (in person and/or virtually) at ordinary conferences. The talks, some of which are described below, illustrated how the previous workshop contributed to the flow of ideas. While a few years ago, highdimensional expanders and Ramanujan complexes were subjects of research for only a few mathematicians, it has clearly become a topic which is of interest to a good number of computer scientists.
The public talk, given on Wednesday evening, October 27, 2021, by Professor Irit Dinur from the Weizmann Institute, illustrated exactly these points. She spoke on “Highdimensional expanders in computer science” and surveyed a few important applications, some of which came out in more detail in some of the other talks.
One of the outstanding achievements of the last few years is the case of HDX as a tool to analyze various Markov chains. This has led to the solution of a few outstanding problems about matroids in a way which was completely unexpected. This method continues to bear fruit, as was illustrated by the talks of Nima Anari, Madhur Tulsiani and Kuikui Liu.
Another major recent achievement of HDX is the construction of locally testable good codes — a longstanding problem in the area of errorcorrecting codes. This was described in Alex Lubotzky’s lecture. This topic builds on the intimate connection between HDX and the area of property testing and PCP, a central topic in the modern theory of computer science. The lecture of Henry Yuen took the subject further to quantum computations, as he presented “Noncommutative property testing” with some results and a number of directions for future research. 
Agenda
Wednesday, October 27
9:30 AM Henry Yuen  Noncommutative Property Testing 11:00 AM Matthew Kahle  Randomness and HighDimensional Expansion 1:30 PM Caroline Klivans  HighDimensional Simplicial Trees 3:00 PM Alex Lubotzky  The C^3 Problem: Locally Testable Codes with Constant Rate and Constant Distance 5:00 PM Irit Dinur (Public Lecture)  High Dimensional Expanders in Theoretical Computer Science Thursday, October 28
9:30 AM Madhur Tulsiani  A WeakRegularity Lemma for HighDimensional Expanders and Algorithmic Applications 11:00 AM Izhar Oppenheim  Random Walks on Partite Complexes 1:00 PM Michael Chapman  Cutoff: New Results and New Methods 2:30 PM Kuikui Liu  Spectral Independence: A New Tool to Analyze Markov Chains 4:00 PM Nima Anari  Entropic Independence in HighDimensional Expanders Friday, October 29
9:30 AM Louis Golowich  Improved ProductBased HighDimensional Expanders 11:00 AM Gil Kalai  The Cascade Conjecture, Topology, and the FourColor Theorem 1:00 PM Nati Linial  Geodesic Geometry on Graphs 
Abstracts and Slides
Nima Anari
Stanford UniversityEntropic Independence in HighDimensional Expanders
Anari will introduce a notion for weighted simplicial complexes called ‘entropic independence.’ This notion is motivated by the desire to obtain tight mixing time bounds for natural random walks associated with a multitude of discrete distributions. As is widely known in Markov chain analysis, spectral analysis is often lossy (by polynomial factors) when the state space is exponentially large. Instead, modified logSobolev inequalities, which characterize the rate of entropy decay in a random walk, are a powerful family of functional inequalities that often yield the correct mixing time. Anari shows how to obtain entropic independence and, as a consequence, tight MLSI and tight mixing times for a range of natural distributions; examples include monomers in monomerdimer systems, the hightemperature Ising model, the hightemperature hardcore model and (nonsymmetric) determinantal point processes.
Anari’s key technical contribution is a new connection between the geometry of the generating polynomial of distributions and entropy decay. He shows that entropic independence and MLSI can be obtained with no extra effort from more manageable corresponding spectral notions, specifically local spectral expansion and as long as the distribution using external fields is allowed to be reweighed. Timepermitting, Anari will briefly mention two additional algorithmic applications of entropic independence: faster sampling via domainsparsification of distributions and parallel algorithms for sampling determinantbased distributions.
Based on joint works with Callum Burgess, Michał Dereziński, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, Kevin Tian, ThuyDuong Vuong and Elizabeth Yang.
Michael Chapman
Hebrew UniversityCutoff: New Results and New Methods.
In recent years, random walks on simplicial complexes proved extremely useful. They were used, for example, to uniformly sample matroid bases and to define highdimensional analogues of expansion. Meanwhile, the cutoff phenomenon for random walks received lots of attention as well. A random walk exhibits the cutoff phenomenon if the transition from being far from mixed to being very mixed happens (relatively) abruptly.
In this talk, Chapman plans to survey cutoff results and proof methods for graphs and for quotients of Bruhat–Tits buildings; discuss generalizations of a recent entropic approach due to Ozawa; apply these generalizations to Ramanujan complexes that were not known previously to exhibit cutoff; and deduce cutoff results on Cayley graphs arising from high dimensional theory.
This talk is based on joint works with Ori Parzanchevski and Yuval Peled.
Louis Golowich
Harvard UniversityImproved ProductBased HighDimensional Expanders
Highdimensional expanders generalize the notion of expander graphs to higherdimensional simplicial complexes. In contrast to expander graphs, only a handful of highdimensional expander constructions have been proposed, and no elementary combinatorial construction with nearoptimal expansion is known. In this talk, Golowich will introduce an improved combinatorial highdimensional expander construction by modifying a previous construction of Liu, Mohanty and Yang (ITCS 2020), which is based on a highdimensional variant of a tensor product. The construction achieves a spectral gap of \(\Omega(1/k^2)\) for random walks on the \(k\)dimensional faces, which is only quadratically worse than the optimal bound of \(\Theta(1/k)\). Previous combinatorial constructions, including that of Liu, Mohanty and Yang, only achieved a spectral gap that is exponentially small in \(k\). Golowich will also present reasoning that suggests our construction is optimal among similar productbased constructions.
Matthew Kahle
Ohio State UniversityRandomness and HighDimensional Expansion
Kahle will survey some expanderrelated results around topology of random simplicial complexes and geometry of random groups. One of the main goals of the talk will be to advertise several attractive open problems in the area.
Gil Kalai
Hebrew University of JerusalemThe Cascade Conjecture, Topology, and the FourColor Theorem
Hellytype theorems and problems form a nice area of discrete geometry and they have nice connections with HD expanders and HD combinatorics. Kalai will start with the notable theorems of Radon and Tverberg and mention the following conjectural extension.
For a set X of points x(1), x(2),…,x(n) in some real vector space V we denote by T(X,r) the set of points in X that belong to the convex hulls of r pairwise disjoint subsets of X. We let t(X,r)=1+dim (T(X,r)).
Radon’s theorem asserts that
If t(X,1)< X then t(X, 2) >0.
The first open case of the cascade conjecture asserts that
If t(X,1)+t(X,2) < X then t(X,3) >0.
In the lecture, Kalai will discuss connections with topology and with graph coloring and how strong topological forms of the cascade conjecture that may imply the four color theorem.
Caroline Klivans
Brown UniversityHighDimensional Simplicial Trees
Similar in spirit to the notion of coboundary expansion, simplicial trees were developed by regarding a graph as a onedimensional complex and generalizing appropriately. This point of view is consistent with the matroidtheoretic approach to graphs and connections to combinatorial Laplacians. In this talk, Klivans will give an overview of the theory of simplicial spanning trees and discuss places where it connects with ideas of highdimensional expansion.
Nati Linial
Hebrew UniversityGeodesic Geometry on Graphs
There are many ways to view graphs from a geometric perspective, and these different views are extremely fruitful. One of the most obvious ways comes from the fact that shortestpath distances make every graph into a metric space. By assigning weights (or lengths) to the edges of a graph G, a whole family of metrics is generated. However, as Linial will show in these works, a much richer class of geometric structures can be associated with graphs. A path system P in G is comprised of one chosen path between every pair of vertices in G. We say that P is consistent if it is closed undertaking subpaths. Linial will first observe that there are examples of consistent path systems that are nonmetric. That is, P cannot be realized by assigning lengths to G’s edges. Linial will prove that the vast majority of all graphs are nonmetrizable in the sense that G has a consistent nonmetric path system. Surprisingly, Linial will also prove that it is possible to decide in polynomial time whether a given graph has a consistent path system.
This work is based on joint work with Daniel Cizma.
Kuikui Liu
Washington UniversitySpectral Independence: A New Tool to Analyze Markov Chains
Markov chain Monte Carlo is a widely used class of algorithms for sampling from highdimensional probability distributions, both in theory and in practice. While simple to implement, analyzing the rate of convergence to stationarity (i.e., the ‘mixing time’) remains a challenging problem in many settings. Liu will introduce a new technique to bound mixing times called ‘spectral independence,’ which says that certain pairwise correlation matrices all have bounded spectral norm. This surprisingly powerful technique originates in the emerging study of highdimensional expanders and has allowed us to ‘unify’ nearly all existing approaches to approximate counting and sampling by building new connections with other areas, including statistical physics, geometry of polynomials, functional analysis and more. Through these connections, several longstanding open problems have recently been answered, including counting bases of matroids and optimal mixing of the Glauber dynamics/Gibbs sampler up to the algorithmic phase transition threshold.
Based on several joint works with Dorna Abdolazimi, Nima Anari, Zongchen Chen, Shayan Oveis Gharan, Eric Vigoda and Cynthia Vinzant.
Alex Lubotzky
Institute for Advanced StudyThe C^3 Problem: Locally Testable Codes with Constant Rate and Constant Distance
An errorcorrecting code (LTC) is locally testable if there is a random tester that reads only a constant number of bits of a given word and decides whether the word is in the code or at least close to it. A longstanding problem asks if there exists such a code that also satisfies the golden standards of coding theory: constant rate and constant distance. Random codes are not LTC!
Lubotzky will construct such codes based on what is called (Ramanujan) left/right Cayley square complexes. These twodimensional objects seem to be of independent interest.
This is based on joint work with I. Dinur, S.Evra, R. Livne and S. Mozes.
Izhar Oppenheim
Ben Gurion UniversityRandom Walks on Partite Complexes
Partite simplicial complexes are the natural generalization of bipartite graphs: an ndimensional simplicial complex is called ‘partite’ if its vertices can be colored with n+1 colors such that each ndimensional simplex has vertices of all colors.
In this talk, Oppenheim will explore the spectra of random walks on partite complexes and show that in the partite case, there are local to global results that take into account the interplay of different links (.i.e., that links that are excellent expanders can compensate for links that are not so good expanders).
This talk is based on ongoing work with Zohar GrinbaumReizis.
Madhur Tulsiani
Toyota Technological Institute at Chicago, University of ChicagoA WeakRegularity Lemma for HighDimensional Expanders and Algorithmic Applications
Tulsiani will discuss an analogue of the weakregularity lemma of Frieze and Kannan, for highdimensional expanders and for a more general class of hypergraphs which we refer to as ‘splitable.’ He will also present an algorithmic version of the lemma and its applications to constraint satisfaction, and the decoding of errorcorrecting codes.
This talks is based on joint work with Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana and Shashank Srivastava.
Henry Yuen
Columbia UniversityNoncommutative Property Testing
In this talk, Yuen will discuss property testing in the noncommutative context. Instead of testing properties of deterministic blackbox functions (the standard setting of classical property testing), he considers testing probabilistic functions whose evaluations are given by measurements on a quantum state. Yuen will discuss how the core components of MIP* = RE, such as the quantum analysis of the lowdegree test, can be interpreted as results in noncommutative property testing, and he will also describe some open questions.
This is based on joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick and John Wright.

Simons Foundation Lecture: Wednesday, October 27
Irit Dinur
Institute for Advanced Study & Weizmann InstituteHigh Dimensional Expanders in Theoretical Computer Science
Expander graphs have been useful in computer science with versatile applications, including coding theory, networking, computational complexity and geometry.
Highdimensional expanders are a generalization that has been studied in recent years and hold promise for some new and exciting applications in theoretical computer science.
In the talk, Irit Dinur will survey some fascinating local to global properties of highdimensional expanders. Can these be harnessed for further computer science applications? She will describe the stateoftheart and interesting future directions.
To attend this inperson event, you will need to register in advance and provide:
 Acceptable proof of vaccination (vaccine card/certificate, a copy or photo of vaccine card/certificate or electronic NYS Excelsior Pass or NJ Docket Pass)
 Photo ID
 Eventbrite ticket confirmation email with QR code
 Simons Foundation Health Screening Questionnaire approval email
Entrance will not be granted without this documentation.
Onsite registration will not be permitted. Walkin entry will be denied.