PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximation Resistant Predicates From Pairwise Independence

Per Austrin, Elchanan Mossel

arXiv:0802.2300v1cs.CC

TL;DR

The paper asks how to characterize approximation-resistant predicates and proves a sufficient condition based on balanced pairwise independence. Under a Unique Games assumption, that condition yields hardness of approximation for the associated CSP.

  • Problem

    The paper studies the structure of approximation-resistant predicates and how well related CSPs can be approximated.

    Source: §1 · pp. 1–2

  • Method

    The authors prove a sufficient condition using a balanced pairwise independent distribution that assigns positive probability to satisfying assignments.

    Source: §1.1 · p. 3, §3 · p. 8

  • Results

    Under the (t+1,k)-UGC, the condition makes Max CSP(P) NP-hard to approximate within a stated threshold.

    Source: §3 · p. 8

  • Takeaways & Limitations

    The criterion provides a route to hereditary approximation resistance through pairwise-independent distributions.

    Source: §1.1 · p. 3

    The authors note a small constant gap of roughly 1/0.44 to the best current bound and say a stronger unconditional bound on h(n) may be possible.

    Source: CSPq · p. 13, §4.2 · p. 13

Abstract

from arXiv · show

We study the approximability of predicates on $k$ variables from a domain $[q]$, and give a new sufficient condition for such predicates to be approximation resistant under the Unique Games Conjecture. Specifically, we show that a predicate $P$ is approximation resistant if there exists a balanced pairwise independent distribution over $[q]^k$ whose support is contained in the set of satisfying assignments to $P$.

1 In tro du tion

This section presents a sufficient condition for hereditary approximation resistance under UGC, based on a balanced pairwise independent distribution supported on a predicate’s satisfying assignments. It applies the proof to a wide range of q-ary and Boolean Max-CSP predicates, establishing hardness results and parametrized hardness under a family of assumptions implied by UGC.

1 Introduction

  • The introduction motivates studying hereditary approximation resistance because, assuming UGC, most predicates are hereditary approximation resistant as k grows, and such predicates make up a vast majority.It also notes that hardness constructions commonly seek approximation-resistant predicates with very few accepting inputs.Source: §1 · p. 2

1.1 Our contributions

  • A balanced pairwise independent distribution supported on P’s satisfying assignments makes Max CSP(P) UG-hard to approximate beyond its random-assignment baseline, so P is hereditarily approximation resistant.This is the paper’s main sufficient condition for predicates over [q].Source: §1.1 · p. 3
  • Pairwise-independent-distribution constructions yield UG-hardness bounds for Max k-CSP_q, with a stronger ratio when k = 2r − 1.The supplied theorem text does not preserve the hardness-ratio expressions clearly enough to report them.Source: §1.1 · p. 3
  • For prime-power q, the paper states a further UG-hardness improvement, including a stronger ratio when k = (q^r − 1)/(q − 1).The authors describe this as improving on Engebretsen’s hardness result.Source: §1.1 · p. 4
  • The Boolean Max k-CSP hardness improves the prior UGC result [21] by essentially a factor of 2, narrowing the stated gap to the best algorithm from roughly 2/0.44 to roughly 1/0.44.The theorem applies for k ≥ 3 and any ǫ > 0.Source: §1.1 · p. 4

1.2 Related work

  • The related-work subsection opens by comparing the paper’s results with those of Samordnitsky and Trevisan, but the supplied passage gives no further comparison details.Source: §1.2 · p. 4
  • The proof applies to any pairwise independent distribution, whereas [21] requires a specific hypergraph linearity test.The construction lets any pairwise distribution define a long-code test; the analysis uses bounds on expectations of products under certain correlations.Source: §1.2 · pp. 4–5
  • The results cover a wide range of Max CSP(P) predicates, extend to any domain [q], and improve the hardness factor for most k even when q = 2.The authors note that it is unclear whether the earlier results in [21] extend to larger domains.Source: §1.2 · p. 5
  • The authors give a family of (t, k)-UGC assumptions, all implied by UGC, with t = 2 equivalent to UGC and larger t yielding weaker assumptions.Each value of t implies a different hardness factor for approximation.Source: §1.2 · p. 5
  • Even the (4, k)-UGC implies Max k-CSP hardness of O(k/2^k), and smaller t yields hardness better than the best known unconditional result.The passages also state that for t ≥ 3, Max k-CSP is NP-hard to approximate within a bound, but the bound is incomplete in the supplied text.Source: §1.2 · p. 5

2 De nitions

Section 2 defines the Unique Games assumptions and the influence and correlated-space tools used to analyze predicates on correlated inputs.

2.1 Unique Games

  • The (t,k)-UGC asks for hardness distinguishing instances with Opt_k ≥ 1 − δ from those with Opt_t ≤ δ; the paper mainly uses (3,k)-UGC, implied by UGC.The section leaves open whether the converse holds or whether the stronger conjecture can be proved without UGC.Source: §2.1 · p. 5

2.2 In uen es

  • Coordinate influence measures dependence on one variable, while low-degree influence restricts that measure to the low-degree part of a function's expansion.For f: [q]^n → [0,1], at most τ/m coordinates can have low-degree influence at least τ.Source: §2.2 · p. 6

2.3 Correlated Probabilit y Spa es

  • The section defines balanced measures by uniform coordinate marginals and t-wise independence by uniform joint marginals on every t-coordinate subset.It also introduces correlation between product-space blocks and states that low-influence functions on t-wise-independent correlated spaces behave almost as under independence, even with limited large influences.Source: §2.3 · p. 7

3 Main theorem

The main theorem gives a UGC-based hardness criterion for predicates using balanced t-wise independent distributions supported on satisfying assignments. Its proof reduces Unique Label Cover to Max CSP(P), establishing completeness and soundness through a long-code verifier.

3 Main theorem

  • A balanced t-wise independent distribution supported on satisfying assignments makes P approximation resistant under the stated Unique Games assumption.The paper also states that the condition gives hereditary approximation resistance when more satisfying assignments are added.Source: §3 · p. 8
  • In the reduction, the prover writes a table for each vertex function f_v:[q]^L→[q]; shift invariance is enforced by querying f_v(x1−x1,...,xL−x1), and acceptance requires P(b1,...,bk).Source: §3 · p. 8
  • When Opt_k(X) ≥ 1 − δ, the verifier accepts with probability at least (1 − η)Pr_{w∼μ}[P(w)].This is the completeness guarantee for the long-code proof in the reduction.Source: §3 · pp. 8–9
  • When Opt_{t+1}(X) is sufficiently small, the verifier's soundness bounds acceptance for every proof, yielding the reduction's hardness direction.The threshold δ depends on ε, η, t, k, and q.Source: §3 · pp. 8–9
  • (1 − 2η)c and s + εc/4 are the respective completeness and soundness bounds for the Max CSP(P) instances.The reduction distinguishes instances with Opt ≥ (1 − 2η)c from those with Opt ≤ s + εc/4.Source: §3 · p. 10

4 Inappro ximabilit y for Max k -CSPq

This section establishes Unique-Games-based hardness for Max k-CSP_q using balanced independence, and presents constructions of balanced pairwise-independent distributions and their hardness consequences for particular domains. It also bounds h(n) by n + O(n^0.525) and uses this bound with Proposition 4.3 to obtain Theorem 1.4.

4 Inappro ximabilit y for Max k -CSPq

  • Corollary 4.1 states that a balanced t-wise independent distribution yields a Max k-CSP_q NP-hardness consequence under (t+1,k)-UGC.The stated corollary assumes t ≥ 2; its approximation threshold is not legible in the supplied passages.Source: §4 · p. 10
  • Binary BCH distributions yield hardness O(k^⌈t/2⌉/2^k) under (t+1,k)-UGC; at t=2, the bound is O(k/2^k), tight up to a constant.The section reduces strong inapproximability to finding small t-wise independent distributions, while focusing mainly on pairwise independence.Source: §4 · p. 10

4.1 Theorems 1.2 and 1.3

  • Lemma 4.2 gives a ring-based recipe in which compatible vectors produce balanced pairwise independence from a uniformly random vector.For m vectors in R^n satisfying the lemma's pairwise condition, the resulting distribution over R^m has support size |R|^n.Source: §4.1 · p. 11
  • For k=2^r−1, Theorem 1.2 gives hardness q^(log_2(k)−k); for general k, the construction may lose a factor q.Source: §4.1 · p. 11
  • When k = (q^r−1)/(q−1), the hardness is k(q−1)+1; for general k, a factor q is lost, and when q ≥ k the hardness is q^2/q^k.Source: §4.1 · p. 12

4.2 Theorem 1.4

  • For k≥3, Hadamard matrices yield UG-hardness within h(k+1)/2^k + ε under (3,k)-UGC.The construction uses a balanced pairwise-independent distribution with support size h(k+1), obtained from Hadamard matrix rows.Source: §4.2 · p. 12
  • Corollary 4.6 gives h(n) ≤ n + O(n^0.525), using a prime between n and n+n^0.525; with Proposition 4.3, it yields Theorem 1.4.Source: §4.2 · pp. 12–13
  • Stronger construction techniques than those of Theorem 4.4 may yield a stronger unconditional bound on h(n) than Corollary 4.6 provides.Source: §4.2 · p. 13

5 Dis ussion

The discussion presents a sufficient condition for hereditary approximation resistance under a weakened Unique Games Conjecture: satisfying assignments must contain a balanced pairwise independent distribution. Small constructions of such distributions yield approximation-resistant predicates with few accepting inputs and improved hardness for Max k-CSP.

5 Discussion

  • A satisfying set containing a balanced pairwise independent distribution suffices for hereditary approximation resistance under a weakened Unique Games Conjecture.The discussion then uses small constructions of these distributions to obtain approximation-resistant predicates with few accepting inputs and improved hardness for Max k-CSP.Source: §5 · p. 13

CSPq

The discussion identifies limits and open questions for Max k-CSP hardness from approximation-resistant predicates. It distinguishes Boolean and larger-domain bounds and asks whether stronger Unique Games assumptions or a converse to the pairwise-independence condition would sharpen the results.

CSPq

  • The discussion asks whether stronger (t,k)-UGC assumptions could improve Max k-CSP hardness beyond the best current NP-hardness result; even understanding (k,k)-UGC is described as an open question.Source: CSPq · p. 13
  • It remains open whether pairwise independence is necessary for hereditary approximation resistance, or only a sufficient condition.Source: CSPq · p. 13
  • For k ≡ 2, 3 (mod 4), the Boolean bound matches Hast’s result that predicates accepting at most 2⌊k/2⌋+1 inputs are not approximation resistant [9].Source: CSPq · p. 13
  • For k ≡ 0, 1 (mod 4), the discussion reports a gap of 2 between how few satisfying assignments an approximation-resistant predicate can and cannot have.Source: CSPq · p. 13
  • The route to Max k-CSP hardness through small approximation-resistant predicates cannot be pushed further, yet a gap of roughly 1/0.44 remains to the best current algorithm.The discussion asks whether that algorithm can be improved.Source: CSPq · p. 13
  • For q = 2^l and k = (q^r−1)/(q−1), the gap between the best algorithm and best inapproximability is Θ(q/log^2 q).Source: CSPq · p. 13

Referen es

The references cover approximation algorithms and hardness for CSPs, alongside work on the Unique Games Conjecture, optimal inapproximability, and related mathematical tools.

References

  • The bibliography lists an approximation algorithm for Max k-CSP [5], improved approximation hardness for Maximum CSP [7], and a Max kCSP approach outperforming a random assignment by almost a linear factor [8].Source: Referen es · p. 14
  • It cites work on optimal inapproximability and the power of unique games [10, 12, 13].Source: Referen es · p. 14
  • Other cited foundations include Gaussian bounds for noise correlation, pairwise-independent random variables, and orthogonal matrices [16, 17, 19].Source: Referen es · p. 15

A Go o d lab ellings from in uen tial v ariables

The lemma relates a sufficiently large fraction of edges meeting the stated threshold condition to a lower bound on Opt_t(X). It constructs a labeling by choosing labels uniformly from each vertex’s candidate set.

A Go o d lab ellings from in uen tial v ariables

  • If at least an ε fraction of edges meet the stated condition for a vector a, index i, and t-element set J, then Opt_t(X) is at least δ, defined as ε.The condition includes a threshold involving g_{v,a} for some a in [q].Source: A Go o d lab ellings from in uen tial… · p. 15
  • The labeling chooses each vertex’s label uniformly from C(v), using an arbitrary label if C(v) is empty.The passage also bounds |C(v)| by q·d/τ.Source: A Go o d lab ellings from in uen tial… · p. 15
  • For edges satisfying Equation 3, each j in J has probability 1/|C(v_j)| that π_j(ℓ(v_j)) equals i.The proof uses this probability to bound the chance that an edge is t-wise satisfied and then considers the expected number of such edges.Source: A Go o d lab ellings from in uen tial… · p. 15
Loading 0802.2300v1…