Theory of Computation Seminars

Reduction From Non-Unique Games To Boolean Unique Games

Dana Moshkovitz, UT Austin

Apr 20, 2020
1:45 pm to 2:45 pm | Zoom

We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap 1-delta vs. 1-C*delta, for any C>1, and sufficiently small delta>0) to the problem of proving a PCP Theorem for a certain non-unique game.
In a previous work, Khot and Moshkovitz suggested a candidate reduction (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 game we reduce from is similar to non-unique games for which PCP theorems are known.

Our proof relies on a new concentration theorem for functions in Gaussian space that are restricted to a random hyperplane.  We bound the typical Euclidean distance between the low degree part of the restriction of the function to the hyperplane and the restriction to the hyperplane of the low degree part of the function.

This is joint work with Ronen Eldan (Weizmann)

Speaker Bio

Dana Moshkovitz is an associate professor of Computer Science at UT Austin. Her research is in Theoretical Computer Science. Much of it focuses on the limitations of approximation algorithms and probabilistic checking of proofs.

Dana did her PhD at the Weizmann Institute in Israel. Her thesis co-won the Nessyahu Prize for best math PhD thesis in Israel in 2009, and part of this work was awarded the FOCS 2008 Best paper. Dana went on to spend a couple of years at Princeton University and the Institute of Advanced Study before joining MIT as an assistant professor. Dana is the recipient of the Jerome Saltzer teaching award of MIT EECS.


Carol Harlow