77 citations · 79 across the 3 of their papers we have counts for
1 paper · 1 filter
Irit Dinur, Elchanan Mossel, Oded Regev
We study the coloring problem: Given a graph G, decide whether c(G)≤q or c(G)≥Q, where c(G) is the chromatic number of G. We derive conditional hardness for this probl…