Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-058 | 1st April 2015 08:50

Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion


Authors: Peng Cui
Publication: 13th April 2015 10:08
Downloads: 1734


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 Min 2-Lin-2 is hard to within $3/2-\epsilon$ and strengthens the previous known hardness for approximating Small Set Expansion, $4/3-\epsilon$, by proving that Min Bisection is hard to approximate within $3-\epsilon$. In addition, the author discusses the limitation of this method to show that it can strengthen the hardness for approximating Minimum Unique Game to $2+\kappa$ where $\kappa$ is a small absolute positive, but is short of proving $\omega_k(1)$ hardness for Minimum Unique Game (or Small Set Expansion), by assuming a generalization of this hypothesis on Unbalanced Max k-CSP with Samorodnitsky-Trevisan hypergraph predicate.

ISSN 1433-8092 | Imprint