Technical Summary: Sharp Low-Degree Thresholds for Planted-vs-Planted Testing

1. Problem Formulation

The paper addresses the problem of planted-vs-planted testing, a hypothesis testing task where the goal is to distinguish between two structured distributions, both containing hidden ("planted") structures, rather than distinguishing a structured distribution from a null (unstructured) distribution.

Specifically, the authors focus on the problem of "counting communities": determining whether observed data was generated by a model with $\ell$ planted communities or a model with $\ell'$ planted communities, where $\ell \neq \ell'$ are fixed distinct positive integers. This is studied in two canonical high-dimensional models:

1. Planted Submatrix Model (PSM): A symmetric matrix where entries are Gaussian, with elevated means for pairs of indices belonging to the same planted community.
2. Planted Dense Subgraph Model (PDS): A graph (or adjacency matrix) where edge probabilities are elevated for pairs within the same planted community.

The primary objective is to establish sharp computational thresholds for this testing problem using the low-degree polynomial framework. This framework posits that if no polynomial of degree $D$ can distinguish the distributions, then no polynomial-time algorithm (where runtime is roughly $n^D$) can succeed. The authors aim to identify the exact leading constant of the signal-to-noise ratio (SNR) threshold, rather than just the order of magnitude.

2. Methodology

The paper develops a novel low-degree certificate framework tailored for planted-vs-planted settings. Standard low-degree lower bound techniques often rely on the null distribution being a product measure, allowing for orthogonal expansions in the observed variables. In planted-vs-planted testing, both hypotheses contain latent structure, making the reference law non-product.

The authors overcome this via three main steps:

1. Latent-Variable Expansion: They expand the degree-$D$ polynomials against an orthonormal basis of the underlying independent variables (latent labels and noise) rather than just the observations. This extends the latent-variable orthogonalization method used for recovery problems (e.g., [SW25]) to the testing setting.
2. Linear Certificate Construction: They reduce the problem of bounding the degree-$D$ advantage (a measure of distinguishability) to constructing a vector $u$ (a certificate) satisfying a linear system $u^\top M = c^\top$. By Bessel's inequality, the squared advantage is bounded by $\|u\|^2$.
3. Pruning of Non-Signal Contributions: A critical innovation is the identification and pruning of "bad" graph indices. They define a graph index as "good" if it contains a subgraph whose basis polynomial has different expectations under the two hypotheses. They prove that the certificate can be supported entirely on these "good" graphs. This allows them to ignore "bad" graphs (typically trees in these models) which have identical moments under both hypotheses, significantly simplifying the norm bound calculation.

For the upper bounds (constructing separating polynomials), the authors utilize:

• Balanced Unicyclic Graphs (BUGs): For strong testing (vanishing error), they construct polynomials based on counting balanced unicyclic graphs. These are the minimal connected structures that distinguish the models, as tree statistics have identical expectations under both planted laws.
• Trace and Signed Triangle Statistics: For weak testing (beating random guessing), simpler statistics suffice: the trace (sum of diagonal entries) for PSM and signed triangle counts for PDS.

3. Key Contributions and Results

A. Sharp Thresholds for Strong Testing

The paper establishes the first sharp low-degree thresholds for strong testing (vanishing error probability) in planted-vs-planted settings.

• Result: For both the Planted Submatrix Model (PSM) and Planted Dense Subgraph Model (PDS), the sharp threshold for distinguishing $\ell$ vs. $\ell'$ communities coincides, down to the sharp constant, with the known sharp low-degree recovery threshold for the corresponding one-community model.
• Threshold Value: The threshold is given by $\lambda \approx (\rho\sqrt{en})^{-1}$, where $\rho$ is the sparsity of planted vertices and $\lambda$ is the signal strength.
• Implication: This resolves the question of whether testing is strictly easier than recovery. The authors show that at the level of sharp low-degree thresholds, the difficulty of distinguishing $\ell$ vs. $\ell'$ is identical to the difficulty of recovering a single community structure.

B. Smooth Transition for Weak Testing

In contrast to strong testing, the paper identifies that weak testing (achieving power bounded away from random guessing) does not exhibit a sharp threshold but rather a smooth transition.

• Result: Weak testing becomes possible at a signal strength scale of $\lambda \approx (\rho\sqrt{n})^{-1}$.
• Gap: There is a gap between the weak testing scale and the strong testing scale by a factor of $\sqrt{e}$. The weak testing threshold is strictly lower than the strong testing threshold.
• Mechanism: Weak testing can be achieved by simple statistics (trace for PSM, signed triangles for PDS) that aggregate global information, whereas strong testing requires the more complex counting of unicyclic structures.

C. Framework Generalization

The authors provide a general framework for planted-vs-planted testing that reduces the lower bound problem to a linear certificate problem on informative subgraphs. This framework is shown to be applicable to models with conditionally independent observations given latent variables.

4. Significance and Claims

The paper claims to provide the first sharp thresholds for low-degree polynomial tests in planted-vs-planted settings. Its significance lies in:

1. Bridging Detection and Recovery: It formally connects the complexity of distinguishing two planted models to the complexity of recovering a planted structure, showing they share the same sharp threshold constant in these models.
2. Refining Computational Phase Transitions: It demonstrates that while some problems (like planted clique) exhibit smooth trade-offs between signal strength and runtime, others (like community counting in sparse regimes) exhibit sharp phase transitions.
3. Methodological Advancement: It successfully adapts the low-degree recovery framework (specifically the pruning and orthogonalization techniques from [SW25]) to the more complex planted-vs-planted setting, overcoming the lack of a product null measure.

The authors explicitly state that their results are limited to the low-degree polynomial model, which serves as a proxy for polynomial-time algorithms. They do not claim to prove hardness for all polynomial-time algorithms (which remains an open complexity-theoretic challenge) but provide strong evidence within the low-degree framework. The work does not propose new experimental applications but rather refines the theoretical understanding of computational limits in high-dimensional inference.