2026/08/03 by Weronika Wrzos-Kaminska
Computer Science · #cs.DS
arxiv created 2026/08/03 · arxiv updated 2026/08/04
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 λ-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 \widetilde O(n1/2+O(1/log(d/λ))), and produces a data structure that answers color queries in time \widetilde O(n1/2+O(1/log(d/λ))), such that the resulting labeling agrees with the planted coloring on all but an O(√(λ/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.