2012/04/10 by Peng Cui, Cui, Peng · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1204.2026
11 pages, 1 figure
openalex publication_date 2012/04/10 · arxiv created 2014/12/15 · arxiv updated 2014/12/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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-ε, by proving that Min 2-Lin-2 is hard to within 3/2-ε and strengthens the previous known hardness for approximating Small Set Expansion, 4/3-ε, by proving that Min Bisection is hard to approximate within 3-ε. 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-κ where κ is a small absolute positive, but is short of proving ω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.