PC Seminar: Exact Computational Thresholds for Testing Between Planted Models

Abstract: High-dimensional planted models provide a canonical setting for the analysis of statistical–computational tradeoffs, and sharp phase transitions for detection and recovery are now established in a broad class of these problems. We study hypothesis testing between two planted models: given a sample from one of two planted distributions, when can a polynomial-time algorithm reliably determine which distribution generated it? Our analysis is carried out in the low-degree polynomial framework, which is conjectured to capture the power of polynomial-time algorithms for a wide range of high-dimensional inference tasks. Prior work of Rush et al. (2022) gave the first computational lower bounds for such planted-vs-planted testing problems, but did not locate the precise point at which testing becomes computationally feasible.

We close this gap for a family of problems by giving exact low-degree thresholds for testing between a model with one planted structure and a model with multiple planted structures. More precisely, we prove matching low-degree upper and lower bounds for strong detection, thereby pinning down the low-degree phase transition in these testing problems. Our proofs combine structural properties of planted models with refined graph-combinatorial arguments, and build on techniques developed for recovery in planted problems by Sohn and Wein (2025).

Based on joint work with Fiona Skerman, Alexander Wein, and Daniel Gutierrez-Espinoza.

This is a seminar in our seminar series on Probability and Combinatorics (PC).