PaperlayerView exact revision on arXiv

Source-linked AI summary

Sum-of-squares lower bounds for planted clique

Raghu Meka, Aaron Potechin, Avi Wigderson

arXiv:1503.06447v1cs.CCcs.DSmath.COmath.PR

TL;DR

The paper addresses the difficulty of finding small planted cliques, for which the best known polynomial-time algorithms handle sizes around √n. It proves average-case lower bounds for SOS via Positivstellensatz degree lower bounds and shows that, with high probability, r-round SOS has a substantial integrality gap for random and planted clique.

  • Problem

    Prior to this work, nontrivial lower bounds for the stronger SOS hierarchy were not known, while the best known polynomial-time planted-clique algorithms handle k = Θ(√n).

    Source: §1.1 · p. 2

  • Method

    The paper proves Positivstellensatz degree lower bounds for clique axioms using a dual certificate whose associated matrix is shown positive semidefinite with high probability.

    Source: §1.3 · p. 4

  • Results

    With high probability, the r-round SOS relaxation has an integrality gap of at least n^(1/2r)/(C_r(log n)^2) for maximum clique, with an additional 1/t factor for planted clique.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    For constant r, the paper’s lower bound rules out SOS handling planted cliques of size n^o(1).

    Source: §1.1 · p. 2

    The proposed dual certificate is not PSD for k roughly O(n^(1/(r+1))), so a different certificate is needed to approach the √n upper bound, even for r = 2.

    Source: §11 · p. 31

Abstract

from arXiv · show

Finding cliques in random graphs and the closely related "planted" clique variant, where a clique of size k is planted in a random G(n, 1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for k ~ sqrt(n). In this paper we study the complexity of the planted clique problem under algorithms from the Sum-of-squares hierarchy. We prove the first average case lower bound for this model: for almost all graphs in G(n,1/2), r rounds of the SOS hierarchy cannot find a planted k-clique unless k > n^{1/2r} (up to logarithmic factors). Thus, for any constant number of rounds planted cliques of size n^{o(1)} cannot be found by this powerful class of algorithms. This is shown via an integrability gap for the natural formulation of maximum clique problem on random graphs for SOS and Lasserre hierarchies, which in turn follow from degree lower bounds for the Positivestellensatz proof system. We follow the usual recipe for such proofs. First, we introduce a natural "dual certificate" (also known as a "vector-solution" or "pseudo-expectation") for the given system of polynomial equations representing the problem for every fixed input graph. Then we show that the matrix associated with this dual certificate is PSD (positive semi-definite) with high probability over the choice of the input graph.This requires the use of certain tools. One is the theory of association schemes, and in particular the eigenspaces and eigenvalues of the Johnson scheme. Another is a combinatorial method we develop to compute (via traces) norm bounds for certain random matrices whose entries are highly dependent; we hope this method will be useful elsewhere.

1 Introduction

The paper establishes average-case lower bounds for SOS on random and planted clique instances, using Positivstellensatz proof-degree lower bounds. Its proof constructs a dual certificate and establishes positive semidefiniteness using association schemes and trace bounds for locally random matrices.

1.1 The problem and main result

  • For planted clique, the best known polynomial-time algorithms handle k = Θ(√n), while the paper frames improving that threshold as an open algorithmic challenge.The planted problem asks to recover a clique hidden in a random G(n, 1/2) graph.Source: §1.1 · p. 2
  • With high probability, the r-round SOS relaxation has a maximum-clique integrality gap of at least n^(1/2r)/(C_r(log n)^2), with an additional 1/t factor for planted clique.The planted-clique bound applies to graphs generated with a planted clique of size t.Source: §1.1 · p. 2

1.2 Background and related work

  • Hierarchy relaxations strengthen with rounds; each r-round relaxation takes n^O(r) time, and the introduction reports no nontrivial lower bounds then known for SOS.The passage positions SOS as stronger than LS+ and SA+ (subject to minor technicalities).Source: §1.2 · p. 3

1.3 Proof systems and SDP hierarchies

  • The proof lower-bounds Positivstellensatz refutation degree for clique axioms, which yields lower bounds for the SOS hierarchy under the stated technical conditions.The paper relates degree-r refutations to SOS infeasibility certification in 2r+Θ(1) rounds.Source: §1.3 · p. 5

1.4 Outline

  • The proof builds a dual certificate and reduces its positive semidefiniteness to matrix analysis using Johnson-scheme eigenspaces and trace bounds for dependent entries.The matrix reduction and expectation-eigenvalue analysis precede a high-probability deviation bound.Source: §1.4 · pp. 6–7

2 Dual certificate for PS(r) refutations of max-clique

The section constructs a dual certificate for clique axioms, extending a symmetric certificate from the complete-graph case. Its positive semidefiniteness yields the stated degree lower bound for random graphs.

2 Dual certificate for PS(r) refutations of max-clique

  • The certificate is defined on multilinear polynomials and extended multilinearly, using the Boolean axioms to reduce individual variable degrees to one.This provides the setup for the paper’s construction of a certificate for the clique axioms.Source: §2 · p. 7

2.1 Complete graph and knapsack

  • For the complete graph, symmetry makes the certificate depend only on set size, following the knapsack approach associated with Grigoriev.Grigoriev’s stated result is that this certificate is PSD for r < k when k < n/2.Source: §2.1 · pp. 7–8

2.2 Certificate for clique axioms

  • The certificate M_G satisfies the clique axioms, and its PSD condition reduces to checking homogeneous multilinear polynomials of degree r.The paper defines M_G on monomials using the number of 2r-clique extensions of each set, then extends it to polynomials.Source: §2.2 · pp. 8–9
  • For k ≤ 2^-cr · (√n / log n)^1/r, the matrix M_G is PSD with high probability over G ← G(n, 1/2).The section says proving this PSD property suffices for its main theorem.Source: §2.2 · p. 10

3 Overview of proof of Theorem 2.5

The proof establishes PSDness of M′ by separating its deterministic expectation, local random variation, and global error. It bounds the expectation’s least eigenvalue and controls the random terms’ norms.

3 Overview of proof of Theorem 2.5

  • M′ is decomposed as E + L + Δ, where E is the expectation, L depends on edges within I ∪ J, and Δ has small-magnitude entries.M′ is formed by filling the zero rows and columns of M; proving M′ PSD suffices for M.Source: §3 · p. 10
  • Johnson scheme results show E is positive definite with a large least eigenvalue, roughly Ω_r(k^r n^r).E is set-symmetric.Source: §3 · p. 10
  • Trace calculations exploit L’s recursive structure to bound its norm by Ck^2r n^(r−1/2) log n.The section describes this as the proof’s most technically intensive part and says it requires combinatorial tools for traces of high powers.Source: §3 · p. 10
  • The global error satisfies ∥Δ∥ < Ck^2r n^(r−1/2) log n, using entrywise concentration and Gershgorin’s circle theorem.The concentration bounds concern the number of cliques in random graphs.Source: §3 · p. 11

4 Preliminaries

The preliminaries fix notation for bounded-degree polynomials, positivstellensatz refutations, and positive semidefinite functionals. They also state matrix and concentration facts used in the proof.

4 Preliminaries

  • P(n, 2r) denotes n-variate polynomials of degree at most 2r, and PS(r) denotes refutations of degree at most r.The paper views functionals on these polynomials as matrices indexed by subsets of [n] of size at most r; under its multilinear-extension convention, PSDness of the functional is equivalent to PSDness of the matrix.Source: §4 · p. 11
  • A functional M is PSD when M(P^2) ≥ 0 for every polynomial P of degree at most r.The notation also uses 1(I) for the indicator vector of a set I.Source: §4 · p. 11
  • The section states Gershgorin’s circle theorem and McDiarmid’s inequality as tools for matrix and concentration bounds.McDiarmid’s inequality is introduced for functions of independent random variables.Source: §4 · pp. 11–12

5 Reduction to PSDness of M′

The section replaces M with a matrix M′ whose entries avoid zero rows and columns. It shows that PSDness of M′ implies PSDness of M.

5 Reduction to PSDness of M′

  • M′ fills in M’s zero rows and columns while controlling entry variance by evaluating entries as if cliques had been added on I and J.This construction avoids zeroing an entire row or column when I or J is not a clique.Source: §5 · p. 12
  • For I and J that are cliques of size r, M′(I, J) equals M(I, J).The equality follows because the entries count clique extensions containing I ∪ J.Source: §5 · p. 12
  • The nonzero part of M is a principal submatrix of M′, so PSDness of M′ implies PSDness of M.The section invokes the fact that a principal submatrix’s smallest eigenvalue is at least the full matrix’s smallest eigenvalue.Source: §5 · pp. 12–13

6 Johnson scheme

The Johnson scheme is the space of set-symmetric matrices, whose entries depend only on the intersection size of their indexing sets. Its commuting matrices share eigenspaces, and the paper uses two bases to analyze their eigenvalues and positive semidefiniteness.

6 Johnson scheme

  • Matrices in the Johnson scheme are set-symmetric: each entry depends only on the intersection size of its indexing sets.The scheme is also a commutative algebra.Source: §6 · p. 13
  • The D-basis consists of disjointness-style matrices that span the Johnson scheme.The matrices in this basis commute with one another.Source: §6 · p. 13
  • The P-basis gives a basis of positive semidefinite matrices for the Johnson scheme.Each P_t is positive semidefinite, and matrices in the scheme can be expressed as linear combinations of the P_t matrices.Source: §6 · pp. 13–14
  • Because Johnson-scheme matrices commute, they are simultaneously diagonalizable and share the eigenspaces used to estimate their eigenvalues.The paper uses classical association-scheme results, especially for the Johnson scheme.Source: §6 · p. 14

7 PSD’ness of the expectation matrices

The section establishes positive semidefiniteness for both the expectation matrix M and the matrix E actually used in the proof. For E, it also gives a positive lower bound on the minimum eigenvalue.

7 PSD’ness of the expectation matrices

  • The expectation matrix EM is positive semidefinite for r < min(k, n − k).The section identifies EM as a scalar multiple of M_Gr and also gives a simpler proof for a restricted range of r.Source: §7 · p. 15

7.1 PSD’ness of E

  • E is positive semidefinite with minimum eigenvalue 2^{-O(r^2)}k^r n^r.The proof writes E as a positive linear combination of the positive semidefinite P_t matrices.Source: §7 · p. 15, §7.1 · pp. 16–17

8 PSD’ness of dual certificate

The proof certifies the dual-certificate matrix by establishing that M′ is positive definite with high probability, then relating this to the main lower bounds. It decomposes M′ into an expectation matrix, a locally random matrix, and a global error matrix, and controls the latter two in norm.

8 PSD’ness of dual certificate

  • With high probability, M′ is positive definite for k < 2^{-cr}(√n/log n)^{1/r}.The proof uses this technical lemma to show that the dual-certificate matrix is positive semidefinite with high probability.Source: §8 · p. 17

8.1 Decomposition of M′

  • M′ is decomposed as E + L + Δ, with E its expectation, L depending locally on edges within I ∪ J, and Δ a global error with small entries.The proof then bounds the norms of L and Δ.Source: §8.1 · pp. 17–18

8.2 Bounding the norm of the locally random matrix L

  • By exploiting L’s recursive structure and careful trace calculations, the proof establishes ∥L∥ is 2^{O(r^2)}k^{2r}n^{r−1/2} log n, its most technically intensive part.Source: §8.1 · p. 18
  • A multiplicative n^{-1/2} improves on the entrywise 2^{a^2}n^a bound for the auxiliary matrix R_a.The proof decomposes L by intersection sizes and uses the recursive structure of M′.Source: §8.2 · pp. 18–19

8.3 Bounding the norm of the global error matrix Δ

  • The global error Δ is controlled by bounding its entries and using concentration of deg_G(I ∪ J) conditioned on I ∪ J being a clique.The section states a high-probability spectral-norm bound for Δ.Source: §8.3 · pp. 20–21

8.4 Putting things together

  • Combining the bounds on L and Δ with E’s positive eigenvalue margin shows M′ has positive minimum eigenvalue in the stated range of k.The resulting positive-semidefiniteness results yield the paper’s PS(r)-refutation lower bound and, by standard arguments, Theorems 1.1 and 1.2.Source: §8.4 · p. 22

9 Bounding norms of locally random matrices

The section develops trace-based norm bounds for locally random matrices, extending the counting argument to dependent entries. Constraint graphs and independence-breaking cycles control which trace terms can have nonzero expectation, allowing the bounds to be applied to the matrices used in the proof.

9 Bounding norms of locally random matrices

  • The trace method bounds matrix norms through traces of high powers, reducing the task to counting terms with nonzero expectation.For the independent-entry case a = 1, the section describes the familiar O(√n) norm bound; the resulting trace-method bound is weaker by a logarithmic factor than but sufficient for the paper's purposes.Source: §9 · pp. 22–23, §9.1 · p. 24

9.1 Constraint graphs

  • Theorem 9.1 converts restrictions on nonzero trace terms and bounds on their expectations into probabilistic bounds on the trace quantity and, in applications, matrix norms.Its assumptions constrain the union size of the sets indexing each term and bound each term's expected value.Source: §9.1 · p. 23
  • A constraint graph connects intersecting sets, and its connected components bound the size of their union, helping count terms with nonzero expectation.Lemma 9.5 relates the union size to the sum of set sizes and the number of connected components.Source: §9.1 · p. 24

9.2 Bounds on ||Ra||

  • For the dependent entries of R_a, a trace term can have nonzero expectation only when every product edge lies in an independence-breaking cycle.The section uses 3- and 4-cycles in an auxiliary graph to represent repeated edge dependencies; Lemma 9.17 bounds the number of connected components among constraint edges by q + 1.Source: §9.2 · p. 27
  • The proof applies Theorem 9.1 to obtain probabilistic norm bounds for R_a with y = 1 and z = 1, using entry magnitudes at most 2a^2 (hence B = 2a^2), for n ≥ 10 and ε ∈ (0,1).Source: §9.2 · p. 29

10 Concentration bounds for number of cliques and degG(I)

This section establishes concentration results for clique counts and for the number of common neighbors that extend a set I. It conditions on I being a clique and uses concentration of the common-neighbor set to analyze degG(I).

10 Concentration bounds for number of cliques and degG(I)

  • Theorem 10.3 gives a concentration bound for the number of a-cliques in a random graph.The section introduces N_a(G) as the number of a-cliques and gives a direct proof using Theorem 9.1.Source: §10 · p. 29
  • Conditioned on I being a clique, degG(I) counts cliques of size 2r − i among vertices adjacent to every vertex in I.The proof uses the independence of edges within the common-neighbor set from edges involving I, then applies the clique-count concentration result.Source: §10 · p. 30
  • The proof controls the size of the common-neighbor set using independent vertex indicators and applies McDiarmid’s inequality to the resulting function.Changing one coordinate changes that function by at most n^(2r−i−1).Source: §10 · pp. 30–31

11 Conclusion and future work

The paper proves lower bounds for maximum clique on random G(n, 1/2) graphs in the SOS hierarchy and Positivstellensatz proof system. It identifies both possible extensions of its techniques and an open gap in the planted-clique bounds.

11 Conclusion and future work

  • The paper establishes a lower bound for maximum clique on random G(n, 1/2) graphs in the SOS hierarchy and Positivstellensatz proof system.The authors suggest that the PSD property of their matrix M and their association-scheme and locally-random-matrix arguments may be useful for other problems, including densest subgraph.Source: §11 · p. 31
  • For r rounds of SOS on planted clique, the gap between the current upper and lower bounds remains open, and the authors ask whether constant rounds can beat the square-root barrier.They report that Kelner12 showed their dual certificate M is not PSD for k roughly O(n^(1/(r+1))), so approaching the upper bound even for r = 2 requires a different certificate.Source: §11 · p. 31

12 Hierarchy Gaps and Positivstellensatz Refutations

The section relates the SOS relaxation for maximum clique to Positivstellensatz refutations through dual certificates and feasible vector solutions. Applying the preceding bounds gives high-probability lower bounds on relaxation values for random and planted graphs.

12 Hierarchy Gaps and Positivstellensatz Refutations

  • The section notes that PS(r)-refutations are typically more robust and stronger than the hierarchy formulations.It refers readers to [OZ13] for a detailed discussion.Source: §12 · p. 34
  • A dual certificate for the clique axioms yields a feasible vector solution to the r-round SOS relaxation with value k.The relaxation is stated using vectors U_S indexed by subsets S of size at most r, and its optimization can be done by semidefinite programming.Source: §12 · pp. 34–35
  • With high probability, the r-round SOS relaxation for maximum clique on G(n, 1/2) has value at least n^(1/2r)/(C^r(log n)^(1/r), while the integral value is (2 + o(1)) log2 n.The proof derives the relaxation lower bound from the preceding lemma and the dual certificate for the clique axioms.Source: §12 · p. 35
  • For G(n, 1/2, t), the planted-graph relaxation has the same stated lower bound with high probability, while the integral value is t.The proof uses monotonicity of the relaxation value when edges are added.Source: §12 · p. 36
Loading 1503.06447v1…