Abstract
Random d-regular graphs are k-colorable with high probability when k >~ d/2 log d, and polynomial-time distinguishable from the standard k-colorable planted model once k <~ sqrt(d); for k >~ sqrt(d), there is mounting evidence that polynomial-time distinguishing is not possible. However, polynomial-time *refutation* of k-colorings in random d-regular graphs has only been acheived when k <~ sqrt(d)/2. We give evidence that this factor-of-two discrepancy, far from being a quirk of the available techniques, is a fundamental feature of the problem — and conjecture that no polynomial time refutation algorithm can improve on it. We begin by observing that refuting k-colorings in uniformly random d-regular graphs is at least as hard as distinguishing such graphs from any k-colorable planted distribution, and, so motivated, study a particular "quietly planted" model based on noisy random lifts of a small, k-colorable base graph. We give evidence that, for infinitely many d and k, this quiet model is indistinguishable in polynomial time from uniformly random d-regular graphs whenever k >~ sqrt(d)/2. Analogous results hold for refutation of large k-way cuts.