Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
Abstract
The low-degree method predicts computational thresholds by asking whether low-degree polynomials can distinguish a planted distribution from a null one. Recent counterexamples by Buhai, Hsieh, Jain, and Kothari (FOCS 2025) and Mao (2026) show that low-degree indistinguishability does not, in general, rule out efficient algorithms, even on noisy inputs. Hsieh, Kane, Kothari, Li, Mohanty, and Tiegel (STOC 2026) asked what it does imply, and showed that for permutation-invariant distributions on {0,1}n, low-degree indistinguishability from the uniform distribution implies statistical indistinguishability after noise. In this work, we study the same question for planted subgraphs in sparse random graphs. Let Qn=G(n,c/n), and let Pn be obtained by planting a uniformly random copy of a deterministic graph Γn into an independent sample from Qn. In the supercritical regime c>1, we show that if Pn is degree-Dn indistinguishable from Qn and the treewidth of Γn is o(Dn/log n), then a noisy version of Pn is asymptotically indistinguishable from Qn. In the critical and subcritical regimes 0<c≤ 1, we obtain the same conclusion without any treewidth assumption, provided Dn=ω(log n). Our proof has two main ingredients. First, we identify the subgraph-count and automorphism factors in the Fourier expansion with counts of isomorphism triples. Second, we cut a tree decomposition of Γn into subtrees, which splits each large Fourier support into low-degree pieces that meet at only a few interface vertices, and we use noise to absorb the cost of reassembling them. At and below criticality, we use the low-degree assumption to rule out short cycles and noise to destroy the remaining long ones.
Related
- Estimation and Recovery of a Planted Dense Subgraph from a Single Network Cascade
- Context-Guided Traversal with Deep Reinforcement Learning for Suspicious Subgraph Detection in Cryptocurrency Transaction Graphs
- Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth
- Modularity in planted partition model
- Bounds on Treewidth via Excluding Disjoint Unions of Cycles
BibTeX
@misc{chen2026rigorous,
title = {{Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth}},
author = {Xuan Chen and Shuangping Li},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2608.06279},
eprint = {2608.06279},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.06279},
}
RIS
TY - UNPB
TI - Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
AU - Xuan Chen
AU - Shuangping Li
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2608.06279
UR - https://arxiv.org/abs/2608.06279
AB - The low-degree method predicts computational thresholds by asking whether low-degree polynomials can distinguish a planted distribution from a null one. Recent counterexamples by Buhai, Hsieh, Jain, and Kothari (FOCS 2025) and Mao (2026) show that low-degree indistinguishability does not, in general, rule out efficient algorithms, even on noisy inputs. Hsieh, Kane, Kothari, Li, Mohanty, and Tiegel (STOC 2026) asked what it does imply, and showed that for permutation-invariant distributions on {0,1}^n, low-degree indistinguishability from the uniform distribution implies statistical indistinguishability after noise. In this work, we study the same question for planted subgraphs in sparse random graphs. Let Q_n=G(n,c/n), and let P_n be obtained by planting a uniformly random copy of a deterministic graph Γ_n into an independent sample from Q_n. In the supercritical regime c>1, we show that if P_n is degree-D_n indistinguishable from Q_n and the treewidth of Γ_n is o(D_n/log n), then a noisy version of P_n is asymptotically indistinguishable from Q_n. In the critical and subcritical regimes 0<c≤ 1, we obtain the same conclusion without any treewidth assumption, provided D_n=ω(log n). Our proof has two main ingredients. First, we identify the subgraph-count and automorphism factors in the Fourier expansion with counts of isomorphism triples. Second, we cut a tree decomposition of Γ_n into subtrees, which splits each large Fourier support into low-degree pieces that meet at only a few interface vertices, and we use noise to absorb the cost of reassembling them. At and below criticality, we use the low-degree assumption to rule out short cycles and noise to destroy the remaining long ones.
ER -