A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

Boaz Barak; Samuel B. Hopkins; Jonathan Kelner; Pravesh K. Kothari; Ankur Moitra; Aaron Potechin

Source-linked AI summary

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

Boaz Barak, Samuel B. Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin

arXiv:1604.03084v2Apr 11, 2016cs.CC

TL;DR

The paper asks how far degree-d Sum-of-Squares relaxations can go on planted clique, where existing polynomial-time methods struggle near the √n scale. It introduces pseudo-calibration, a Bayesian-inspired construction of pseudo-distributions, and proves a nearly tight lower bound for SoS.

Problem
Existing polynomial-time algorithms recover planted cliques only at the ε√n scale, leaving open whether constant-degree SoS could find substantially smaller cliques.
Method
The paper introduces pseudo-calibration, requiring pseudo-distributions to match a calibration property on low-degree polynomial functions of the graph and clique variables.
Results
The degree-d SoS relaxation has integrality gap at least n^1/2−c(d/log n)^1/2 with high probability, and admits a degree-d pseudodistribution when ω≤n^1/2−c(d/log n)^1/2.
Takeaways & Limitations
For d=o(log n), the result gives a nearly tight n^1/2−o(1) lower bound and provides a general perspective on SoS limitations relative to LS+.
Takeaways & Limitations
The cited lower-bound statements formally apply to the refutation variant, and extending the earlier correction-based method failed already at degree d=6.

Abstract

from arXiv · show

We prove that with high probability over the choice of a random graph $G$ from the Erdős-Rényi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$. This yields a nearly tight $n^{1/2 - o(1)}$ bound on the value of this program for any degree $d = o(\log n)$. Moreover we introduce a new framework that we call \emph{pseudo-calibration} to construct Sum of Squares lower bounds. This framework is inspired by taking a computational analog of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.

1 Introduction

The paper studies why polynomial-time algorithms struggle with planted cliques and proves a nearly tight lower bound for degree-d Sum-of-Squares relaxations, while introducing a Bayesian-inspired proof framework.

Problem setting: The planted clique problem asks one to recover an added clique from a random G(n,1/2) graph, and connects to questions across average-case complexity and applications.Related areas include community detection, molecular biology, biological networks, game theory, property testing, compressed sensing, cryptography, and mathematical finance.
Problem setting: Existing polynomial-time algorithms only recover planted cliques of size ε√n for constant ε>0, motivating lower bounds for algorithmic approaches based on spectral methods and convex programs.The paper notes that average-case lower bounds are not expected to follow directly from standard conjectured complexity-class separations.
Prior work: Sum-of-Squares is a stronger semidefinite-programming hierarchy than LS+, raising the possibility that polynomial-time SoS could recover cliques much smaller than √n.Degree-d SoS can be solved in n^O(d) time.
Prior work: Earlier SoS lower bounds improved from approximately n^1/d to approximately n^1/2 for degree 4 and approximately n^1/(⌈d/2⌉+1) for general degree d, but left constant-degree performance unresolved.This paper addresses whether constant-degree SoS can significantly beat the √n threshold.
Main result: The main theorem gives an SoS integrality gap of at least n^1/2−c(d/log n)^1/2 for every degree function d=d(n) and sufficiently large n.The result implies a nearly tight n^1/2−o(1) bound when d=o(log n).
Proof perspective: The proof is more general and interprets SoS limitations through a computational-Bayesian lens, also clarifying differences between SoS and LS+.The authors suggest the perspective may also inform SoS upper bounds.

2 Planted Clique and Probabilistic Inference

The paper frames planted-clique SoS lower bounds through computational Bayesian probabilities and pseudo-calibration, requiring pseudo-distributions to match low-degree planted-model expectations while remaining internally consistent and positive. This framework yields degree-d certificates for random graphs up to clique size n^(1/2-c(d/log n)^(1/2)) and clarifies why weak global correlations matter.

2 Planted Clique and Probabilistic Inference: Planted clique differs from sparse random constraint problems because information about one vertex has a weak global effect on all other variables.In random 3SAT, analogous information mainly affects nearby variables because correlations decay exponentially with distance.
2.1 Computational Bayesian Probabilities and Pseudo-distributions: Computational Bayesian probabilities represent the uncertain beliefs of a bounded observer even when the graph uniquely determines the actual clique.The Sum-of-Squares algorithm provides an internally consistent set of such computational probabilities within a restricted proof system.
2.1 Computational Bayesian Probabilities and Pseudo-distributions: The calibrated pseudo-expectation enforces strong clique constraints and weak statistical relationships, including degree-based membership and neighbor/non-neighbor effects.It must assign zero to simple strong constraints and reflects that high-degree vertices are more likely to belong to the clique.
2.1 Computational Bayesian Probabilities and Pseudo-distributions: Pseudo-calibration requires the pseudo-expectation to match Bayesian conditional expectations on simple low-degree functions of the graph and clique variables.The paper defines simple functions as low-degree polynomials in both the adjacency matrix entries and the variables x; this requirement essentially determines the pseudo-distribution.
2.2 From Calibrated Pseudo-distributions to Sum-of-Squares Lower Bounds: With high probability, if ω ≤ n^(1/2-c(d/log n)^(1/2)), a degree-d pseudodistribution satisfies all six SoS constraints.This is the restated main theorem and yields the claimed integrality-gap regime for random graphs.
2.3 Proving Positivity: The positivity proof uses approximate spectral decompositions whose expected eigenvalues are nonnegative, while controlling error terms through approximate diagonalization.The moment matrix is factored approximately, and positive eigenmass must dominate off-diagonal and approximation errors.

3 Proving Positivity: A Technical Overview

The positivity proof analyzes the moment matrix through graphical-matrix decompositions, approximate diagonalization, and combinatorial control by matchings and vertex separators.

Problem setup: The moment matrix has dependent, graph-polynomial entries whose spectral structure differs from standard independent random matrices, making positive semidefiniteness difficult.The proof therefore uses symbolic factorization or approximate diagonalization.
3.1 Warm Up: The full analysis approximately diagonalizes F by splitting it into intersection-based components and choosing permutation-symmetric pieces whose off-diagonal blocks can be charged to diagonal mass.The construction is organized around decomposing F into F_0 through F_d and controlling each component spectrally.
3.1 Warm Up: A graphical matrix M_U is indexed by disjoint vertex sets and assigns each entry the Fourier parity function induced by an injective map of a shape graph U.These matrices provide the building blocks for spectral analysis.
3.1 Warm Up: The warm-up decomposes the matrix into graphical matrices and charges negative eigenvalues against appropriate diagonal structures determined by matchings.Perfect matchings use a literal diagonal matrix, while smaller matchings require a collapsed diagonal matrix.
3.2 The Main Analysis: Vertex-disjoint paths and minimal vertex separators generalize matching size as the combinatorial parameter controlling graphical-matrix norms and the charging argument.Menger’s theorem identifies the maximum number of disjoint paths with the size of a minimal separator.
3.2 The Main Analysis: For ω < n^1/2−ε, coefficient decay enables the proof to bound each higher component Q_i between −D^8d and D^8d, completing positivity.The stated bounds are Q_i ⪯ D^8d and Q_i ⪰ −D^8d for i > 1.

4 Preliminaries

This section fixes notation for graphs, cliques, Fourier representations, separators, and degree-d pseudoexpectations used in the Sum-of-Squares analysis.

Sum of Squares preliminaries: A degree-d pseudoexpectation is a linear operator on multilinear polynomials of degree at most d, normalized by Ẽ[1] = 1 and used to impose polynomial constraints.The degree-d SoS algorithm optimizes an objective over degree-d pseudoexpectations satisfying the given constraints.
Notation: For a graph G, C_q is the collection of q-cliques, C_≤q contains cliques of size at most q, and empty sets and singletons count as cliques.The full clique collection is denoted C(G).
Notation: G(n, 1/2) denotes graphs on [n] whose edges are included independently with probability 1/2.The graph is also represented using independent {−1, 1}-valued edge variables.
Graph preliminaries: A minimal vertex separator is a smallest vertex set intersecting every path between vertex sets I and J.If I and J intersect, every separator contains their intersection.
Graph preliminaries: Menger’s theorem equates the maximum number of vertex-disjoint paths between I and J with the size of a minimal vertex separator.This connection is used later in the positivity analysis.
Fourier preliminaries: Every graph function has a Fourier-polynomial representation in edge variables, with parity functions forming an orthonormal basis under the G(n, 1/2) inner product.For an edge set W, χ_W is the corresponding parity function.

5 The Pseudo-expectation

The paper constructs a pseudo-expectation using low-degree graph and clique-variable polynomials, with coefficients fixed by pseudocalibration to the planted distribution. It then proves that this operator approximately satisfies the SoS constraints and is positive semidefinite with high probability.

Pseudocalibration: Pseudocalibration requires the calibration identity to hold for every function that is low degree in both graph indicators and clique variables.This computational analogue of Bayesian calibration essentially determines the pseudo-distribution.
Definition and parameters: The construction targets a planted clique of size ω = n^1/2−ε and uses degree d and truncation degree τ satisfying Cd/ε ≤ τ ≤ (ε/C) log n.The eventual choice d = (ε/C)^2 log n yields ε = Ω((d/log n)^1/2).
Definition and parameters: The pseudo-expectation is defined through multilinear moments ˜E[xS] for vertex sets S of size at most d.Each moment is represented as a polynomial in the graph’s edge indicators, truncated according to τ.
Constraint satisfaction: ˜E[1] = 1 ± n−Ω(ε) and ˜E[Σ_i x_i] ≈ ω with high probability.These estimates provide normalization and the intended clique-size objective.
Constraint satisfaction: ˜E[xS] = 0 for every set S of size at most d that is not a clique in G, with probability 1.Thus the pseudo-expectation respects the clique support constraints.
Positive semidefiniteness: With high probability, the associated moment matrix is positive semidefinite, completing the construction of a valid degree-d pseudo-distribution after normalization.The proof uses an approximate factorization M = LQ0L† + “error” and spectral bounds on its components.

6 Approximate Factorization of the Moment Matrix

The moment matrix is analyzed by decomposing graph-dependent Fourier terms into ribbons and factoring each ribbon around its leftmost and rightmost minimum vertex separators. This yields a structured approximate factorization whose pieces support the later positive-semidefiniteness argument.

Ribbon decomposition: Ribbons are graph structures with distinguished endpoint sets I and J that arise in the Fourier decomposition of moment-matrix entries.Their vertex sets may include isolated vertices and I and J may intersect.
Canonical factorization: Each ribbon is canonically partitioned into left, middle, and right subribbons using its leftmost and rightmost minimum vertex separators.The edge sets are disjoint and satisfy χR = χWℓ·χWm·χWr.
Canonical factorization: The factorization preserves separator structure even when the leftmost and rightmost separators intersect.Intersection vertices can appear in all three pieces, while edge sets remain pairwise disjoint.
Canonical factorization: The canonical factorization is characterized by separator conditions, reachability constraints, degree conditions, and prescribed intersections among the three subribbons.Lemma 6.6 establishes the equivalence between these conditions and canonical factorization.
Connection to PSDness: With high probability, Q0 ⪰ D and every Qi for i ∈ [1, 2d] satisfies corresponding diagonal domination bounds.These estimates feed into the final PSDness proof.

7.1 Ribbons and Spectral Norms

The paper introduces graphical matrices to capture permutation-invariant ribbon contributions and bounds their spectral norms using the combinatorial structure of their shapes. The key structural parameter is separator size, generalizing matching size.

Ribbon shapes: A ribbon’s shape records its graph structure and the distinguished endpoint sets up to renaming of vertices.The shape also specifies the intersection pattern of the endpoints.
Graphical matrices: Graphical matrices aggregate all ribbons with a fixed shape and are designed as minimal permutation-invariant matrices of the random graph.A single-edge shape recovers the standard ±1 adjacency matrix.
Spectral norm bounds: For a shape U with t = O(log n) vertices, p vertex-disjoint paths between distinguished endpoints, and no isolated internal vertices, Lemma 7.8 supplies a high-probability spectral-norm bound.The bound depends on t, the endpoint structure, and the path count.
Spectral norm bounds: The graphical-matrix bound generalizes the adjacency-matrix spectral estimate, giving √n poly log(n), tight up to a polylogarithmic factor.The adjacency matrix corresponds to a two-vertex shape with one connecting edge.

7.2 PSDness for Q0—Proof of Lemma 7.1

The proof establishes PSDness of Q0 and controls the remaining Qi and error terms by decomposing them according to ribbon shapes and bounding their contributions through separator-based spectral estimates.

PSDness of Q0: Q0 is compared against a diagonal matrix D whose entries are 2^(|S| choose 2)/4 for cliques S and zero otherwise.With high probability, Q0 ⪰ D.
PSDness of Q0: The proof splits Q0 into diagonal and off-diagonal blocks and bounds the off-diagonal contribution by grouping terms according to ribbon shape.A union bound over shapes and sizes controls the resulting graphical matrices.
Control of correction terms: Every Qi for i ∈ [1, 2d] is bounded between −D/8d and D/8d with high probability.The argument decomposes Qi into graphical matrices and applies the ribbon spectral-norm lemma.
Improper ribbons: Improper ribbons are controlled by tracking isolated and repeated vertices created by the factorization, together with separator paths that cannot become isolated.In particular, newly isolated vertices lie among overlap vertices, while designated path vertices remain non-isolated.
Error control: The number of nonzero terms for fixed r is at most 2^O(rτ), and τ ≤ (ε/C) log n makes their total contribution negligible compared with 1/τ.This controls the error terms in the approximate factorization.

7.4 L L† is Well-Conditioned—Proof of Lemma 7.3

The section proves that the projected matrix product ΠLΠL†Π is well-conditioned with high probability by separately controlling diagonal and off-diagonal contributions.

ΠLΠL†Π ⪰ Ω(ω/n)^(d+1)·Π with high probability.Here Π projects onto Span{e_C : C ∈ C_≤d}.
Off-diagonal blocks are indexed by row and column set sizes s_l and s_r, and are analyzed through auxiliary graphs with distinguished subsets A and B.The auxiliary graphs impose, among other conditions, that B has no internal edges and is a minimum vertex separator.
The off-diagonal estimates hold with probability 1 − O(n^-99 log n) and are bounded by (ω/n)^(s_r/2)·1/d^4 under the stated parameter assumptions.
The proof decomposes L into diagonal, error, and off-diagonal parts, with the diagonal entries controlled by a small relative error.The decomposition is L = D + E + L_off-diag, with |E(S,S)| ≤ n^-Ω(ε)·(ω/n)^(|S|/2).
Combining the d^2 block bounds using Cauchy-Schwarz yields the claimed matrix inequality.The relevant blocks have norm at most (ω/n)^((s_l+s_r)/2)·d^-4.

7.5 High-Degree Matrices Have Small Norms

The section proves that the sum of high-degree matrices ξ_0 through ξ_2d has extremely small norm with high probability by bounding ribbon coefficients and applying concentration.

∥ξ_0 − … + ξ_2d∥ ≤ n^-16d with high probability.
Every triple of ribbons with nonzero coefficient in ξ_c has total vertex count Θ(τ).This structural restriction implies that coefficients c_T vanish when |T| exceeds Cτ.
Lemma 7.17 gives entrywise bounds |ξ_i(I,J)| ≤ n^-20d with probability 1 − O(n^-100 log n).
For smaller T, the coefficient magnitude is bounded by (ω/n)^(τ/C−Cd) using bounds on ribbon coefficients and the number of nonzero terms.
A union bound over at most n^(2d) entries and all i ≤ 2d converts the entrywise estimates into the Frobenius and operator-norm bound.The proof uses ∥·∥ ≤ ∥·∥_F.

A.1 Calibration of ˜E

This appendix section introduces a Fourier-expansion argument for calibrating the pseudo-expectation operator on low-degree polynomial constraints.

The calibration argument considers real-valued polynomials whose coefficients have degree at most τ in the ±1 edge indicators.
The stated goal is to control the calibrated values of the constant constraint and the sum of variables.The supplied passages identify the polynomial form and Fourier strategy but do not include the complete calibration formulas.
The proof expands the coefficient functions in the Fourier basis and analyzes the resulting terms indexed by subsets S of vertices.

A.2 Concentration Bounds for Linear Constraints

The section develops concentration bounds for low-complexity graph-dependent polynomial quantities using the moment method and symmetry under vertex permutations.

The concentration lemma applies to families of edge subsets invariant under vertex permutations and parameterized by the number of incident vertices.
The moment-method proof bounds contributions by requiring each edge occurrence to appear at least twice, which limits the number of distinct incident vertices.
With high probability, the calibrated constant satisfies Ẽ[1] = 1 ± n^-Ω(ε), while Ẽ[∑_i x_i] = ω·(1 ± n^-Ω(ε)).
Taking ℓ = (log n)^2 and using t ≤ τ ≤ log n yields the needed high-probability concentration estimates.
For τ ≤ (ε/2) log n and ω = n^(1/2−ε), the resulting error is at most n^-Ω(ε).

A.3 Combinatorial Proofs about Ribbons

The section defines a partial order on vertex separators and proves that minimum separators admit unique leftmost and rightmost elements bounding any pair.

Extremal separators: Every ribbon has a unique minimum separator separating I from any other separator, called the leftmost separator; the rightmost separator is defined analogously.
Partial order: The order Q1 ⩽ Q2 means that Q1 separates I from Q2 in the ribbon.
Partial order: Transitivity follows because every path from I to Q3 must meet Q2, then Q1 when Q1 ⩽ Q2.
Partial order: Antisymmetry for minimum separators follows from Menger’s theorem: mutually bounding separators intersect every disjoint I-J path at the same vertex.
Bounding separators: For minimum separators Q1 and Q2, the construction QL = U ∪ WL and QR = U ∪ WR produces separators with QL ⩽ Q1, Q2 ⩽ QR.
Bounding separators: QL and QR are minimum because their sizes sum to at most 2k while each is a separator of size at least k.

B Spectral Norms

The section bounds the spectral norm of a graphical matrix by breaking labeling dependencies and applying a trace-power moment calculation. With high probability, the resulting bound holds simultaneously across all partition components.

Overview: The analysis is attributed to Medarametla and Potechin, with the results restated and proved in the paper’s notation.
Moment calculation: The counting argument uses the structural assumptions that U has p vertex-disjoint paths from A \ B to B \ A and that every vertex outside A ∪ B has degree at least 1.
Proof strategy: The proof uses a dependence-breaking partition of labelings followed by the trace power method.
Dependence breaking: The partition has m = O(2^t · t · log n) components, and each labeling is assigned to a component where the required conditions hold.
Moment calculation: The moment calculation bounds expectations by counting repeated label patterns across 2ℓ copies of vertex-disjoint paths and vertices outside the distinguished sets.
Final bound: Taking ℓ = (log n)^3 yields a simultaneous high-probability bound on all Mk and hence on M, with failure probability at most n^-100 log n.The component-wise threshold is s = 2^t · n^(t-p-r)/2 · (log n)^O(t-r+p).