BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
BEGIN:VEVENT
CATEGORIES:Colloquia / Seminar / Lecture
DESCRIPTION:We reduce the problem of proving a "Boolean Unique Games Conjec
ture" (with gap 1-delta vs. 1-C*delta\, for any C>1\, and sufficiently smal
l delta>0) to the problem of proving a PCP Theorem for a certain non-unique
game.\nIn a previous work\, Khot and Moshkovitz suggested a candidate redu
ction (i.e.\, without a proof of soundness). The current work is the first
to provide a reduction along with a proof of soundness. The non-unique ga
me we reduce from is similar to non-unique games for which PCP theorems are
known.\n\nOur proof relies on a new concentration theorem for functions in
Gaussian space that are restricted to a random hyperplane. We bound the t
ypical Euclidean distance between the low degree part of the restriction of
the function to the hyperplane and the restriction to the hyperplane of th
e low degree part of the function.\n\nThis is joint work with Ronen Eldan (
Weizmann)
DTEND:20200420T184500Z
DTSTAMP:20240524T032137Z
DTSTART:20200420T174500Z
GEO:42.3783;-71.117081
LOCATION:Zoom
SEQUENCE:0
SUMMARY:Reduction From Non-Unique Games To Boolean Unique Games
UID:tag:localist.com\,2008:EventInstance_32749274016383
URL:https://events.seas.harvard.edu/event/tba_1166
END:VEVENT
END:VCALENDAR