Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Unique Game Conjecture:
TR15-058 | 1st April 2015
Peng Cui

Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion

In this paper, the author puts forward a variation of Feige's Hypothesis, which claims that it is hard on average refuting Unbalanced Max 3-XOR under biased assignments on a natural distribution. Under this hypothesis, the author strengthens the previous known hardness for approximating Minimum Unique Game, $5/4-\epsilon$, by proving that ... more >>>

TR18-006 | 10th January 2018
Subhash Khot, Dor Minzer, Muli Safra

Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

Revisions: 2

We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes
the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a
contribution from [BKT].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves ... more >>>

TR18-034 | 15th February 2018
Young Kun Ko

On Symmetric Parallel Repetition : Towards Equivalence of MAX-CUT and UG

Unique Games Conjecture (UGC), proposed by [Khot02], lies in the center of many inapproximability results. At the heart of UGC lies approximability of MAX-CUT, which is a special instance of Unique Game.[KhotKMO04, MosselOO05] showed that assuming Unique Games Conjecture, it is NP-hard to distinguish between MAX-CUT instance that has a ... more >>>

TR18-077 | 23rd April 2018
Boaz Barak, Pravesh Kothari, David Steurer

Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture

Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khot's 2 to 2 games conjecture follows from a combinatorial hypothesis about the soundness of a certain ``Grassmanian agreement tester''.
In this work, we show that the hypothesis of Dinur et al follows from a ... more >>>

TR19-004 | 11th January 2019
Amey Bhangale, Subhash Khot

UG-hardness to NP-hardness by Losing Half

The $2$-to-$2$ Games Theorem of [KMS-1, DKKMS-1, DKKMS-2, KMS-2] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than $\varepsilon$ fraction of the constraints, for every constant $\varepsilon>0$. We show that the reduction ... more >>>

ISSN 1433-8092 | Imprint