Khot's bipartite d-to-1 conjecture

From papers

Fix an integer d>1d>1. Let Φ=(X,Y,Ψ,W)\Phi=(X,Y,\Psi,W) be a weighted bipartite dd-to-11 label-cover instance with label sets {1,,R}\{1,\ldots,R\} and {1,,R/d}\{1,\ldots,R/d\} and total edge weight w(Φ)=1w(\Phi)=1. A labeling LL assigns labels from the respective sets, and wL(Φ)w_L(\Phi) denotes the total weight of satisfied constraints. Khot's bipartite d-to-1 conjecture. For every γ>0\gamma>0 there exists a constant RR such that it is NP-hard to distinguish between the case that some labeling satisfies all constraints, so wL(Φ)=1w_L(\Phi)=1, and the case that every labeling satisfies total weight at most γ\gamma.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.