Speaker:Vedat Levi Alev

Title

High-Dimensional Expansion, Theory and Applications

Abstract

The expansion of a graph is a measure of its connectivity — a graph with strong connectivity properties is called an expander graph. Expander graphs have found countless applications in computer science, thanks to their pseudorandom properties and potential sparsity. In this talk, we will focus on “high-dimensional expansion” — an extension of the study of expansion from the setting of graphs to the setting of hyper-graphs and set systems. We will also talk about applications of high-dimensional expansion in, (i) approximating constraint satisfaction problems such as k-SAT, (ii) list-decoding and construction of direct sum codes, and (iii) analyzing the mixing time of random walks which play a very important role in the field of random-sampling, such as the Glauber dynamics.

Based on joint work with: Lap Chi Lau, Fernando Granha-Jeronimo,  Ori Parzanchevski, Dylan Quintana, Shashank Srivastava, and Madhur Tulsiani

About Vedat Levi Alev

Vedat Levi Alev is a postdoctoral fellow at the Einstein Institute of Mathematics in the Hebrew University of Jerusalem, hosted by Gil Kalai, Alexander Lubotzky, and Ori Parzanchevksi. He completed his PhD in the University of Waterloo, under the supervision of Lap Chi Lau. Broadly interested in theoretical computer science, his particular focus is in spectral graph theory, random walks, and approximation algorithms.