2026-10-11T04:21:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25372 2026-03-19T12:04:10Z ddc:004 open_access

Recovering Communities in Structured Random Graphs Kapralov, Michael Trevisan, Luca Wrzos-Kaminska, Weronika Hypercube graphs Community detection Fourier analysis of Boolean functions The problem of recovering planted community structure in random graphs has received a lot of attention in the literature on the stochastic block model, where the input is a random graph in which edges crossing between different communities appear with smaller probability than edges induced by communities. The communities themselves form a collection of vertex-disjoint sparse cuts in the expected graph, and can be recovered, often exactly, from a sample as long as a separation condition on the intra- and inter-community edge probabilities is satisfied. In this paper, we ask whether the presence of a large number of overlapping sparsest cuts in the expected graph still allows recovery. For example, the d-dimensional hypercube graph admits d distinct (balanced) sparsest cuts, one for every coordinate. Can these cuts be identified given a random sample of the edges of the hypercube where each edge is present independently with some probability p ∈ (0, 1)? We show that this is the case, in a very strong sense: the sparsest balanced cut in a sample of the hypercube at rate p = Clog d/d for a sufficiently large constant C is 1/poly(d)-close to a coordinate cut with high probability. This is asymptotically optimal and allows approximate recovery of all d cuts simultaneously. Furthermore, for an appropriate sample of hypercube-like graphs recovery can be made exact. The proof is essentially a strong hypercube cut sparsification bound that combines a theorem of Friedgut, Kalai and Naor on boolean functions whose Fourier transform concentrates on the first level of the Fourier spectrum with Karger’s cut counting argument. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Kapralov and Luca Trevisan and Weronika Wrzos-Kaminska 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.85 urn:nbn:de:0030-drops-253727 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.85 eng https://creativecommons.org/licenses/by/4.0/legalcode