Multiple Planted Structures Below $\sqrt{n}$: An SoS Integrality Gap and an SQ Lower Bound
2026-04-08 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study problems where multiple hidden patterns (like cliques) are planted in a large random network. They show that a popular algorithmic method called Sum-of-Squares (SoS) fails to reliably detect these multiple hidden cliques when their total size is below a certain threshold related to the square root of the network size. They also prove using another framework, statistical queries (SQ), that no efficient algorithm can distinguish between the planted and random cases under similar size constraints. This work generalizes known single-pattern hardness results to settings with multiple disjoint planted structures.
planted cliqueSum-of-Squares (SoS)integrality gapstatistical query (SQ) modelaverage-case inferencebicliquepseudoexpectationdisjoint planted structurescomputational thresholdrandom graph
Authors
Matvey Mosievskiy, Lev Reyzin
Abstract
We study computational limitations in \emph{multi-plant} average-case inference problems, in which $t$ disjoint planted structures of size $k$ are embedded in a random background on $n$ elements. A natural parameter in this setting is the total planted size $K := kt$. For several classic planted-subgraph problems, including planted clique, existing algorithmic and lower-bound evidence suggests a characteristic computational threshold near $\sqrt{n}$ in the single-plant setting. Our main result is a Sum-of-Squares (SoS) integrality gap for refuting the presence of multiple planted cliques. Specifically, for $G \sim G(n,1/2)$, we construct a degree-$d$ SoS pseudoexpectation for the natural relaxation that maximizes the total size of up to $t$ disjoint cliques. Throughout the regime $kt \le n^{1/2 - c\sqrt{d/\log n}},$ for a universal constant $c>0$, this relaxation achieves objective value $kt(1-o(1))$, and therefore degree-$d$ SoS cannot certify an upper bound below $kt$. This extends the planted-clique SoS lower bounds of~\cite{BarakHKKMP19} to a multi-plant setting with explicit disjointness constraints. As complementary evidence from a different computational model, we prove a lower bound in the statistical query (SQ) framework, extending the results of~\cite{FeldmanGRVX17}. We show that for detecting $t$ disjoint planted $k \times k$ bicliques (equivalently, a row-mixture distribution), when $kt = O(n^{1/2-δ})$ for any fixed $δ>0$, no polynomial-time SQ algorithm can distinguish the planted and null distributions with constant advantage.