Recovering Planted Colorings in Sublinear Time

Abstract

We give a sublinear algorithm for the planted $k$-coloring problem. Given an expander $G$ with a planted coloring, the goal is to efficiently determine the color class of a given vertex. We work in the adversarial planted coloring model of David and Feige [STOC 2016], where an adversary chooses a $d$-regular spectral $\lambda$-expander $G$ on $n$ vertices and plants a balanced $k$-coloring by partitioning the vertices into $k$ equal parts and deleting all edges within each part. This model generalizes the earlier random graph models studied by Blum and Spencer [J. Algorithms 1995] and Alon and Kahale [STOC 1994]. We give the first sublinear-time algorithm for recovering planted colorings in this model. The algorithm has preprocessing time and space $\tilde{O}\left(n^{1/2+O(1/\log (d/\lambda ))}\right)$, and produces a data structure that answers color queries in time $\tilde{O}\left(n^{1/2+O(1/\log (d/\lambda ))}\right)$, such that the resulting labeling agrees with the planted coloring on all but an $O(\sqrt{\lambda /d})$ fraction of vertices, up to a permutation of the $k$ colors. The algorithm gives sublinear-time inner product access to the bottom eigenspace of the normalized adjacency matrix, which allows us to adapt the classical spectral approach of Alon and Kahale in sublinear time.