Finding Pseudorandom Colorings of Pseudorandom Graphs

Abstract

We consider the problem of recovering a planted pseudorandom 3-coloring in expanding and low threshold-rank graphs. Alon and Kahale [SICOMP 1997] gave a spectral algorithm to recover the coloring for a random graph with a planted random 3-coloring. We show that their analysis can be adapted to work when coloring is pseudorandom i.e., all color classes are of equal size and the size of the intersection of the neighborhood of a random vertex with each color class has small
variance. We also extend our results to partial colorings and low threshold-rank graphs to show the following:

* For graphs on n vertices with threshold-rank r, for which there exists a 3-coloring that is eps-pseudorandom and properly colors the induced subgraph on (1-gamma)n vertices, we show how to recover the coloring for (1 - O(gamma + eps)) n vertices in time (rn)^{O(r)}.

* For expanding graphs on n vertices, which admit a pseudorandom 3-coloring properly coloring all the vertices, we show how to recover such a coloring in polynomial time.

Our results are obtained by combining the method of Alon and Kahale, with eigenspace enumeration methods used for solving constraint satisfaction problems on low threshold-rank graphs.