A&C Seminar: Max Hopkins "Hypercontractivity and Small-Set Expansion on High Dimensional Expanders"
Speaker
Max Hopkins
UC San Diego
Abstract: Hypercontractivity is one of the most powerful tools in Boolean function analysis. Traditionally studied on the Boolean cube, recent years have seen a number of exciting applications of hypercontractivity on extended domains, most famously including the resolution of Khot’s 2-2 games conjecture. Despite such impressive applications, however, our general understanding of hypercontractivity actually remains remarkably poor, with few known examples and complicated, domain-specific proofs.
In this talk, we discuss the first steps towards a unified theory of hypercontractivity based on high dimensional expanders (HDX), a broad class of hypergraphs that have recently seen a series of breakthrough applications in coding theory and approximate sampling. We’ll pay special attention to the motivating application of characterizing small-set expansion in graphs, and briefly discuss how the line of work could lead to new insights towards resolving the unique games conjecture.
Based on joint work with Mitali Bafna, Tali Kaufman, and Shachar Lovett to appear at STOC 2022.
In this talk, we discuss the first steps towards a unified theory of hypercontractivity based on high dimensional expanders (HDX), a broad class of hypergraphs that have recently seen a series of breakthrough applications in coding theory and approximate sampling. We’ll pay special attention to the motivating application of characterizing small-set expansion in graphs, and briefly discuss how the line of work could lead to new insights towards resolving the unique games conjecture.
Based on joint work with Mitali Bafna, Tali Kaufman, and Shachar Lovett to appear at STOC 2022.