MPS Conference on High-Dimensional Expanders

Date & Time


Location

Gerald D. Fischbach Auditorium
160 5th Ave
New York, NY 10010 United States

View Map

Wed: 8:30 AM – 6 PM
Thur: 8:30 AM – 5 PM
Fri: 8:30 AM – 2 PM

Registration Closed
Invitation Only

Participation is by invitation only. All participants must register.

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.

 

  • Agendaplus--large

    WEDNESDAY, OCTOBER 23

    8:30 AMCHECK-IN & BREAKFAST
    9:30 AMPeter Sarnak | Density Theorems and Applications
    10:30 AMBREAK
    11:00 AMShai Evra | Ramanujan Complexes and Super Golden Gates
    12:00 PMLUNCH
    1:30 PMOri Parzanchevski | Random Walks on Ramanujan Complexes and Applications
    2:30 PMBREAK
    3:00 PMMing-Hsuan Kang | Ihara Zeta Functions, L-functions and Automata
    4:00 PMBREAK
    5:00 PMPUBLIC LECTURE, Alex Lubotzky | High-Dimensional Expanders
    6:00 PMDAY ONE CONCLUDES

    THURSDAY, OCTOBER 24

    8:30 AMCHECK-IN & BREAKFAST
    9:30 AMIrit Dinur | Agreement Tests on High Dimensional Expanders
    10:30 AMBREAK
    11:00 AMPrahladh Harsha | Lifting Small Locally Testable Codes (LTCs) to Large LTCs via HDXs
    12:00 PMLUNCH
    1:00 PMRyan O'Donnell | Explicit Near-Ramanujan Graphs of Every Degree
    2:00 PMBREAK
    2:30 PMKonstantin Golubev | The Vertex Shadow on the Edge Laplacian Spectrum
    3:30 PMBREAK
    4:00 PMShayan Oveis Gharan | High Dimensional Expanders and Analysis of Markov Chains
    5:00 PMDAY TWO CONCLUDES

    FRIDAY, OCTOBER 25

    8:30 AMCHECK-IN & BREAKFAST
    9:30 AMTali Kaufman | Co-Boundary Expanders from Symmetry and Short Radius
    10:30 AMBREAK
    11:00 AMUli Wagner | Maps from complexes to Euclidean spaces: Quantitative and Algorithmic Aspects
    12:00 PMLUNCH
    1:00 PMRoy Meshulam | Near Coverings, Cosystolic Expansion and Topological Property Testing
    2:00 PMMEETING CONCLUDES
  • Abstractsplus--large

    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)?

  • Travelplus--large

    Air and Train

    Group A
    The foundation will arrange and pay for all air and train travel to the conference for those in Group A. Please provide your travel specifications by clicking the registration link above. If you are unsure of your group, please refer to your invitation sent via email.
    Group B
    Individuals in Group B will not receive travel or hotel support. Please register at the link above so that we can capture your dietary requirements. If you are unsure of your group, please refer to your invitation sent via email.

    Personal Car

    For participants driving to Manhattan, The Roger Hotel offers valet parking. Please note there are no in-and-out privileges when using the hotel’s garage, therefore it is encouraged that participants walk or take public transportation to the Simons Foundation.
  • Hotelplus--large

    Participants in Group A who require accommodations are hosted by the foundation for a maximum of four nights at The Roger hotel. Any additional nights are at the attendee’s own expense.

    The Roger New York
    131 Madison Avenue
    New York, NY 10016
    (between 30th and 31st Streets)

    To arrange accommodations, please register at the link above.

    For driving directions to The Roger, please click here.

  • Contactsplus--large

    Travel Assistance
    Christophe Vergnol, Protravel International
    chrisvgroup@protravelinc.com
    646-747-9767

    Registration, Hotel and General Meeting Assistance
    Meghan Fazzi
    Senior Executive Assistant, Simons Foundation
    mfazzi@simonsfoundation.org
    (212) 524-6080

Subscribe to MPS announcements and other foundation updates