首次确定低度多项式测试在结构化模型中的精确阈值，揭示检测与恢复的统一性。
Sharp Low-Degree Thresholds for Planted-vs-Planted Testing
- 基于潜在变量展开和信号去噪方法，构建新型植株-植株检验框架。
- 在植株子矩阵与稠密子图模型中，检测阈值与恢复阈值精确一致。
- 发现弱检测无尖锐阈值，呈现平滑过渡，适合理论研究者参考。
本文首次建立了低度多项式测试在植株-植株设置下的精确阈值，目标是通过渐近可忽略的错误判断哪一种结构化的植株机制生成了观测数据。我们证明了在植株子矩阵和植株稠密子图模型中，计数社区任务的低度上下界匹配，所得检测阈值在常数项上与已知的低度恢复阈值完全一致。相比之下，弱检测任务（仅需优于随机猜测）不具有尖锐阈值，而表现为平滑过渡，我们准确识别了这一现象。为实现上述结果，我们发展了一个新框架，其基于源自低度恢复的潜变量展开，并引入新方法以识别并剔除非信号贡献。
原文摘要 · Abstract (English)
We establish the first sharp thresholds for low-degree polynomial tests in planted-vs-planted settings, where the goal is to determine with vanishing error which of two structured planted mechanisms generated the observed data. We prove matching low-degree upper and lower bounds for counting communities in the planted submatrix and planted dense subgraph models. The resulting testing threshold coincides, down to the sharp constant, with the known low-degree recovery threshold. In contrast, the task of weak testing, where the goal is to outperform random guessing, does not have a sharp threshold but rather a smooth transition, which we identify. To prove our results, we develop a framework for planted-vs-planted testing that builds on a latent-variable expansion originating in low-degree recovery and employs new methods to identify and prune non-signal contributions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。