Recent trends in the study of expanders and high dimensional expanders

February 12-16, 2017 ,
The David Lopatie Conference Centre
Weizmann Institute of Science

Organizer: Tali Kaufman, Bar Ilan University
Organizing committee: David Peleg, Weizmann Institute

General School Description

The main purpose of this one-week program is to study recent trends in the study of expanders and high dimensional expanders. Expanders have proven to be extremely important in various CS applications; High dimensional expanders are starting to emerge: these are a vast stronger generalisation of expanders, that could be potentially useful in applications where expanders are not strong enough. We will study how methods based on interlacing polynomials, representation theory and buildings were useful in recent exciting developments in the study of expanders and of high dimensional expanders. The message we will try to advocate is that not only are the objects of study of interest, but also the mathematical tools that are used in their development. Namely, we would like to expose the participants to various tools based on interlacing polynomials, representation theory and buildings that are less common in the CS theory toolkit.

No prior knowledge of expanders or representation theory is assumed.

Course 1: New trends in expanders based on the method of interlacing polynomials

Instructor: Doron Puder

We will study new exciting developments in the study of expanders based on the method of Interlacing polynomials. The method of interlacing polynomials was recently developed by Marcus, Srivastana and Speilman. This method is a powerful new tool that implies the existence of optimal expander graphs of all degrees; Moreover, it implies a proof of the long standing Kadison-Singer conjecture. The main goal of this school is to expose people form CS and Math to this method, its potential, and the power that could be gained by combining it with representation theory. We believe the tools taught in this course can be useful for further applications in theoretical computer science.

No background in expanders or representation theory is assumed.

Course 2: New trends in high dimensional expanders based on Ramanujan complexes and their applications

Instructor: Ori Parzanchevski

Expansion in higher dimension is a much stronger property than the "normal" notion of expansion. As opposed to graphs, where a random constant degree graph is an expander with high probability; random constructions of high dimensional expanders are not known. In this school we will introduce the only known family of high dimensional expanders known to date, namely Ramanujan complexes. Ramanujan complexes are based on buildings; We will introduce the theory of building; We will explore phenomena like random walks in higher dimensions. We would argue that for some CS applications it is essential to use high dimensional expansion, as opposed to the common one dimensional expansion.

No background in high dimensional expanders or buildings is assumed.

Schedule

  • 09:15 - 10:00   morning meet and greet (and breakfast)
  • 10:00 - 10:55   Session 1a - Doron Puder
  • 10:55 - 11:05   Coffee break
  • 11:05 - 12:00   Session 1b - Doron Puder
  • 12:00 - 14:00   Lunch (served)
  • 14:00 - 14:55   Session 2a - Ori Parzanchevski
  • 14:55 - 15:05   Coffee break
  • 15:05 - 16:00   Session 2b - Ori Parzanchevski

Sponsors

erc logo Bar Ilan Univercity logo