picture

Recent trends in the study of expanders and high dimensional expanders

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

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

Instructor: Ori Parzanchevski

Lecture 1: Expanders and Ramanujan graphs
We will recall what are expanders graphs, and review some of their combinatorial properties. From the spectral theory of regular trees we will arrive at the notion of Ramanujan graphs, and then glimpse how number theory appears in the construction of such graphs.

Lecture 2: Buildings and Ramanujan complexes.
We will explain the problem of constructing high-dimensional expanders, and in particular the lack of random constructions. Then, we will present Ramanujan complexes as a highdimensional generalization of Ramanujan graphs. For this purpose we will describe what are Bruhat-Tits buildings, which are the high-dimensional analogues of regular trees.

Lecture 3: Expansion in Ramanujan complexes
We will study the spectral theory of Ramanujan complexes by two methods: a combinatorial analysis which will allow us to deduce global expansion from local expansion, and representation theory, which will give us optimal global results. No previous knowledge of representation theory will be assumed..

Lecture 4: Random walks on Ramanujan digraphs and complexes.
We will describe some notions of random walks on Ramanujan complexes, and show that they converge optimally fast to the uniform distribution. The analysis will involve combinatorics, representation theory, and the notion of Ramanujan digraphs, which will be expained as well.

Lecture 5: Trees and buildings in quantum computation.
We will briefly explain what a quantum gate is, and what does “compiling a quantum circuit” mean. Then we will show how the theory of Ramanujan graphs and complexes allows us to build optimal quantum gates. No prior knowledge of quantum computation will be assumed..