Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth

Xuan Chen, Shuangping Li

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 coun…