The alpha-constraint label-cover hardness conjecture
The alpha-constraint label-cover hardness conjecture
Let be a label-cover instance whose constraints are alpha-constraints, where an alpha-constraint is defined by permutations and the relation
For a labeling , let be the maximum fraction of constraints it satisfies, and let be the largest relative size of a vertex set admitting a labeling by subsets of at most labels that satisfies all induced constraints. The alpha-constraint hardness conjecture. For every and there exists some such that it is NP-hard to distinguish between
and
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 was implicitly proved previously, while the conjecture concerns every constant .
Sources & referencesView supporting material
Primary source
Irit Dinur, Elchanan Mossel and Oded Regev, “Conditional Hardness for Approximate Coloring”, arXiv:cs/0504062 (2005).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.