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.
- 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