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.
This conference will bring together mathematicians and computer scientists with a wide range of interests to hear about these developments and to discuss future directions of research.

Meeting Report
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, errorcorrecting 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 highdimensional 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 onedimensional 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 highdimensional 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.
MingHsuan Kang from Taiwan gave an overview of the stateoftheart 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 highdimensional expanders. He stressed that this theory is not just a generalization of the onedimensional 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 highdimensional expanders have some of those properties themselves. This was followed by a talk by Prahladh Harsha who described, along these same lines, how socalled ‘good’ locally testable codes might be constructed by defining small locally testable codes on local pieces of a highdimensional 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 twodimensional Ramanujan complex, explaining the two strips in the eigenvalues as coming from the the edges and from the vertices. Finally, OveisGharan described the program of using analysis of random walks on highdimensional 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 coboundary 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 nonabelian coefficients and its connection to topological almostcovering 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.

Agenda
WEDNESDAY, OCTOBER 23
9:30 AM Peter Sarnak  Density Theorems and Applications 11:00 AM Shai Evra  Ramanujan Complexes and Super Golden Gates 1:30 PM Ori Parzanchevski  Random Walks on Ramanujan Complexes and Applications 3:00 PM MingHsuan Kang  Ihara Zeta Functions, Lfunctions and Automata 5:00 PM PUBLIC LECTURE, Alex Lubotzky  HighDimensional Expanders THURSDAY, OCTOBER 24
9:30 AM Irit Dinur  Agreement Tests on High Dimensional Expanders 11:00 AM Prahladh Harsha  Lifting Small Locally Testable Codes (LTCs) to Large LTCs via HDXs 1:00 PM Ryan O'Donnell  Explicit NearRamanujan Graphs of Every Degree 2:30 PM Konstantin Golubev  The Vertex Shadow on the Edge Laplacian Spectrum 4:00 PM Shayan Oveis Gharan  High Dimensional Expanders and Analysis of Markov Chains FRIDAY, OCTOBER 25
9:30 AM Tali Kaufman  CoBoundary Expanders from Symmetry and Short Radius 11:00 AM Uli Wagner  Maps from complexes to Euclidean spaces: Quantitative and Algorithmic Aspects 1:00 PM Roy Meshulam  Near Coverings, Cosystolic Expansion and Topological Property Testing 
Abstracts
Irit Dinur
Institute for Advanced Study and the Weizmann InstituteAgreement Tests on HighDimensional 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 highdimensional 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 StudyRamanujan 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 RamanujanPetersson 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 ZurichThe 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 highdimensional Laplace spectrum is concentrated around the degree, and again, these can be interpreted as sparsifiers of the complete ddimensional complex. Some researchers have conjectured that Ramanujan complexes should have these properties, but we have shown that the Laplace spectrum of 2dimensional kregular 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 2complexes. This is joint work with Ori Parzanchevski.
Prahladh Harsha
Tata Institute of Fundamental ResearchLifting 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 Dleft 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 nbits. 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 SipserSpielman 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 bipartitegraph is part of an HDX and a smalllift is testable, then so is a large lift.
MingHsuan Kang
National ChiaoTung UniversityIhara Zeta Functions, Lfunctions and Automata
In this talk, Kang will introduce generalizations of Ihara zeta functions on both padic groups of adjoin type and simply connected padic groups. For padic groups of adjoint type, Ihara zeta function is related to Langlands Lfunction and Kang will try to give this connection a combinatoric explanation. For simply connected padic 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 UniversityCoBoundary Expanders from Symmetry and Short Radius
Kaufman will introduce a highdimensional analogue of a spanning tree. She will show that symmetric complexes with highdimensional spanning tree of small depth (i.e., with short highdimensional radius) obey highdimensional form of a Cheeger inequality known as coboundary expansion. Using this characterization Kaufamn will study new coboundary expanders that do not arise from buildings. This is joint work with Izhar Oppenheim.
Alex Lubotzky
Hebrew UniversityExpander 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
TechnionNear 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 ‘coverstable.’ Meshykan will show that this is equivalent to X being a cosystolic expander with respect to nonabelian coefficients. This gives a new combinatorialtopological interpretation to cosystolic expansion, which is a wellstudied notion of highdimensional expansion. As an example, he will show that the 2dimensional spherical building is coverstable.
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 UniversityExplicit NearRamanujan Graphs of Every Degree
For every constant d >= 3 and epsilon > 0, O’Donnell gives a deterministic poly(n)time algorithm that outputs a dregular graph on Θ(n) vertices that is epsilonnearRamanujan (i.e., its eigenvalues are bounded in magnitude by 2sqrt(d1)+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 WashingtonHighDimensional 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 highdimensional expanders as a new ‘global’ tool to study mixing time of Markov chains.
Ori Parzanchevski
Hebrew UniversityRandom 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 highdimensional 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 UniversityDensity Theorems and Applications
In the theory of Lfunctions, 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 AustriaMaps 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 kdimensional simplicial complex K, does it admit a (piecewiselinear) embedding into ddimensional 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)?