2021 MPS Conference on High-Dimensional Expanders

The second Simons workshop on high-dimensional expanders (HDX) took place at the Simons Foundation in New York October 27–29, 2021. This was, in a way, a follow-up to the first one held at the same place in October 2019.
The workshop was a great success. Besides the fact that the in-person participants were so happy to be once again attending an in-person 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, high-dimensional 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 “High-dimensional 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 long-standing problem in the area of error-correcting 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 “Non-commutative property testing” with some results and a number of directions for future research.

Nima Anari
Stanford University

Entropic Independence in High-Dimensional Expanders

View Slides (PDF)

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 log-Sobolev 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 monomer-dimer systems, the high-temperature Ising model, the high-temperature hardcore model and (non-symmetric) 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. Time-permitting, Anari will briefly mention two additional algorithmic applications of entropic independence: faster sampling via domain-sparsification of distributions and parallel algorithms for sampling determinant-based distributions.

Based on joint works with Callum Burgess, Michał Dereziński, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, Kevin Tian, Thuy-Duong Vuong and Elizabeth Yang.
 

Michael Chapman
Hebrew University

Cutoff: New Results and New Methods.

View Slides (PDF)

In recent years, random walks on simplicial complexes proved extremely useful. They were used, for example, to uniformly sample matroid bases and to define high-dimensional 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 University

Improved Product-Based High-Dimensional Expanders

View Slides (PDF)

High-dimensional expanders generalize the notion of expander graphs to higher-dimensional simplicial complexes. In contrast to expander graphs, only a handful of high-dimensional expander constructions have been proposed, and no elementary combinatorial construction with near-optimal expansion is known. In this talk, Golowich will introduce an improved combinatorial high-dimensional expander construction by modifying a previous construction of Liu, Mohanty and Yang (ITCS 2020), which is based on a high-dimensional 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 product-based constructions.
 

Matthew Kahle
Ohio State University

Randomness and High-Dimensional Expansion

View Slides (PDF)

Kahle will survey some expander-related 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 Jerusalem

The Cascade Conjecture, Topology, and the Four-Color Theorem

Helly-type 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 University

High-Dimensional Simplicial Trees

Similar in spirit to the notion of coboundary expansion, simplicial trees were developed by regarding a graph as a one-dimensional complex and generalizing appropriately. This point of view is consistent with the matroid-theoretic 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 high-dimensional expansion.
 

Nati Linial
Hebrew University

Geodesic 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 shortest-path 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 non-metric. That is, P cannot be realized by assigning lengths to G’s edges. Linial will prove that the vast majority of all graphs are non-metrizable in the sense that G has a consistent non-metric 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 University

Spectral Independence: A New Tool to Analyze Markov Chains

View Slides (PDF)

Markov chain Monte Carlo is a widely used class of algorithms for sampling from high-dimensional 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 high-dimensional 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 long-standing 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 Study

The C^3 Problem: Locally Testable Codes with Constant Rate and Constant Distance

View Slides (PDF)

An error-correcting 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 long-standing 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 two-dimensional 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 University

Random Walks on Partite Complexes

View Slides (PDF)

Partite simplicial complexes are the natural generalization of bipartite graphs: an n-dimensional simplicial complex is called ‘partite’ if its vertices can be colored with n+1 colors such that each n-dimensional 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 Grinbaum-Reizis.
 

Madhur Tulsiani
Toyota Technological Institute at Chicago, University of Chicago

A Weak-Regularity Lemma for High-Dimensional Expanders and Algorithmic Applications

Tulsiani will discuss an analogue of the weak-regularity lemma of Frieze and Kannan, for high-dimensional 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 error-correcting codes.

This talks is based on joint work with Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana and Shashank Srivastava.
 

Henry Yuen
Columbia University

Noncommutative Property Testing

View Slides (PDF)

In this talk, Yuen will discuss property testing in the noncommutative context. Instead of testing properties of deterministic black-box 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 low-degree 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.

Irit Dinur
Institute for Advanced Study & Weizmann Institute

High Dimensional Expanders in Theoretical Computer Science

View Slides (PDF)

Expander graphs have been useful in computer science with versatile applications, including coding theory, networking, computational complexity and geometry.

High-dimensional 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 high-dimensional expanders. Can these be harnessed for further computer science applications? She will describe the state-of-the-art and interesting future directions.
 

To attend this in-person 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.
On-site registration will not be permitted. Walk-in entry will be denied.