Recovering Planted Colorings in Sublinear Time
2026-08-03 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors present a faster algorithm to identify the color group of a vertex in a special kind of graph where colors are hidden (planted coloring). Their method works on graphs with certain expansion properties, even when an adversary chooses the structure, meaning it’s quite robust. They improve on previous models by providing a way to quickly preprocess the graph and then answer color questions in sublinear time. Their method approximates the original coloring well, making only a small fraction of mistakes. They achieve this by efficiently computing and using spectral properties of the graph.
planted coloringexpander graphspectral graph theorysublinear algorithmregular graphgraph coloringnormalized adjacency matrixeigenspacespectral gapdata structure
Authors
Weronika Wrzos-Kaminska
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 $λ$-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\left(n^{1/2+O(1/\log(d/λ))}\right)$, and produces a data structure that answers color queries in time $\widetilde O\left(n^{1/2+O(1/\log(d/λ))}\right)$, such that the resulting labeling agrees with the planted coloring on all but an $O(\sqrt{λ/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.