{"id":"arxiv/2608.06279","url":"https://arxiv.org/abs/2608.06279","tags":["cs.CC","cs.DS","math.PR"],"score":0,"title":"Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth","domain":"cs.CC","source":"arxiv","authors":["Xuan Chen","Shuangping Li"],"reviews":0,"subject":"cs.CC","summary":"The low-degree heuristic has become a widely used framework for predicting computational thresholds in average-case planted-versus-null problems. However, a recent sequence of counterexamples shows that low-degree indistinguishability does not, in general, rule out efficient noise-tolerant distinguishers; see Buhai et al. (2025) and Mao (2026). Motivated by these developments, Hsieh et al. (2026) initiated the study of rigorous consequences of the low-degree heuristic. In this work, we continue this program for planted-graph problems. Let $Q_n=G(n,c/n)$, and let $P_n$ be obtained by planting…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-06","reactions":{}}