Max Hopkins (Theory Seminar)

Abstract: Small-set expansion has long played an important role in hardness of approximation and in the search for a proof of the Unique Games Conjecture (UGC). In recent work, understanding the small-set expansion in the Johnson and Grassmann graphs were key to proving the 2-2 Games Conjecture, the strongest evidence yet of the hardness of unique games. The breakthrough analysis of expansion for these graphs by Khot, Minzer, Moshkovitz, and Safra, however, lacked a framework for extending the results for future progress on the UGC. This talk will cover joint work with Lovett, Kaufman, and Rao, in which we propose viewing small-set expansion in these graphs through the lens of High Dimensional Expanders (HDX). By using a framework for Boolean analysis on HDXs introduced by Dikstein, Dinur, Filmus, and Harsha, we show how to tighten and extend some of the bounds from Khot et. al's previous work to a more general, and potentially useful, set of graphs.