Khot's bipartite d-to-1 conjecture
Khot's bipartite d-to-1 conjecture
Fix an integer . Let be a weighted bipartite -to- label-cover instance with label sets and and total edge weight . A labeling assigns labels from the respective sets, and denotes the total weight of satisfied constraints. Khot's bipartite d-to-1 conjecture. For every there exists a constant such that it is NP-hard to distinguish between the case that some labeling satisfies all constraints, so , and the case that every labeling satisfies total weight at most .
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
Sign in to submit a solution.
No solutions have been posted yet.