BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20220909T120000Z
UID:a6d77130d8c6d554dc6012b25a1fc5f2-329
DTSTAMP:19700101T120011Z
DESCRIPTION:On High Dimensional Expanders and Hardness of Approximation
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/329/on-high-dimensional-expanders-and-hardness-of-approximation/
SUMMARY: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: https://www.csa.iisc.ac.in/iisc-msr-seminar/

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d



Hosts: Rahul Madhavan and Rameesh Paul
DTSTART:20220909T120000Z
END:VEVENT
END:VCALENDAR