2019 MPS Conference on High-Dimensional Expanders

Expander graphs, particularly Ramanujan graphs, have been a major focus of research over the last five decades. These graphs are of fundamental importance in various subareas of computer science such as networks, simulations and randomization, error-correcting codes and many more. In the early days, problems concerning expander graphs attracted the attention of mathematicians who have applied some of the results from representation theory and the theory of automorphic forms to obtain explicit constructions of expanders, much needed by the computer scientists.  In the last 15 years, computer science has paid its debt to pure mathematics, and expander graphs have also become of great importance in various areas of math, such as group theory, number theory, geometry and more. It became the area with the most useful interaction between math and CS.

In recent years, a high-dimensional theory of expanders has begun to emerge. This is a relatively new development, but it has already produced results in both pure math and CS.

The main goal of the workshop was to bring together mathematicians and computer scientists working in these or related areas and to describe the main achievements and challenges facing this theory. Just like graphs (which is the one-dimensional case of the theory), this area too is very interdisciplinary and the speakers were asked, and indeed made the effort, to talk in a way that would appeal to a wide audience.

The first day began with a lecture by Peter Sarnak of Princeton University and the IAS, who described the density conjecture in number theory — a conjecture that can replace the Ramanujan conjecture for many applications relevant for combinatorial and geometric problems on high-dimensional expanders (HDX). His lecture was followed by one by Shai Evra and one by Ori Parzanchevski, which showed how to use such number theory to achieve ‘golden gates’ on some unitary groups (these are of great importance for quantum computing) and random walks on HDX.

Ming-Hsuan Kang from Taiwan gave an overview of the state-of-the-art in the zeta functions of simplical complexes and their connections with such number theoretic functions.

The first day ended with a public lecture by Alex Lubotzky from the Hebrew University of Jerusalem. In this lecture, Lubotzky described some of the achievements and challenges of this new theory of high-dimensional expanders. He stressed that this theory is not just a generalization of the one-dimensional case, but an area that leads to new horizons in pure mathematics (such as topological overlapping) and in computer science (such as property testing and locally testable codes).

The second day began with a lecture by Irit Dinur describing the type of local to global phenomenon that takes place in Probabilistically Checkable Proofs (PCPs), property testing and locally testable codes, and showed how high-dimensional expanders have some of those properties themselves. This was followed by a talk by Prahladh Harsha who described, along these same lines, how so-called ‘good’ locally testable codes might be constructed by defining small locally testable codes on local pieces of a high-dimensional expander. Harsha emphasized the similarities to and differences from the celebrated LDPC codes of Sipser and Spielman.

O’Donnell described a derandomized construction of almost Ramanujan graphs of every degree (whereas the known constructions only hold for degrees that are prime powers with some restrictions). Golubev gave a careful analysis of the spectrum of the two-dimensional Ramanujan complex, explaining the two strips in the eigenvalues as coming from the the edges and from the vertices. Finally, Oveis-Gharan described the program of using analysis of random walks on high-dimensional expanders to give new analyses for Markov Chain algorithms and problems of interest in statistical physics.

On the third day, Tali Kaufman described a higher dimensional version of a spanning tree, that looks like a cone and how families of codes shifted by a group action can be used to prove co-boundary expansion. Wagner described a plethora of results on embedability between Euclidean complexes — when is it undecidable and when is it decidable. Meshulam described two threads of research, the first having to do with cosystolic expansion with non-abelian coefficients and its connection to topological almost-covering maps. The second thread showed how Sipser Spielman codes are homological codes.

Altogether, the workshop illustrated the broad spectrum of achievements and challenges in this area and helped to create a community of scholars coming from very different backgrounds but working on related problems.

Irit Dinur
Institute for Advanced Study and the Weizmann Institute

Agreement Tests on High-Dimensional Expanders

In an agreement test, the input is a collection of local functions, each defined over a small domain, and the domains are overlapping. The goal is to stitch these into one global function.

Structures underlying agreement tests often (always?) turn out to be high-dimensional expanders. In this talk, Dinur will describe a new general framework for agreement tests capturing the known results and show some applications. This talk is based on joint work with Yotam Dikstein.
Shai Evra
Institute for Advanced Study

Ramanujan Complexes and Super Golden Gates

In their seminal works from the ’80s, Lubotzky, Phillips and Sarnak (LPS), presented two remarkable explicit constructions: infinite families of Ramanujan regular graphs and optimal topological generators for PU(2). In recent years, these two results have been generalized to higher dimensions, to the notions of (i+) Ramanujan complexes and (ii+) super golden gates for compact Lie groups.

In this talk, Evra will describe some recent works that extend the results of LPS to higher dimensions. A key ingredient in the work of LPS is Deligne’s proof of the Ramanujan-Petersson conjecture for GL(2). Unfortunately, the naïve generalization of the Ramanujan conjecture is false in higher dimensions. Following a program initiated by Sarnak and Xue in the ’90s, we prove a density hypothesis and use it as a replacement for the naïve Ramanujan conjecture.

This talk is based on joint work with (intersections of) Ori Parzanchevski, Cristina Ballantine, Brooke Feigon, Kathrin Maurischat and Amitay Kamber.
Konstantin Golubev
ETH Zurich

The Vertex Shadow on the Edge Laplacian Spectrum

Expander graphs are ones in which the nontrivial spectrum of the Laplacian is highly concentrated around the degree, and in another language, they are spectral sparsifiers of the complete graph. It is natural to look for complexes whose high-dimensional Laplace spectrum is concentrated around the degree, and again, these can be interpreted as sparsifiers of the complete d-dimensional complex. Some researchers have conjectured that Ramanujan complexes should have these properties, but we have shown that the Laplace spectrum of 2-dimensional k-regular Ramanujan complexes is concentrated in two narrow strips, one around k and one around 2k. In a new work, Golubev will shed light on this situation; he will show that the 2k strip is accounted for by ‘shadows’ of the vertices and that these complexes are in fact spectral sparsifiers of the complete tripartite complex. From this analysis of the ‘bad’ eigenvalues, Golubev is able to deduce stronger combinatorial properties for Ramanujan 2-complexes. This is joint work with Ori Parzanchevski.
Prahladh Harsha
Tata Institute of Fundamental Research

Lifting Small Locally Testable Codes (LTCs) to Large LTCs via HDXs

In this talk, Harsha will illustrate how to lift a ‘small’ locally testable code via a HDX expander to a ‘large’ locally testable code. Given a D-left regular bipartite graph G = ([n], [m], E) and a ‘small’ code C ∈ {0,1}^D, the Tanner construction shows how to lift this code to a ‘large’ code on n-bits. These Tanner lifts are extremely useful. For instance, if C is a ‘small’ code with good distance and rate, and G is a bipartite expander, then the Sipser-Spielman analysis shows that the lifted code is a ‘large’ code that has good distance and rate. Harsha will show a similar lifting property for local testability. More precisely, he will show that if C₀ is a base code, the bipartite-graph is part of an HDX and a small-lift is testable, then so is a large lift.
Ming-Hsuan Kang
National Chiao-Tung University

Ihara Zeta Functions, L-functions and Automata

In this talk, Kang will introduce generalizations of Ihara zeta functions on both p-adic groups of adjoin type and simply connected p-adic groups. For p-adic groups of adjoint type, Ihara zeta function is related to Langlands L-function and Kang will try to give this connection a combinatoric explanation. For simply connected p-adic groups, Ihara zeta function is related to the factorization of affine Weyl group, and Kang will discuss this factorization from the viewpoint of automata.
Tali Kaufman
Bar Illan University

Co-Boundary Expanders from Symmetry and Short Radius

Kaufman will introduce a high-dimensional analogue of a spanning tree. She will show that symmetric complexes with high-dimensional spanning tree of small depth (i.e., with short high-dimensional radius) obey high-dimensional form of a Cheeger inequality known as co-boundary expansion. Using this characterization Kaufamn will study new co-boundary expanders that do not arise from buildings. This is joint work with Izhar Oppenheim.
Alex Lubotzky
Hebrew University

Expander graphs, particularly Ramanujan graphs, have been a major focus of research over the last five decades. This research has yielded fruitful interactions between mathematics and computer science, with applications from one field benefiting the other. In recent years, a high dimensional theory of expanders has started to emerge.

In this lecture, Alexander Lubotzky will survey some of the achievements and challenges of this new theory. He will explain why this theory is not just a generalization but also an area that leads to new horizons in pure mathematics (such as topological overlapping) and computer science (such as property testing and locally testable codes).
Roy Meshulam
Technion

Near Coverings, Cosystolic Expansion and Topological Property Testing

Meshulam will show the stability of covers of simplicial complexes. Given a map from Y to X that satisfies almost all of the local conditions of being a cover, is it close to being a genuine cover of X? Complexes X for which this holds are called ‘cover-stable.’ Meshykan will show that this is equivalent to X being a cosystolic expander with respect to non-abelian coefficients. This gives a new combinatorial-topological interpretation to cosystolic expansion, which is a well-studied notion of high-dimensional expansion. As an example, he will show that the 2-dimensional spherical building is cover-stable.

Meshulam will show this work as an example of ‘topological property testing,’ where one is interested in studying stability of a topological notion that is naturally defined by local conditions. This is joint Work with Irit Dinur.
Ryan O’Donnell
Carnegie Mellon University

Explicit Near-Ramanujan Graphs of Every Degree

For every constant d >= 3 and epsilon > 0, O’Donnell gives a deterministic poly(n)-time algorithm that outputs a d-regular graph on Θ(n) vertices that is epsilon-near-Ramanujan (i.e., its eigenvalues are bounded in magnitude by 2sqrt(d-1)+epsilon [excluding the single trivial eigenvalue of d]). This is joint work with Sidhanth Mohanty (UC Berkeley) and Pedro Paredes (Carnegie Mellon).
Shayan Oveis Gharan
University of Washington

High-Dimensional Expanders and Analysis of Markov Chains

Most interesting probability distributions that appear in science and mathematics have exponentially large support, and we are unable to study them precisely. Researchers typically simulate Markov chains and hope that after running the chain long enough it generates random samples from the target distribution. Samples can then be exploited to estimate several quantities of interests, such as marginals or moments of the underlying distribution.

The most fundamental question is how long one should run the chain to obtain an approximate/exact sample. Over the last decades, researchers have developed several techniques that are mostly ‘local’ to answer this question. In this talk, Oveis Gharan will discuss how to use the theory high-dimensional expanders as a new ‘global’ tool to study mixing time of Markov chains.
Ori Parzanchevski
Hebrew University

Random Walks on Ramanujan Complexes and Applications

Various random walks can be defined on quotients of buildings and, in particular, on Ramanujan complexes. Parzanchevski will review various results obtained regarding or using such walks, including the Diaconis cutoff phenomenon for complexes and groups, optimal generators for GL(n,q), powering in high-dimensional expanders and the Riemann hypothesis for Ramanujan complexes. This talk is based on joint works with M. Chapman, T. Kaufman, E. Lubetzky and A. Lubotzky.
Peter Sarnak
Princeton University

Density Theorems and Applications

In the theory of L-functions, density theorems serve as substitutes for the generalized

Riemann hypothesis in a number of situations. The naïve form of the Ramanujan conjectures in the theory of automorphic forms fails in general but a density version appears to hold quite generally and serves as a substitute. Sarnak will review the above and some recent developments and applications.
Uli Wagner
Institute of Science and Technology Austria

Maps from Complexes to Euclidean Spaces: Quantitative and Algorithmic Aspects

Wagner will survey algorithmic and quantitative aspects of maps from simplicial complexes to Euclidean spaces (or other target manifolds), such as: Given a finite k-dimensional simplicial complex K, does it admit a (piecewise-linear) embedding into d-dimensional Euclidean space? Can we decide this algorithmically? If K embeds, what is the minimum geometric complexity of such an embedding (i.e., the minimum number of simplices in a subdivision K’ of K on which the embedding is simplexwise linear)? If K does not embed, to what extent can we quantify its nonembeddability (e.g., in terms of topological overlap or crossing numbers)?