← 研踪 PaperTrailarXiv:2608.06279 · v2
Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
首次提交 2026-08-07 01:07
版本更新 2026-11-03 11:28
雷达观测 2026-11-04 23:40
摘要
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\le 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.
作者备注：41 pages, 4 figures
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-03 11:28 · 最新观测版本
Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
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\le 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.
查看此版本解读 →查看此版本原文 ↗