BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230706T120000Z
UID:b78a73b72d3cee1ad71a594029fe4115-481
DTSTAMP:19700101T120021Z
DESCRIPTION:Unique Games and Expansion
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/481/unique-games-and-expansion/
SUMMARY:The Unique Games Conjecture (UGC) is a central open question in computational complexity and algorithms. In short, the UGC stipulates that almost satisfiable instances of Unique Games, a certain 2-variable constraint satisfaction problem (CSP), are NP-hard to distinguish from highly unsatisfiable instances. The UGC is known to imply a vast number of hardness-of-approximation results in combinatorial optimization. In this talk I will discuss our results that give algorithms for Unique Games (UG) on a large class of restricted instances: certifiable small-set expanders and graphs with certifiable global hypercontractivity. Our first algorithm solves UG instances whenever low-degree sum-of-squares (SoS) proofs certify good bounds on the small-set-expansion of the underlying constraint graph. A more complicated version of our algorithm succeeds even when the constraint graph is not a small-set expander as long as the structure of non-expanding small sets is “characterized” by a low-degree SoS proof, a property we call certified global hypercontractivity. The latter algorithm gives new insights into the breakthrough 2-2 Games hardness result, in particular, gives us some evidence as to what hard instances of UG look like.


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

We are grateful to the Kirani family for generously supporting the theory seminar series



Hosts: Rameesh Paul, Rachana Gusain, Rahul Madhavan, KVN Sreenivas
DTSTART:20230706T120000Z
END:VEVENT
END:VCALENDAR