A new point of NP-hardness for 2-to-1 Label Cover

arxiv: 1204.5666 · v1 · pith:GOMPUG46new · submitted 2012-04-25 · 💻 cs.CC

Per Austrin , Ryan O'Donnell , John Wright This is my paper

classification 💻 cs.CC

keywords coverlabelto-1assignmentfindgiveninstancenp-hard

0 comments

read the original abstract

We show that given a satisfiable instance of the 2-to-1 Label Cover problem, it is NP-hard to find a $(23/24 + \eps)$-satisfying assignment.

This paper has not been read by Pith yet.