## Small-Set Expansion on the Grassmann Graph.

Dor Minzer

Member, School of Mathematics

October 23, 2018

A graph G is called a small set expander if any small set of vertices contains only a small fraction of the edges adjacent to it.

This talk is mainly concerned with the investigation of small set expansion on the Grassmann Graphs, a study that was motivated by recent applications to Probabilistically Checkable Proofs and hardness of approximation.

This talk is mainly concerned with the investigation of small set expansion on the Grassmann Graphs, a study that was motivated by recent applications to Probabilistically Checkable Proofs and hardness of approximation.