Khot's bipartite d-to-1 conjecture

About 21 years old · traced to

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.

References

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.