11 citations · 27 across the 17 of their papers we have counts for
Showing 2012 · cs.CCShow all
3 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.
cs.CC2012★ 10 cited
On the Usefulness of Predicates
Per Austrin, Johan Håstad
Motivated by the pervasiveness of strong inapproximability results for Max-CSPs, we introduce a relaxed notion of an approximate solution of a Max-CSP. In this relaxed version, loo…