Quasirandomness conjecture for constant-degree tests of stochastic block models

Let $\mathbb{P}_n$ be a stochastic block model, with parameters allowed to depend arbitrarily on $n$, and let $\mathbb{G}(n,1/2)$ denote the Erdős–Rényi random graph. A signed subgraph count is the statistic associated with a signed copy count of a fixed graph, and a constant-degree polynomial test is a polynomial test of degree bounded independently of $n$. The hypotheses are

$$\mathsf{H}_0: \mathbb{G}(n,1/2),\qquad \mathsf{H}_1: \mathbb{P}_n.$$

Quasirandomness conjecture. There exists a constant-degree polynomial test that distinguishes these hypotheses with high probability if and only if one of the signed subgraph counts for an edge, a star, a triangle, or a $4$-cycle distinguishes them with high probability.

This conjecture seeks to extend the preceding star-count result to arbitrary stochastic block models, including models in which conditioning on the latent structure does not force edge probabilities to be at least $1/2$. The paper proves the claim under several structural conditions, including cross-community edge probability exactly $1/2$, all edge probabilities at least $1/2$, community probabilities bounded below by a universal positive constant, or two communities; the general case remains open.