本文首次系统地研究了低阶多项式阈值函数（PTF）在以下假设检验问题中的表现：给定一个基准 $d$ 正则图 $G$，判断其噪声随机提升（noisy random lift）是否与一个完全随机的 $d$ 正则图等价。我们将检测任务形式化为在两个分布之间进行区分：
- $\mathcal{D}_0$：从均匀分布中抽取的 $d$ 正则图；
- $\mathcal{D}_1$：先对 $G$ 进行随机提升，再在提升后的边上加入噪声得到的图。
在此框架下，我们证明了任何固定阶数的 PTF 在区分 $\mathcal{D}_0$ 与 $\mathcal{D}_1$ 时的错误概率均保持在常数水平，因而该检测问题在低阶多项式时间内是信息论上不可区分的。关键技术在于我们对噪声随机提升中短环计数的分布进行了精细分析，证明其在对数尺度的环长范围内与完全随机正则图的分布几乎相同。该结果扩展了 McKay、Wormald 与 Wysocka 以及 Johnson 对随机正则图环计数的经典定理，也统一了 Fortin 与 Rudinsky 对随机提升的环计数分析。
我们的证明主要依赖于组合概率技巧和生成函数方法，结合了图的谱特性来控制噪声对环结构的扰动。该工作不仅为 PTF 在图结构学习中的局限性提供了理论依据，也为进一步探索更高阶或非线性检测器的潜在优势奠定了基础。
博主点评：这篇论文在理论图论与计算学习交叉点上提供了新视角，尤其是对短环分布的细致刻画，为后续研究提供了强有力的工具箱。若能将分析推广到更一般的图模型，或许能揭示更深层的计算-统计壁垒。