2026-09-10T09:44:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27762 2026-09-09T12:19:37Z ddc:004 open_access

Recovering Planted Colorings in Sublinear Time Wrzos-Kaminska, Weronika sublinear algorithms spectral algorithms graph coloring We study the problem of recovering a planted k-coloring in sublinear time. Given an expander G with a planted coloring, the goal is to efficiently construct a small-space data structure that allows consistent color queries: given a vertex v, the algorithm quickly returns the color of v according to the planted solution. 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. In the adjacency list model, our algorithm has preprocessing time and space Õ(n^{1/2 + O(1/log(d/λ))}), and produces a data structure that answers color queries in time Õ(n^{1/2 + O(1/log(d/λ))}). With a high constant probability, 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. Our algorithm gives sublinear time inner product access to the bottom eigenspace of the normalized adjacency matrix by using random walks, which allows us to adapt the classical spectral approach of Alon and Kahale in sublinear time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Weronika Wrzos-Kaminska 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.45 urn:nbn:de:0030-drops-277627 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.45 eng https://creativecommons.org/licenses/by/4.0/legalcode