Computer Science/Discrete Mathematics Seminar I

The emerging theory of High-Dimensional Expansion suggests a number of inherently different notions to quantify expansion of simplicial complexes. We will talk about the notion of local spectral expansion, that plays a key role in recent advances in PCP theory, coding theory and counting complexity. Our focus is on bounded-degree complexes, where the problems can be stated in a graph-theoretic language:

Let $G$ be a graph. For a vertex $v \in G$, we denote by $G_v$ the subgraph of $G $ that is induced by the neighbors of $v$. We say that $G$ is $(a,b)$-regular if (I) $G$ is $a$-regular and (II) $G_v$ is $b$-regular for every vertex $v$. We analyse the spectral expansion of $(a,b)$-regular graphs:

What is the largest spectral gap in the adjacency operator of an $(a,b)$-regular graph $G$? What is the relation between the local expansion of the graphs ${G_v : v \in G}$ and the global expansion of $G$? We will also present a new construction of $(a,b)$-regular local-and-global expanders.

Joint work with Michael Chapman and Nati Linial.