Showing cs.CCShow all
2 papers · 1 filter
cs.CC2005
Conditional Hardness for Approximate Coloring
Irit Dinur, Elchanan Mossel, Oded Regev
We study the coloring problem: Given a graph G, decide whether or , where c(G) is the chromatic number of G. We derive conditional hardness for this probl…
cs.CC2003
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
Irit Dinur, Venkatesan Guruswami, Subhash Khot +1
Given a -uniform hyper-graph, the E-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP constr…