The alpha-constraint label-cover hardness conjecture

Let G=(V,E),2R,ΨG={\rangle (V,E),2R,\Psi\langle} be a label-cover instance whose constraints are alpha-constraints, where an alpha-constraint is defined by permutations π1,π2:{1,,2R}{1,,2R}\pi_1,\pi_2:\{1,\ldots,2R\}\to\{1,\ldots,2R\} and the relation

α={(2i1,2i1),(2i,2i1),(2i1,2i)}i=1R.\alpha=\{(2i-1,2i-1),(2i,2i-1),(2i-1,2i)\}_{i=1}^R.

For a labeling LL, let sat(G){\sf sat}(G) be the maximum fraction of constraints it satisfies, and let isatt(G){\sf isat}_t(G) be the largest relative size of a vertex set admitting a labeling by subsets of at most tt labels that satisfies all induced constraints. The alpha-constraint hardness conjecture. For every ε>0\varepsilon>0 and tNt\in\mathbb{N} there exists some RNR\in\mathbb{N} such that it is NP-hard to distinguish between

sat(G)=1{\sf sat}(G)=1

and

isatt(G)<ε.{\sf isat}_t(G)<\varepsilon.

This conjecture is used for the reduction to approximate coloring with three colors and is described as seemingly stronger than Khot's conjectures; the source notes that the corresponding hardness for t=1t=1 was implicitly proved previously, while the conjecture concerns every constant tt.

Sources & referencesView supporting material

Primary source

Irit Dinur, Elchanan Mossel and Oded Regev, “Conditional Hardness for Approximate Coloring”, arXiv:cs/0504062 (2005).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.