Speaker: Prahladh Harsha

Title: Explicit SoS lower bounds from high-dimensional expanders

Abstract: In recent years, high dimensional expanders (HDXs) have
found a variety of applications in theoretical computer science. In
this talk, we see yet another surprising application of explicit
constructions of HDXs: explicit hard integrality-gap instances for
the Sum-of-Squares hierarchy. In contrast, all previously known hard
instances, proving inapproximability in the SoS hierarchy, are random
instances.

This construction offers an interesting and baffling contrast to the
recent work of Alev, Jeronimo and Tulsiani who showed that instances
in which the variables correspond to vertices in a HDX are easy to
solve. In contrast, in our instances the variables correspond to the
edges of the complex. The talk will be self-contained and no prior
knowledge of HDXs will be assumed.

[Joint work with Irit Dinur, Yuval Filmus and Madhur Tulisiani]