Seminars

View all Seminars  |  Download ICal for this event

On High Dimensional Expanders and Hardness of Approximation

Series: Bangalore Theory Seminars

Speaker: Max Hopkins Ph.D student University of California San Diego

Date/Time: Sep 09 11:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
Expander graphs are a classical tool in theoretical computer science, with applications ranging from network stability all the way to the PCP Theorem. In this talk, we overview recent developments in the nascent theory of high dimensional expansion, a generalization of expanders to hypergraphs and posets, and discuss a recent line of work towards their application to hardness of approximation. We focus in particular on two interconnected narratives. First, we will cover recently popularized spectral notions of high dimensional expansion, their relation to powerful tools such as hypercontractivity, and discuss how such connections could open a new path towards proving Khots Unique Games Conjecture. Second, we will introduce lesser-known topological notions of high dimensional expansion and discuss how they lead to explicit lower bounds for fundamental problems within the Sum-of-Squares semidefinite programming hierarchy, the most powerful known algorithmic paradigm for combinatorial approximation problems such as unique games. Based on a series of joint works with Mitali Bafna, Jason Gaitonde, Tali Kaufman, Ting-Chun Lin, Shachar Lovett, and Ruizhe Zhang.


For more details please visit: Link

Microsoft teams link:

Link



Hosts: Rahul Madhavan and Rameesh Paul