12 citations · 51 across the 12 of their papers we have counts for
Showing 2012 · cs.CCShow all
2 papers · 2 filters
cs.CC2012
New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
Per Austrin, Ryan O'Donnell, Li-Yang Tan +1
We show that given a 3-colorable graph, it is NP-hard to find a 3-coloring with $(16/17 + \eps)$ of the edges bichromatic. In a related result, we show that given a satisfiable ins…
cs.CC2012
A new point of NP-hardness for 2-to-1 Label Cover
Per Austrin, Ryan O'Donnell, John Wright
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.