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

Background

• Planted clique is a central average-case complexity problem with applications ranging from community detection and biology to game theory, property testing, statistics, cryptography, and finance.Brute force succeeds for clique size above c log n, whereas known polynomial-time algorithms work only for ε√n for constant ε>0.Source: §1 · p. 3

Prior work

• The motivation is strengthened by prior evidence that algorithmic hierarchies have limitations, including an LS+ lower bound and progressively stronger SoS lower bounds.SoS is stronger than LS+ in several settings, making its planted-clique limitations particularly significant.Source: §1 · p. 3

Main result

• The result rules out the possibility that constant-degree, polynomial-time SoS algorithms recover planted cliques of size n^ε for fixed ε>0.Earlier bounds left open whether SoS could substantially beat the √n threshold.Source: §1 · p. 3
• The degree d SoS relaxation has integrality gap at least n^1/2−c(d/log n)^1/2 for every d=d(n) and sufficiently large n.For d=o(log n), this gives a nearly tight n^1/2−o(1) lower bound.Source: §1 · pp. 3–4

Proof framework

• The proof introduces pseudo-calibration, a computational-Bayesian framework for constructing SoS pseudo-distributions and clarifying the hierarchy’s limitations.The framework is intended to provide intuition for both negative results and potentially SoS upper bounds, while explaining differences between SoS and LS+.Source: §1 · p. 4

Implications

• The lower bound is most naturally a refutation result, and it also implies failure of objective-value-based decision algorithms and some SoS-based search algorithms.In planted graphs, a high-objective solution can depend only on the random portion and therefore provide no information for rounding to the planted clique.Source: §1 · p. 4

2 Planted Clique and Probabilistic Inference

• Planted clique has weak global variable effects, whereas random 3SAT has strong local effects whose correlations decay exponentially with distance.Revealing that a vertex is outside the planted clique slightly changes beliefs about all neighbors and non-neighbors; in sparse 3SAT, fixing one variable mainly affects nearby variables.Source: §2 · p. 5

2.1 Computational Bayesian Probabilities and Pseudo-distributions

• Computational Bayesian probabilities represent an observer’s uncertainty about graph-determined events, and Sum-of-Squares supplies an internally consistent restricted set of such probabilities.A computationally bounded observer may assign probabilities strictly between zero and one even when the graph information-theoretically determines the clique; the resulting pseudoexpectation need only approximate conditional expectations while maintaining nonnegativity and consistency.Source: §2.1 · pp. 5–6
• Pseudo-calibration requires agreement on all low-degree polynomials in the graph and clique variables, thereby enforcing both strong constraints and weak probabilistic effects.It implies behaviors such as higher clique likelihood for high-degree vertices and adjusted neighbor/non-neighbor probabilities, while essentially determining the pseudodistribution and avoiding the failures of earlier constructions.Source: §2.1 · p. 7, §2.2 · pp. 9–10

2.2 From Calibrated Pseudo-distributions to Sum-of-Squares Lower Bounds

• Theorem 2.3 guarantees a degree d pseudodistribution with high probability when ω ≤ n^(1/2−c(d/log n)^(1/2)).This pseudodistribution satisfies linearity, normalization, Booleanity, clique, size, and positivity constraints, even though typical random graphs contain no clique remotely that large.Source: §2.2 · p. 8

2.3 Proving Positivity

• For degree bounds τ in graph entries and d in clique variables, pseudo-calibration together with degree-τ dependence on G completely determines the low-degree pseudoexpectation map.Fourier analysis then expresses each ˜E_G[x^S] for |S| ≤ d as an explicit low-degree polynomial in the centered adjacency variables.Source: §2.3 · pp. 10–11
• For d = 2, positivity follows from an approximate diagonalization whose error remains spectrally small when ω ≪√n.The moment matrix has one large approximate eigendirection and remaining eigenvalues controlled by the error term.Source: §2.3 · p. 11
• For general d, the proof organizes calibrated polynomials into graph-shape classes, reducing the approximate diagonalization to a constant number of eigenspaces depending on d.Permutation symmetry preserves the relevant inner products, while graph-dependent structure is needed because calibrated values can depend substantially on G.Source: §2.3 · p. 12
• Approximate eigenspace errors cannot be ignored, so the proof recursively diagonalizes each error matrix until its magnitude is sufficiently reduced.This recursive error control is the main technical complication of establishing positive semidefiniteness.Source: §2.3 · pp. 12–13
• Pseudo-calibration guarantees non-negative expected eigenvalues for polynomials low-degree in both G and x.For such polynomials, the relevant quantity is an expected squared pseudoexpectation, which is nonnegative.Source: §2.3 · p. 12

3 Proving Positivity: A Technical Overview

• Because moment-matrix entries are dependent polynomials in the random graph, their spectrum differs from standard independent-entry random matrices, making positive semidefiniteness challenging.The proof therefore uses symbolic factorization, also described as approximate diagonalization.Source: §3 · pp. 13–14

3.1 Warm Up

• The warm-up decomposes the moment matrix into graphical matrices whose spectral behavior is governed by bipartite matching size, then charges negative eigenvalues to matching-dependent diagonal components.Perfect-matchings yield pseudorandom spectral norms, whereas smaller matchings require charging against diagonals obtained by collapsing matching edges.Source: §3.1 · pp. 14–15

3.2 The Main Analysis

• The main analysis replaces matching size with separator size and groups positive diagonal and negative off-diagonal graphical masses, recursively factorizing error terms caused by repeated vertices.Leftmost and rightmost separators organize the decomposition; the resulting matrices Q_i are analyzed through graph shapes and coefficient tradeoffs.Source: §3.2 · pp. 15–18
• For all ω < n^(1/2−ε), rapidly decaying coefficients let the analysis bound each Q_i for i > 1 between −D/8d and D/8d, completing the positivity proof.The remaining error matrices from truncation are negligible, while Q_0 is bounded below by a positive semidefinite matrix D.Source: §3.2 · pp. 17–18

4.1 General Notation

• The paper fixes notation for cliques, multilinear polynomials, indicators, edge-incident vertices, matrix norms, and the G(n, 1/2) random-graph distribution.Cliques include the empty set and all singletons, and G(n, 1/2) samples edges independently with probability 1/2.Source: §4.1 · p. 18

4.2 Graphs

• Graphs are represented by {−1, 1} adjacency variables; under G(n, 1/2), these variables are independent, and graph functions are real-valued functions of them.The section also defines graph multiplication through coordinatewise products and minimal vertex separators.Source: §4.2 · p. 19

4.3 Fourier Analysis

• Any graph function can be represented as a Fourier polynomial in edge variables, with parity functions on edge subsets forming an orthonormal basis under expectation over G(n, 1/2).Source: §4.3 · p. 19

4.4 The Sum-of-Squares Algorithm

• The degree-d Sum-of-Squares algorithm optimizes an objective over degree-d pseudoexpectations satisfying normalization, positivity, and specified polynomial constraints.The paper adopts the pseudoexpectation formulation from Barak and Steurer.Source: §4.4 · pp. 19–20

5 The Pseudo-expectation

• The parameters satisfy Cd/ε ≤ τ ≤ (ε/C) log n, with ω = n^1/2−ε and an eventual choice d = (ε/C)^2 log n.The construction also assumes ε ≥ C log log n / log n for sufficiently large C.Source: §5 · p. 20

5.1 Definition of ˜E

• The pseudo-expectation is specified by multilinear moments that are polynomials in graph-edge indicators, with Fourier coefficients fixed by pseudocalibration to the planted distribution.The construction truncates the relevant Fourier expansion according to the parameter τ.Source: §5.1 · p. 20

5.2 ˜E Satisfies Constraints

• With high probability, ˜E[1] = 1 ± n^-Ω(ε), its total mass is approximately ω, and every moment ˜E[xS] vanishes when S is not a clique.The non-clique vanishing holds with probability 1 for sets S of size at most d.Source: §5.2 · p. 21

5.3 Proof of Main Theorem

• With high probability, the constructed pseudo-expectation is approximately PSD, completing the main technical step needed for the SoS lower bound.The proof combines approximate normalization, clique-support constraints, and the PSD lemma under Cd/ε ≤ τ ≤ (1/C)ε log n.Source: §5.3 · p. 22

5.4 Proof Plan

• The PSD proof reduces to showing that the associated moment matrix M is positive semidefinite, using an approximate factorization M = L Q0 L† + “error”.The factorization is analyzed by controlling positive eigenvalues of Q0 and LL† against the error; Sections 6 and 7 develop these two steps.Source: §5.4 · p. 22

6.1 Ribbons and Vertex Separators

• Ribbons encode the Fourier terms of M(I, J), and minimum vertex separators provide canonical leftmost and rightmost interfaces for separating I from J.The subsets I and J may intersect, and ribbon vertex sets may include isolated vertices.Source: §6.1 · p. 23

6.2 Factorization of Monomials

• The canonical factorization partitions each ribbon into left, middle, and right subribbons, yielding χ_R = χ_Wℓ·χ_Wm·χ_Wr with disjoint edge sets.The left, middle, and right pieces are defined using the leftmost and rightmost separators, and the converse characterization identifies when three ribbons form this canonical factorization.Source: §6.2 · pp. 24–25

6.3 Factorization of Matrix Entries

• The first factorization rewrites entries M(I, J) by grouping Fourier ribbons into left, middle, and right components subject to separator conditions and size bounds.This separates most factorization conditions across the three components, leaving disjointness as the principal coupling condition.Source: §6.3 · pp. 26–27

6.4 Factorization of the Matrix M

• The matrix factorization expresses M using L Q0 L† plus error matrices, with Q0 supported on clique-indexed rows and the large-ribbon error ξ0 intended to have negligible spectral norm.With high probability Q0 ⪰ 0, while the nondisjointness error E0 is not negligible and therefore requires further factorization.Source: §6.4 · p. 27

6.5 Iterative Factorization of E0

• The iterative factorization targets E0 by enlarging ribbons to allow degree-0 vertices and relaxing the middle-ribbon condition from 3 to 3*.Every proper ribbon is an improper ribbon with an empty added vertex set, and E0 is recovered as Ec0 by choosing coefficients that select middle ribbons satisfying the stricter condition 3.Source: §6.5 · p. 28, §6.5.1 · p. 28

6.5.1 The matrix Ec and its factorization

• Separating factorization handles repeated vertices by choosing separators that separate I and J from one another and from those repeats, producing an approximate factorization of Ec with negligible high-probability error ξc.The construction compares the relaxed factorization with a corrected coefficient function c′ and introduces ξc to account for size-bound discrepancies.Source: §6.5.1 · pp. 28–30
• Keeping isolated vertices is essential because otherwise a vertex could appear in multiple ribbon pieces while disappearing from the separating factorization.This would invalidate the multiplicity-based matching argument used in the factorization proof.Source: §6.5.1 · p. 32
• E_c = L Q_c L† − E′_c − ξ_c, with the choice of separating factorization shown not to affect the relevant expression.The error term ξ_c is intended to have negligible norm with high probability, as established later in Section 7.5.Source: §6.5.1 · pp. 31–32

6.5.2 Application to E0 and M

• Applying the factorization recursively for i ∈ [1, 2d] yields M = L(Q0 − Q1 + Q2 − … − Q2d−1 + Q2d)L† − (ξ0 − ξ1 + ξ2 − … − ξ2d−1 + ξ2d).At each step, E_ci−1 is replaced by a structured Q_i term, a new residual E_ci, and an error ξ_i.Source: §6.5.2 · p. 32
• The recursion ends with E_2d = 0 because each separating factorization increases a left or right separator, whose size is at most d, and both become nonempty after the first step.Thus 2d successive increases are impossible: starting from empty separators, the first step increases both sides, leaving too few steps for the required bound.Source: §6.5.2 · pp. 32–33

7 M is PSD

• The matrix M decomposes as M = L(Q0 − Q1 + Q2 − . . . − Q2d−1 + Q2d)L† − (ξ0 − ξ1 + ξ2 − . . . − ξ2d−1 + ξ2d), while Lemma 7.3 gives L(Q0 − . . . + Q2d)L† ⪰ Ω(ω/n)d+1 · Π and, with high probability, ∥ξ0 − . . . + ξ2d∥⩽n−16d.Source: §7 · p. 33

7.1 Ribbons and Spectral Norms

• Graphical matrices encode ribbon structure through a graph shape with distinguished endpoint sets, enabling spectral-norm bounds for matrices arising from the moment-matrix decomposition.The main bound applies to shapes with at most O(log n) vertices, vertex-disjoint paths between distinguished sets, and no isolated non-distinguished vertices; it generalizes the adjacency-matrix norm bound.Source: §7.1 · p. 35

7.2 PSDness for Q0—Proof of Lemma 7.1

• The proof of Lemma 7.1 decomposes Q0 into diagonal and off-diagonal parts, further groups the latter by ribbon shape, and uses Lemma 7.8 plus union bounds to prove Q0 ⪰ D with high probability.For fixed endpoint sizes and ribbon sizes, the argument bounds each shape contribution and then sums over shapes and sizes.Source: §7.2 · pp. 35–36

7.3 Norm Bounds for Qi—Proof of Lemma 7.2

• For every i ∈ [1, 2d], the Qi matrices satisfy the stated two-sided spectral bounds with high probability after decomposition into proper and improper ribbons and application of graphical-matrix norm estimates.Coefficient bounds for improper ribbons, grouping by shape, and union bounds control the contributions across endpoint and ribbon sizes.Source: §7.3 · pp. 36–38

7.3.1 Coefficient Decay in the Factorization: Proof of Lemma 7.10

• The coefficient-decay analysis characterizes how the separating factorization changes a ribbon’s underlying graph using lost paths, separator-size increases, intersections, and newly isolated vertices.These combinatorial quantities are introduced to support the proof of the coefficient bound in Lemma 7.10.Source: §7.3.1 · pp. 38–39
• For fixed r, there are at most 2O(rτ) nonzero terms; when τ ≤ (ε/C) log n for a universal constant C, 2O(rτ) · n−εr ≪ 1/τ for all r ≥ 1.Source: §7.3.1 · p. 42

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

• With high probability, Π L Π L† Π ⪰ Ω(ω/n)^(d+1) · Π, establishing the required conditioning of L L†.The proof controls diagonal and off-diagonal blocks, with each off-diagonal block bounded by (ω/n)^((sℓ+sr)/2) · d^-4.Source: §7.4 · pp. 43–44

7.5 High-Degree Matrices Have Small Norms

• With high probability, the high-degree contribution satisfies ∥ξ0 − . . . + ξ2d∥ ≤ n^-16d.The section sets up ξi as differences of matrices defined from separating factorizations and begins controlling each ξi via Frobenius norms and concentration.Source: §7.5 · pp. 44–45
• Every nonzero ribbon triple in ξc has total vertex count Θ(τ), so Fourier coefficients cT vanish when |T| exceeds Cτ.For smaller T, the coefficient bound is at most (ω/n)^(τ/C−Cd), using the coefficient estimates and the number of nonzero summands.Source: §7.5 · pp. 45–46
• With probability 1 − O(n^−96 log n), the alternating sum ξ0 − . . . + ξ2d has Frobenius and operator norm at most n^−16d.The proof obtains entrywise bounds of n^−20d and applies a union bound over all entries and i ≤ 2d.Source: §7.5 · p. 46

A.1 Calibration of ˜E

• The subsection restates Lemma 5.3 before giving its proof.Source: §A.1 · p. 49
• The polynomial is defined on {0, 1}^n and indexed by subsets S of [n].Source: §A.1 · p. 49
• Its coefficients have degree at most τ when expressed using the ±1 indicators G_e for edges in G.Source: §A.1 · p. 49
• The calibration statement is formulated under expectation over G sampled from G(n, 1/2).Source: §A.1 · p. 49
• The proof begins by expanding the polynomial coefficients in the Fourier basis.Source: §A.1 · p. 49
• The argument represents each coefficient c_S as a real-valued map from graphs G to R.Source: §A.1 · p. 49

Moment method

• The scalar concentration lemma bounds high moments by counting constraint tuples whose associated vertices repeat sufficiently often.The proof shows that moment contributions require repeated appearances, limiting the number of distinct vertices and enabling a combinatorial count.Source: §A.2 · pp. 49–50

Main concentration result

• With high probability, Ẽ[1] = 1 ± n^-Ω(ε) and Ẽ[Σ_i x_i] = ω · (1 ± n^-Ω(ε)).These bounds restate Lemma 5.4 and provide the section’s main concentration conclusion.Source: §A.2 · p. 50

Parameter regime

• For τ ≤ (ε/2) log n and ω = n^1/2−ε, the resulting error is at most n^-Ω(ε).The argument applies the scalar lemma with ℓ = (log n)^2 and uses t ≤ τ ≤ log n.Source: §A.2 · p. 51

• Finally, QL ⩽ Q1 and Q2 ⩽ QR, establishing the bounding property needed for the unique leftmost and rightmost minimum separators.These canonical separators are denoted SL(R) and SR(R), respectively.Source: §A.3 · pp. 51–52
• Minimum vertex separators are partially ordered by Q1 ⩽ Q2 when Q1 separates I from Q2, with transitivity proved by concatenating path-separation arguments.Antisymmetry follows from Menger’s theorem: mutually preceding minimum separators must intersect every disjoint I–J path at the same vertices.Source: §A.3 · p. 51
• For any two minimum separators Q1 and Q2, the construction QL = U ∪ WL and QR = U ∪ WR yields separators bounding both under the partial order.Here U = Q1 ∩ Q2, while WL and WR collect symmetric-difference vertices reachable from I or J without crossing Q1 ∪ Q2; their disjointness ensures both constructions separate I and J.Source: §A.3 · p. 52
• The constructed separators are minimum because their combined sizes cannot exceed 2k, while each separator must have size at least k.Thus, when |Q1| = |Q2| = k, both QL and QR have size exactly k.Source: §A.3 · p. 52

Attribution

• The section’s results are presented as essentially due to Medarametla and Potechin, with proofs rewritten in the current paper’s notation and minor modifications.The section states and proves the results for completeness.Source: B Spectral Norms · p. 53

Lemma 7.8

• The lemma considers a graph U on t≤O(log n) vertices with p vertex-disjoint paths from A\B to B\A and minimum degree at least one outside A∪B.For the associated graphical matrix M(G), the stated result holds with high probability and has dependence on t, r, and p through the displayed bound.Source: B Spectral Norms · p. 53

Moment Calculation

• The spectral-norm estimate then follows by applying the trace power method to each block and controlling moments through the vertex-disjoint paths and label repetitions.The argument bounds ∥M∥ by the sum of the block norms after the dependence-breaking decomposition.Source: B Spectral Norms · pp. 53–54

Breaking Dependence

• The proof first partitions labelings into disjoint classes using independent random partitions so that every labeling is assigned to a class where the required dependence conditions hold.The number of partitions is m=O(2^t·t·log n), established by a union bound over labelings.Source: B Spectral Norms · p. 53

Moment Calculation

• With ℓ=(log n)^3, the proof obtains s=2^t·n^((t−p−r)/2)(log n)^O(t−r+p) and failure probability at most n^−100 log n for each dependence-breaking block.A union bound then gives ∥M_k∥≤s for all blocks with probability at least 1−n^−100 log n, and the argument concludes the spectral-norm bound for M.Source: B Spectral Norms · p. 55