Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion.

Peng Cui2015

TL;DR

This paper introduces a new hypothesis about the average-case hardness of a problem called "Unbalanced Max 3-XOR." Based on this hypothesis, the authors prove stronger NP-hardness results for approximating two important problems: Minimum Unique Game (Min UG) and Small Set Expansion (SSE). Specifically, they show that Min UG is hard to approximate within a factor of 2 - ε, and Min Bisection (a variant of SSE) is hard to approximate within 3 - ε.

What Problem Does This Paper Address?

The paper tackles the challenge of understanding the limits of approximation algorithms for certain computational problems. Specifically, it focuses on the Unique Game Problem (UG) and the Small Set Expansion Problem (SSE). For UG, the goal is to find a labeling of graph vertices that satisfies as many edge constraints as possible, where each constraint involves a permutation. The Minimum Unique Game (Min UG) is the opposite: minimize unsatisfied edges. For SSE, the aim is to find a subset of vertices with a specific density that minimizes the number of edges connecting it to the rest of the graph. Min Bisection is a special case of SSE where the subset must have exactly half the vertices.

While significant progress has been made in establishing NP-hardness for approximating these problems (meaning it's likely impossible to find a polynomial-time algorithm that guarantees a good solution), there's still a gap between the best known hardness results and what might be theoretically possible. For Min UG, the best known hardness is a factor of 5/4 - ε, and for Min Bisection, it's 4/3 - ε. This paper seeks to push these hardness bounds further, making it even harder to find efficient approximation algorithms.

Methods

The core of this paper's contribution lies in introducing and leveraging a new hypothesis: a variation of Feige's Hypothesis. This hypothesis posits that it's computationally hard on average to refute "Unbalanced Max 3-XOR" instances under biased assignments. Unbalanced Max 3-XOR involves finding an assignment to variables that satisfies the most XOR clauses, where each clause has three literals, and the clauses are constructed with a bias towards negative literals.

Using this new hypothesis, the authors employ a standard technique in theoretical computer science: reduction. They construct gadgets and mappings to transform instances of Unbalanced Max 3-XOR into instances of Min 2-Lin-2 (a problem related to solving linear equations over GF(2)) and Min Bisection. The properties of these gadgets are carefully designed so that the hardness of the original problem (Unbalanced Max 3-XOR) translates into stronger hardness for the target problems (Min UG and SSE).

Specifically, they show:

  • Min 2-Lin-2 hardness: They construct a gadget that maps an Unbalanced Max 3-XOR instance to a Min 2-Lin-2 instance. The hardness of distinguishing between satisfiable and unsatisfiable instances of the former translates to a hardness of 3/2 - ε for approximating Min 2-Lin-2. Since Min 2-Lin-2 is related to Min UG, this implies a strengthened hardness for Min UG.
  • Min Bisection hardness: They construct a graph gadget that maps an Unbalanced Max 3-AND instance (closely related to Unbalanced Max 3-XOR) to a Min Bisection instance. The hardness of distinguishing between satisfiable and unsatisfiable instances of the former translates to a hardness of 3 - ε for approximating Min Bisection.

Datasets

Not discussed in the paper. The paper focuses on theoretical hardness results and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • A New Hypothesis for Average-Case Hardness: The paper introduces a novel variation of Feige's Hypothesis concerning the average-case hardness of "Unbalanced Max 3-XOR." This hypothesis is crucial as it provides a new starting point for proving stronger hardness results.
  • Bridging the Gap in Hardness: The work successfully pushes the known NP-hardness bounds for Min UG and Min Bisection, narrowing the gap between current best results and potential theoretical limits. This is a significant step in understanding the inherent difficulty of these problems.
  • The Power of Gadget Constructions: The paper demonstrates the effectiveness of carefully crafted "gadgets" in reducing problems. These gadgets are key to translating the hardness of one problem into hardness for another, often by encoding logical constraints into graph or equation structures.
  • Limitations of the Current Approach: The authors acknowledge that their method, even with the new hypothesis, has limitations. It can strengthen the hardness for Min UG to 2 - ε but falls short of proving the conjectured Ω(1) hardness. This suggests that further theoretical breakthroughs might be needed for even stronger results.

Key Results

  • Strengthened Hardness for Min 2-Lin-2: Assuming the new variation of Feige's Hypothesis, Min 2-Lin-2 is proven to be NP-hard to approximate within a factor of 3/2 - ε.
  • Strengthened Hardness for Min UG: This result implies that Minimum Unique Game (Min UG) is NP-hard to approximate within 2 - ε, an improvement over the previous 5/4 - ε bound.
  • Strengthened Hardness for Min Bisection: Assuming the new hypothesis, Min Bisection is proven to be NP-hard to approximate within a factor of 3 - ε, an improvement over the previous 4/3 - ε bound.
  • Generalization to k-CSP: The paper discusses how the proposed method can be generalized to k-ary Constraint Satisfaction Problems (k-CSP) with Samorodnitsky-Trevisan hypergraph predicates, leading to a hardness of 2 - κ for Min 2-Lin-2. However, it also notes that this generalization has limitations for larger k.

Limitations and Future Work

  • Inability to Prove Ω(1) Hardness for Min UG/SSE: The authors explicitly state that their method, even with the strengthened hypothesis, cannot prove the conjectured Ω(1) hardness for Min UG or Small Set Expansion. This suggests that further theoretical advancements or different approaches might be necessary to reach these stronger hardness bounds.
  • Dependence on a New Hypothesis: The results are contingent on the proposed variation of Feige's Hypothesis. Proving this hypothesis independently would further solidify the findings.
  • Generalization Limitations: While the paper discusses generalization to k-CSP, it notes that the resulting hardness for Min 2-Lin-2 (2 - κ) is not strong enough to prove constant factor hardness for Min UG when k is large. This indicates that the current reduction techniques might not be sufficient for all cases of generalized problems.
  • Future Work: The paper implicitly suggests exploring alternative hypotheses or more powerful reduction techniques to overcome the limitations and achieve stronger hardness results for Min UG and SSE. Investigating the average-case complexity of other CSPs under biased assignments is also a natural extension.

Summary updated

Abstract

In this paper, the author strengthens the previous known hardness for approximating Minimum Unique Game Problem, 5/4 − e, by proving that Min 2Lin-2 is NP-hard to be approximated within 2 − e and strengthens the previous known hardness for approximating Small Set Expansion Problem, 4/3 − e, by proving that Min Bisection is NP-hard to be approximated within 3− e, assuming a variation of Feige’s Hypothesis, which claims that refuting Unbalanced Biased Max 3XOR is NP-hard on average on a natural distribution. In Unique Game Problem (UGP), we are given a graph G = (V, E), and a set of labels, [k]. Each edge e = (u, v) in the graph is equipped with a permutation πe : [k] → [k]. The solution of the problem is a labeling f : V → [k] that assigns a label to each vertex of G. An edge e = (u, v) is said to be satisfied under f if πe( f (u)) = f (v). The goal of the problem is to find a labeling such that the number of the satisfied edges under this labeling is maximized. The value of the instance Val(I) is defined as the maximum fraction of the satisfied edges under all labeling. In the same situation of UGP, the goal ofMinimum Unique Game Problem (Min UGP) is to find a labeling such that the number of the unsatisfied edges under this labeling is minimized. The value of the instance Val(I) is defined as the minimum fraction of the unsatisfied edges under all labelling. In Max 2Lin-2, we are given a set of linear equations over GF2. Each equation contains exactly two variables. The goal of the problem is to seek an assignment of the variables such that the number of satisfied equations is maximized. In the same situation of Max 2-Lin-2, the goal of Min 2Lin-2 is to seek an assignment of the variables such that the number of unsatisfied equations is minimized. Note that Max 2Lin-2 is a special case of UGP, and Min 2Lin-2 is special case of Min UGP. The Unique Game Conjecture (UGC)[1] states: for every ζ, δ > 0, there is a k = k(ζ, δ) such that given an instance I of UGP with k labels it is NP-hard to distinguish whether Val(I) > 1 − ζ or Val(I) 0. The (c′, s′)-approximation NP-hardness of Min UGP is defined as: for some fixed 0 s′ − e or Val(I) 0. In Small Set Expansion Problem (SSE), we are given a graph G = (V, E) and a constant 0 0, there is a δ such that it is NP-hard to distinguish whether ΦG(δ) > 1− η or ΦG(δ) < η. As a special case of Small Set Expansion Problem, Min Bisection is defined as: given a graph G with n vertices, where n is even, find a set S of n/2 vertices (a bisection) such that the number of edges connecting S and V S (the bisection width) is minimized. In the paper[4], the author shows a new point of (1/2, 3/8)-approximation NPhardness of UGP, which is an improvement of previously known (3/4, 11/16)-approximation NP-hardness of UGP[2]. Their result determines a two-dimensional region of for (c, s)-approximation NP-hardness of UGP, namely, the triangle with the three vertices (0, 0), (1/2, 3/8), and (1, 1). All known points of (c, s)-approximation NP-hardness of UGP are in the triangle, plus an inferior bump area near the origin by [3]. However, the best known hardness for approximating Min UGP is still 5/4 − e despite all the efforts. It is known that Min Bisection (and SSE) is NP-hard to be approximated within 4/3 − e by [5]. It would be interesting to answer the question whether we can further enlarge the hardness gap of Min UGP and SSE. In this paper, the author strengthens the previous known hardness for approximating Minimum Unique Game Problem, 5/4 − e, by proving that Min 2Lin-2 is NP-hard to be approximated within 2 − e and strengthens the previous known hardness for approximating Small Set Expansion Problem, 4/3 − e, by proving that Min Bisection is NP-hard to be approximated within 3 − e, assuming a variation of Feige’s Hypothesis, which claims that refuting Unbalanced Biased Max 3XOR is NP-hard on average on a natural distribution. In Fig. 1, the red area is the known region of (c, s)-approximation NP-hardness of UGP, the yellow area is the region of (c, s)-approximation NP-hardness of UGP assuming the variation of Feige’s Hypothesis. InMax 3XOR, we are given a set of XOR clauses, each clause contains exactly three literals. The goal of the problem is to seek an assignment of the Boolean variables such that the number of satisfied clauses is maximized. In Max 3AND, we are given a set of AND clauses, each clause contains exactly three literals. The goal of the problem is to seek an assignment of the Boolean variables such that the number of satisfied clauses is maximized. In Unbalanced Biased Max 3XOR, we are given a set of XOR clauses, each clause contains exactly three literals. The fraction of negative occurrence of each variable is exactly β < 1/2, which is called balance of the instance. In addition, the domain of the variables is restricted such that the fraction of variables assigned to 0 is no more than γ < β, which is called bias of the instance. In random Unbalanced Biased Max 3XOR, we assume that formulas are generated by the following random process. Given parameters n and m, each clause is generated independently at random by selecting the three variables in it independently at random and inserting the negative literal of the variable into the clause with probability β < 1/2
BibTeX
@misc{cui2015strengthened,
  author = {Peng Cui},
  title = {{Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion.}},
  year = {2015},
}
Figure