title: Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
authors: Afonso S. Bandeira Jess Banks Dmitriy Kunisky Cristopher Moore Alexander S. Wein
text: 
  
  Nonmagnetic ground state, Crystal field effects and Heavy-fermion behaviour in the Remeika Phase: Pr_3Ir_4Ge_13
      [
      Received XXX 2019 / Accepted XXX 2020
  ===============================================================================================================
  
  
  
  empty
  
  
  
  
  We study the problem of efficiently refuting the k-colorability of a graph, or equivalently certifying a lower bound on its chromatic number. We give formal evidence of average-case computational hardness for this problem in sparse random regular graphs, showing optimality of a simple spectral certificate. This evidence takes the form of a computationally-quiet planting: we construct a distribution of d-regular graphs that has significantly smaller chromatic number than a typical regular graph drawn uniformly at random, while providing evidence that these two distributions are indistinguishable by a large class of algorithms. We generalize our results to the more general problem of certifying an upper bound on the maximum k-cut. 
  
  This quiet planting is achieved by minimizing the effect of the planted structure (e.g. colorings or cuts) on the graph spectrum. Specifically, the planted structure corresponds exactly to eigenvectors of the adjacency matrix. This avoids the pushout effect of random matrix theory, and delays the point at which the planting becomes visible in the spectrum or local statistics. To illustrate this further, we give similar results for a Gaussian analogue of this problem: a quiet version of the spiked model, where we plant an eigenspace rather than adding a generic low-rank perturbation.
  
  Our evidence for computational hardness of distinguishing two distributions is based on three different heuristics: stability of belief propagation, the local statistics hierarchy, and the low-degree likelihood ratio. Of independent interest, our results include general-purpose bounds on the low-degree likelihood ratio for multi-spiked matrix models, and an improved low-degree analysis of the stochastic block model. 
  
  
  
  
  
  
  
  
  
  
  § INTRODUCTION
  
  
  Assuming the widely believed ≠ hypothesis, many combinatorial problems in graphs are known to be computationally hard. Prominent examples from graph theory and network science include finding large cliques or independent sets, clustering or maximizing cuts, and finding vertex colorings or computing chromatic numbers. Fortunately, the worst-case computational difficulty of many of these problems appears to not be predictive of their feasibility in typical graphs, motivating the study of forms of average-case complexity for many of these problems. Many remarkable examples exist dating back to at least the work of Karp and others in the mid 70s <cit.>,[See also Karp's lecture on the occasion of his Turing Award <cit.>.] they include the problem of vertex colorings <cit.> in random graphs, the related problem of finding the largest independent set[Recall that the set of nodes of the same color in a vertex coloring is an independent set.] (or, equivalently, clique) and many others <cit.>. In both of these problems, for certain natural distributions of random graphs, a multiplicative gap of 2 is identified between the typical optimal solution and the solution found by the best known polynomial-time algorithm <cit.>, and improving over this has since been a standing open problem. Motivated by this question, Kucera <cit.> and Alon et al. <cit.> studied random graph models with planted structures (either a large independent set or clique, or a coloring with an unusually small number of colors) and investigate when such structures are easy to detect. Foreshadowing to what follows, we point out that the existence of a planted structure that cannot be detected efficiently implies that that it is impossible to efficiently refute the existence of such a structure in the underlying unplanted model. In this paper we will focus on the problem of computing the chromatic number, and the related problem of understanding the size of the largest k-cut. The random graph model throughout is the uniform distribution over d-regular graphs on n nodes.
  
  
  
    
  Refuting colorability.
  For an integer k ≥ 1, a graph G = (V,E) is k-colorable if there exists an assignment σ V → [k] of “colors” to the vertices such that σ(i) σ(j) for every edge (i,j) ∈ E. The chromatic number χ(G) of G is defined as the minimum value of k for which G is k-colorable.
  
  A random d-regular graph  on n vertices (we will write random variables in bold-face font throughout the paper) is known to have a typical chromatic number χ() ∼1/2d/log d (see, e.g., <cit.> and references therein) in the double limit n →∞ followed by d →∞, where f ∼ g denotes f/g → 1.
  The problem we will study is that of algorithmically refuting the k-colorability of a graph, which we define in Section <ref>.
  Informally speaking, an algorithm that refutes k-colorability provides an efficiently-verifiable proof that G is not k-colorable.
  As a simple example, an algorithm exhibiting a (k + 1)-clique refutes k-colorability.
  More generally, one may encode a k-coloring as a collection of boolean variables satisfying certain logical relations depending on G, and refute coloring by deriving a contradiction from those axioms. 
  
  
  We will provide evidence that the refutation problem is computationally hard when  is a uniformly random d-regular graph. The proof strategy is to construct a different distribution over d-regular graphs whose typical chromatic number is χ()∼1/2√(d), and to argue that this distribution is computationally hard to distinguish from a uniformly random d-regular graph (whose chromatic number is instead χ() ∼1/2d/log d)—we think of this new distribution as having a computationally-quiet planting[This terminology is inspired by the notion of quiet planting from prior work <cit.>, although our notion is somewhat different.] of a coloring with few colors. We will see below that the value 1/2√(d) coincides with a simple spectral bound on χ() for  uniformly random, and so our result is a tight computational lower bound on refutation algorithms.
  The formal evidence for computational hardness used in this paper is threefold: we provide consistent pieces of evidence based on (i) the Kesten–Stigum threshold for the belief propagation message-passing algorithm, (ii) the Local Statistics semidefinite programming hierarchy, and (iii) the low-degree likelihood ratio for an analogous Gaussian model.
  
  
  
  
    
  The spectral refutation.
  Instead of just refuting k-colorability, we will consider the more general task of refuting the existence of large k-cuts in a graph.
  We define the fractional size of the largest such cut as
  
      _k(G) max_σ : V → [k]|{(u, v) ∈ E: σ(u) ≠σ(v)}|/|E|∈ (0, 1].
  
  Intuitively, _k(G) describes how close G is to being k-colorable, as the cut counts the fraction of polychromatic edges under the coloring σ.
  _k(G) is non-decreasing in k, and for any k, G is k-colorable if and only if _k(G) = 1; therefore, the chromatic number is given by
  
      χ(G) = min{k: _k(G) = 1} = 1 + max{k: _k(G) < 1}.
  
  
  Accordingly, upper bounds on _k away from the maximum value of 1 yield lower bounds on the chromatic number.
  This task is often called certifying a bound on the optimization problem _k.
  The relations (<ref>) show how certifying such a bound in turn refutes colorability. In fact, Hoffman's early work <cit.> proposed a technique for any d-regular graph G that gives, when rephrased in our notation, a refutation of colorability by bounding _k via the minimum eigenvalue λ_min(A_G) of the adjacency matrix A_G of G.
  Namely, Hoffman showed that for any d-regular graph G,
  
      _k(G) ≤k - 1/k(1 + -λ_min(A_G)/d).
  
  (Note that λ_min(A_G) ≤ 0 since (A_G) = 0.) A short proof of (<ref>) will be given in Section <ref>.
  We note that k - 1/k is the expected value of the objective of (<ref>) when σ V → [k] is chosen uniformly at random, so expressions like the right-hand side of (<ref>) should be viewed as expressing a factor of “gain” over this value. For  a uniformly random d-regular graph on n vertices, whose law we denote 𝒢_n, d, a theorem due to Friedman
  <cit.> states that λ_min() = -2√(d-1) + o(1) with high probability[Here and throughout, o(1) pertains to the limit n →∞ with d fixed. We say that an event occurs with high probability (w.h.p.) if it has probability 1-o(1).] for any fixed d ≥ 3.
  This implies that when ∼_n, d, Hoffman's spectral approach with high probability certifies the upper bound
  
      _k() ≤k - 1/k(1 + 2√(d - 1)/d + o(1)).
  
  This in turn translates to a lower bound on the chromatic number of χ() ≥ (1 - o_d(1)) 1/2√(d), where o_d pertains to the double limit n →∞ followed by d →∞ (see Section <ref>).
  
  Equipped with this direct analysis of a simple technique, the natural question arises: can any polynomial-time algorithm produce a bound that, like Hoffman's, is valid for any graph G, but is typically tighter for ∼_n, d? 
  Most prior work on this question has studied bounds provided by a semidefinite program computing the Lovász ϑ function, which, as shown by <cit.>, is equivalent to the degree-2 sum-of-squares relaxation of _k(G).
  The work <cit.> and a later, more precise analysis by <cit.> showed that, with high probability when ∼𝒢_n, d, this relaxation certifies a bound still no better than
  
      _k() ≤k - 1/k(1 + 2√(d - 1)/d + 2√(d - 1) - o(1)) = k - 1/k(1 + 2√(d - 1)/d - O_d(1/d)).
  
  Note that (<ref>) matches the spectral bound (<ref>) in the double limit n →∞ followed by d →∞. No polynomial-time certifier is known to asymptotically improve upon this bound. It appears plausible, then, that the spectral bound (<ref>) is an optimal efficiently-computable certificate on _k() for ∼_n, d.
  In this work, we will argue that this is indeed the case.
  
  
  
  
    
  Detecting a planted k-cut.
  
  The following line of reasoning will be central to this work: to prove computational hardness of a refutation problem, it is sufficient to construct a computationally-quiet planted distribution (e.g. <cit.>). To illustrate the meaning of this, suppose our goal is to show computational hardness of refuting (w.h.p.) k-colorability of a graph drawn from _n,d. Suppose we are able to construct a planted distribution 𝒫 over d-regular graphs such that (i) a typical graph drawn from 𝒫 is k-colorable, and (ii) 𝒫 is computationally quiet in the sense that no polynomial-time algorithm can distinguish (w.h.p.) between a sample from 𝒫 and a sample from _n,d. It then follows that no polynomial-time algorithm can refute k-colorability in _n,d, because if such a refutation algorithm were to exist, it must succeed w.h.p. on _n,d and must fail w.h.p. on 𝒫, thus providing a solution to the distinguishing problem. More generally, to show hardness of certifying an upper bound on the maximum k-cut, we need a planted distribution for which there exists a large k-cut.
  
  As discussed in <cit.>, a natural planted distribution with a large k-cut is a d-regular variant of the popular stochastic block model (SBM). To sample a graph from this d-regular distribution, which we will denote 𝒢^sbm_n, d, k, η, first sample a balanced labelling : [n] → [k] uniformly at random (balanced means that |^-1(i)| = n/k for every i ∈ [k]), and then choose  uniformly among d-regular graphs conditional on the event[For now, we will not consider the integrality conditions on the parameters (n, d, k, η) that this implies, although these types of considerations will be important later.]
  
      |{(u,v) ∈ E: (u) ≠(v)}|/|E| = k-1/k(1 - η).
  
  Note that this ensures _k() ≥k-1k(1 - η), since the planted partition  witnesses a k-cut with that fraction of bichromatic edges. We will mostly be concerned with the disassortative regime of this model where η∈ [-1k-1,0], and the planted k-cut  is larger than a typical one; for instance, when η = -1k-1 and the planted cut includes every edge, we have the well-studied planted coloring model.
  
  The relevance of this distribution to certifying bounds on _k for ∼_n, d is as follows: if an algorithm can with high probability over _n,d certify that _k() < k-1k(1 - η), then (as discussed above) it is simple to build another testing (or detection) algorithm that distinguishes between ∼_n, d and ∼^sbm_n, d, k, η with high probability. The advantage of taking this point of view is that there is a rich literature, originating in heuristic methods from statistical physics, that has provided a great deal of evidence that polynomial-time testing between _n, d and ^sbm_n, d, k, η is impossible below the Kesten–Stigum threshold, i.e., when
  
      d < d_KS^ sbm = d_KS^ sbm(η) 1/η^2 + 1.
  
  We will refer to this claim as the SBM conjecture. Polynomial-time algorithms are known to succeed when d > d_KS^ sbm <cit.>. While proving such a conjecture seems to be beyond the reach of current techniques (even under an assumption such as ≠), various forms of concrete evidence have been given (either for the d-regular SBM and other variants). These include results on stability of belief propagation <cit.>, the local statistics hierarchy <cit.>, and the low-degree likelihood ratio <cit.>. We will discuss all of these methods further in Section <ref>.
  
  Rearranging (<ref>) we find that, conditional on the SBM conjecture, the above argument implies that when ∼_n, d, no polynomial-time algorithm can certify with high probability a bound stronger than
  
      _k(G) ≤k - 1/k(1 + 1/√(d - 1) - o(1)).
  
  
  Comparing this to (<ref>) and (<ref>), we see a discrepancy between the best known certification algorithms and the above hardness result. For large d, this discrepancy amounts to a factor of 2 in the “gain” term. This begs the question of whether better certification algorithms exist, or whether the hardness result can be improved. We will see below that it is the latter.
  
  
  
  
  
    
  A quieter planting.
  
  Our main contribution is to show an improved hardness result by using a “better” planted distribution. The superior planted distribution is the following more rigid version of the SBM.
  
  
  
      The equitable stochastic block model (eSBM), denoted _n, d, k, η^ eq, is the probability distribution over d-regular graphs on n vertices sampled as follows: first, choose a uniformly random balanced partition : V → [k]. Then, letting
      
      M = η𝕀_k + 1 - ηk_k
  
      (where 𝕀_k  and _k are the k× k identity and all-ones matrices, respectively), for each i ∈ [k] place a random dM_i,i-regular graph on the color class ^-1(i), and for each i<j ∈ [k] place a random bipartite dM_i,j-regular graph between ^-1(i) and ^-1(j). This model is only defined when k|n, dM is a nonnegative integer matrix, and dM_i,in/k is even[This last condition ensures that it is possible to place a dM_i,i-regular graph on n/k vertices.] for all i.
  
  
  As in ^sbm_n,d,k,η, the planted cut  has fractional size k-1k(1 - η), and we will again restrict to the disassortative case η∈ [-1/k-1,0]. This model is discussed in <cit.>, where it is alternatively called the “regular block model.” We instead follow <cit.> in using the term “equitable,” so as to differentiate it from the standard d-regular variant of the SBM discussed in the previous section.
  
  Using some of the same methods that provide concrete evidence for the SBM conjecture—namely stability of belief propagation and the local statistics hierarchy—we will show that the equitable SBM appears to exhibit a different computational threshold from the standard SBM. Specifically, we conjecture that no polynomial-time algorithm can distinguish (w.h.p.) between _n,d and _n, d, k, η^ eq when
  
      d < d_KS^ eq = d_KS^ eq(η) 2/η^2(1 + √(1 - η^2)).
  
  
  We will state a formal version of this “eSBM conjecture” later (Conjecture <ref>), which actually pertains to a slightly “noisy” version of the equitable block model. We remark that when k is large, η must be close to zero (in the disassortative case), and so we have approximately d^ eq_KS≈ 4d^ sbm_KS.
  
  Repeating our earlier argument for hardness of certification, with the eSBM in place of the SBM, yields the following corresponding result: conditional on the eSBM conjecture, no polynomial-time algorithm can certify a better bound than
  
      _k() ≤k - 1/k(1 + 2√(d - 1)/d - o(1))
  
  when ∼_n,d, which matches the spectral bound (<ref>). However, we have ignored an important caveat here: the equitable block model only exists when the parameters (n,d,k,η) satisfy certain integrality conditions. For this reason, our actual lower bound (Theorem <ref>) is sometimes weaker than (<ref>) would suggest; see Section <ref> for discussion. When d ≫ k^2, the integrality conditions are negligible and we obtain a tight lower bound, essentially matching (<ref>). Another setting where we obtain tight results is for the problem of refuting colorability (or more accurately, near-colorability) in the double limit n →∞ followed by d →∞, which is discussed in Remarks <ref> and <ref>. This corresponds to the choice η = -1/k-1. Here, when ∼_n,d, the following results hold asymptotically: the true value of χ() is 1/2d/log d, the spectral approach certifies a lower bound of 1/2√(d) on χ(), the basic SBM planting implies hardness of certifying a lower bound better than √(d), and the improved eSBM planting implies hardness of certifying a lower bound better than 1/2√(d) (which is tight, matching the spectral bound).
  
  
  
  
  
    
  Why is the equitable SBM quieter?
  
  Here, we give some intuition for why the equitable model is a good quiet planting. For the sake of illustration, it helps to consider the simple rank-1 Wigner spiked matrix model: = η^⊤ + where η > 0 (the signal-to-noise ratio), = 1 (the planted “signal,” drawn from some prior), and  (the “noise”) is a GOE matrix, i.e., a symmetric matrix with 𝒩(0,1/n) entries (see Definition <ref>). For large n, the eigenvalues of  follow the semicircle law and are contained in the interval [-2,2]. For 1 < η < 2, a surprising “pushout” effect occurs: although the planted signal  has quadratic form ^⊤≈η < 2, its presence causes there to exist some other unit vector  achieving ^⊤≈η + 1/η > 2 <cit.>; as a result, simply checking the largest eigenvalue allows one to distinguish  from . Even though the signal  is “small”, the vector  (which is the leading eigenvector of ) is able to achieve a “large” quadratic form by correlating nontrivially with both the signal  and the noise . The main result of <cit.> can be interpreted as giving a “quieter” way to plant the signal “orthogonal to the noise” with no pushout effect, i.e., ^⊤≈ 2 and the maximum eigenvalue of  is ≈ 2.
  
  It turns out that a similar effect is at play in the SBM. Here the minimum eigenvalue of the adjacency matrix  of a random d-regular graph converges to λ_min - 2√(d-1). As will be made clear in Section <ref>, the SBM is in some sense analogous to the spiked Wigner model with multiple planted vectors, namely k “coloring vectors” _i for i ∈ [k], that encode the planted labelling  as follows: (_i)_u = c(k ·(u) = i - 1), where c is chosen so that each _i = 1. Planting a k-cut of value k-1k(1+|η|) via either the SBM or eSBM has the effect that all planted coloring vectors achieve a small quadratic form: _i^⊤_i ≈ -d |η|. In the SBM there is a pushout effect similar to the spiked Wigner model, whereby an eigenvalue less than λ_min can be created even when d|η| < |λ_min| (see <cit.> for results when the degree grows slowly with n). The eSBM, however, has the property that each coloring vector _i is an eigenvector. In particular, the subspace spanned by {_i}_i∈[k] is orthogonal to the other eigenvectors, which are thus unaffected by the planted structure. As a result, there is no pushout effect in the eSBM, allowing for a larger k-cut to be planted without disrupting the minimum eigenvalue.
  
  An alternative viewpoint is that the standard plantings (the spiked Wigner model or SBM) pick a random solution (e.g., a cut) and then condition on that particular solution having the desired value. In contrast, the quieter plantings are perhaps more similar to conditioning on the event “there exists a solution having the desired value.”
  
  
      
      The fact that the coloring vectors _i are eigenvectors of the eSBM can actually be exploited to give a polynomial-time algorithm for distinguishing _n,d from _n, d, k, η^ eq for any settings of the parameters. See, for example, <cit.> for some discussion of such algorithms. For this reason, it is crucial that our eSBM conjecture (Conjecture <ref>) adds a small amount of noise to the graph in order to “defeat” these types of algorithms. We discuss this issue further in Section <ref>.
  
  
  
  
    
  The case k = 2: large cuts in _n, d.
  
  Here, we briefly discuss the specific case k = 2, which is better understood in the existing literature.
  In this case, _2(G) is merely the fraction of edges crossing the largest cut of G, and thus up to this scaling is the solution to the well-known max-cut problem. Equivalently, letting A_G be the adjacency matrix of G, we have _2(G) = 1/2(1 + 1/2 |E|Γ_2(A_G)) where
  
      Γ_2(A)  -min_x ∈{± 1}^n x^⊤ A x ≥ 0.
  
  When ∼_n,d, the behavior of Γ_2(A_) turns out to be deeply connected to its Gaussian analogue Γ_2() where  is a GOE matrix. The quantity Γ_2() has been studied in statistical physics, being the ground state energy of the Sherrington-Kirkpatrick model of spin glasses <cit.>.
  The deep but non-rigorous analysis of Parisi <cit.> proposed an asymptotic value 1/n Γ_2() → 2P_*≈ 1.526, which was later proven rigorously in a sequence of mathematical works <cit.>. By relating the graph model to the Gaussian model, <cit.> gave an asymptotic formula for the size of the largest cut in a random regular graph with large degree:
  
      lim_n →∞_∼_n, d_2() = 1/2(1 + 2P_*/√(d) + o_d(1/√(d))).
  
  For the Gaussian setting, it was shown in <cit.> using a quiet planting approach that (conditional on a certain complexity assumption based on the low-degree likelihood ratio) the best possible upper bound on 1/nΓ_2() that can be certified in polynomial time is 2, in contrast with the true value 2P_*; the optimal bound is given by a simple spectral certificate involving the maximum eigenvalue of . Given this, we might expect that the best efficiently-certifiable bound on _2() for ∼_n, d is given by replacing 2P_* in (<ref>) with 2.
  Indeed, <cit.> and <cit.> showed respectively that the degree-2 and degree-4 sum-of-squares relaxations can certify a bound no better than
  
      _2() ≤1/2(1 + 2/√(d) + o_d(1/√(d))).
  
  
  Our results extend the picture emerging from this literature in two important ways.
  We show (see Theorem <ref> and discussion in Section <ref>) that conditional on the eSBM conjecture, (<ref>) is in fact the optimal bound on _2() certifiable in polynomial time.
  Thus, if the eSBM conjecture holds then no constant-degree sum-of-squares relaxation can improve upon on the known results for degree-2 and degree-4. Furthermore, we justify this bound with an explicit quiet planting of a large cut in a random regular graph.
  
  
  
    
  The Gaussian k-cut model.
  
  Above, we have seen an intimate connection between Γ_2(A_) where A_ is the adjacency matrix of ∼_n, d, and its Gaussian counterpart Γ_2() where ∼GOE(n). More generally, _k() can be written in terms of a certain quantity Γ_k(A_) defined in Section <ref>, which has a natural Gaussian counterpart Γ_k().
  
  In fact, explicit formulas similar to (<ref>) are also known that relate the asymptotic values (in the double limit n →∞ followed by d →∞) of Γ_k(A_) and Γ_k() even for k > 2 <cit.>.
  The broadly applicable techniques used in these results—the Lindeberg exchange method and related probabilistic interpolation arguments—suggest that there is a general and fundamental relationship between the graph model in the large-degree limit and the Gaussian model. Yet, it is not clear whether this implies any relation between the respective thresholds for efficient certification.
  
  To clarify this matter, we also give results showing that the problem of certifying upper bounds on Γ_k() under the Gaussian model exhibits similar behavior to the graph model: no polynomial-time certifier can improve over the basic spectral bound. The proof is again based on quiet planting, and can be seen as an extension of the results of <cit.> which handled the k=2 case. Our results rely on a complexity assumption concerning the low-degree likelihood ratio, which we discuss further in Section <ref>. As a by-product, we develop a general framework for bounding the low-degree likelihood ratio of certain Gaussian models, which may be of independent interest. Specifically, we conduct the low-degree analysis of a broad class of multi-spiked matrix models (both Wigner and Wishart), and give an improved low-degree analysis of the stochastic block model which suggests that fully-exponential time is needed below the Kesten–Stigum threshold.
  
  
  
   §.§ Heuristics for Average-Case Computational Hardness
  
  
  
  Our results on hardness of certification rely on unproven conjectures about average-case hardness, such as the eSBM conjecture. Proving these types of conjectures seems to be beyond the reach of current techniques (even when assuming standard complexity conjectures such as ), as illustrated by the fact that no such proof is known for the famous planted clique problem. However, a myriad of heuristic techniques have emerged for predicting hardness of average-case problems by proving lower bounds against certain classes of algorithms. Taken together, these methods create a fairly coherent theory of computational complexity for a large class of high-dimensional Bayesian inference problems. In this section we describe the three methods that will be used in this work: belief propagation, the local statistics hierarchy, and the low-degree likelihood ratio. We remark that these are not the only such methods, some others being average-case reductions <cit.>, sum-of-squares lower bounds <cit.>, statistical query lower bounds <cit.>, the overlap gap property <cit.>, and analysis of non-convex loss landscapes <cit.>. Finally, in Section <ref> we discuss the XOR-SAT problem—an important counterexample for many of the above heuristics—and the related issues of “robustness” that arise in our eSBM conjecture.
  
  
  
  
    §.§.§ Belief Propagation and the Kesten–Stigum Threshold
  
  
  
  The sharp computational phase transition known as the Kesten–Stigum (KS) threshold in the stochastic block model, was first predicted by <cit.> using non-rigorous ideas inspired by statistical physics. The idea is to consider the belief propagation (BP) algorithm, an iterative method that attempts to recover the planted community structure by keeping track of “beliefs” about each node's community label and updating these in a locally-Bayesian-optimal way. BP has an “uninformative” fixed point, which is a natural starting point for the algorithm where the beliefs reflect no knowledge of the communities. It was shown in <cit.> that if the signal-to-noise ratio (SNR) lies above the KS threshold then the uninformative fixed point is unstable, suggesting that BP should leave it and find a community assignment that correlates with the truth; and if the SNR lies below the KS threshold then the uninformative fixed point is stable, meaning that BP will remain there and fail to find a nontrivial solution. It was later proven that indeed it is possible to nontrivially recover the communities in polynomial time when above the KS threshold <cit.>, whereas no such algorithm is known below the KS threshold. More generally, similar computational thresholds have been predicted in various models (e.g., <cit.>) by examining the stability of BP or its simplified variant, approximate message passing (AMP) <cit.>. For many high-dimensional inference problems, it is known that BP and AMP achieve optimal information-theoretic performance (e.g. <cit.>); and when they don't, it is often conjectured that they achieve the best possible performance among efficient algorithms. Thus, stability of BP provides concrete evidence for computational hardness.
  
  
  
  
  
    §.§.§ The Local Statistics Hierarchy
  
  
  Introduced by one of the authors, Mohanty, and Raghavendra in <cit.> and building off of the work of Hopkins and Steurer <cit.>, the Local Statistics hierarchy is a family of increasingly powerful semidefinite programming algorithms for solving Bayesian hypothesis testing problems. By analogy with the Sum-of-Squares algorithm, we take this hierarchy as a proxy for hardness: the higher we need to go to perform the hypothesis test, the harder it is.
  
  Consider a generic inference scheme where we are to distinguish between a null model  which outputs unstructured data ∈^m, and a planted model  generating structured data ∈^m according to some random and hidden signal ∈^n. Letting x = (x_1,...,x_n) be a set of variables, we may regard the conditional expectation _∼ [p() | ] as a random linear functional from [x] ↦ that is positive in a certain sense: _∼ [p()^2 | ] ≥ 0 for every polynomial p. 
  
  The Local Statistics hierarchy is parameterized by two integers (D_x,D_G). Given as input some G_0 ∈^m, it attempts to find a linear functional that approximates this conditional expectation [p(x) | G] in the planted model. In particular, borrowing terminology from Sum-of-Squares programming, we search for a “pseudoexpectation” functional  that assigns a real number to every polynomial of degree at most D_x in [x], with the constraints that (i) p(x)^2 ≥ 0, and (ii) p(x) ≈_(,) ∼ p() for every polynomial p(x) ∈[x] whose coefficients are of degree at most D_G in the input G_0. It is well-known that this may be written as a SDP on matrices of size O(n^D_x) with O(m^D_G) affine constraints.
  
  In many cases, this paper included, this problem is soluble with high probability when the input G_0 is sampled from the planted model . For instance, the evaluation map p(x) ↦ p() is a feasible solution provided that the  is sufficiently concentrated and these polynomials do not fluctuate too much about their expectations. On the other hand, by taking D_x and D_G sufficiently large it becomes infeasible when the input is drawn from a different distribution. The D_x and D_G necessary measure the hardness of the hypothesis testing problem.
  
  
  
    §.§.§ The Low-Degree Likelihood Ratio
  
  
  
  As was first discovered in a series of works in the sum-of-squares literature <cit.>, analyzing the low-degree likelihood ratio gives predictions of computational hardness that match widely-believed conjectures for many hypothesis testing problems (as corroborated by the various other heuristics mentioned above). 
  In essence, this method takes low-degree polynomials as a proxy for all polynomial-time algorithms, and analyzes whether any low-degree polynomial can distinguish two distributions  and  (with the same interpretations as above) as n →∞.
  
  The key to making this analysis tractable is to choose the correct soft notion of “successfully distinguishing.”
  This is done by considering the maximization
  
      [                             maximize                 _∼ p()/(_∼p()^2)^1/2;                            such that p ≠ 0  is a polynomial of degree≤ D. ]
  
  In words, we seek to maximize p() under  in expectation, while keeping its typical magnitude under  modest.
  
  We note that, if we did not restrict p to be a low-degree polynomial, then the optimal p would equal the classical likelihood ratio, L d/d.
  In absence of computational constraints, thresholding L gives an optimal test between  and  in the sense of minimizing error probabilities, as shown in the classical Neyman-Pearson lemma <cit.>.
  Moreover, the value of the above problem would be the norm L of L in L^2().
  If that norm is bounded as n →∞, then  and  cannot be distinguished w.h.p. by any test, by an application of Le Cam's second moment method for contiguity (see <cit.> for further exposition). 
  
  With the further constraint to low-degree polynomials, the result is similar: the optimal p is the aforementioned low-degree likelihood ratio, the orthogonal projection of L to the subspace of degree-D polynomials in L^2(), which we denote L^≤ D.
  The value of the problem is its norm, L^≤ D.
  We again consider whether, as n →∞, for D = D(n) slowly growing with n, this norm diverges or remains bounded.
  If it diverges, we expect that low-degree polynomials can distinguish  from  w.h.p. (at an intuitive level, the algorithm we have in mind is thresholding L^≤ D); if it remains bounded, we conclude that low-degree polynomials cannot distinguish  from  w.h.p. in this particular sense, and therefore expect that no polynomial-time algorithm can do so either.
  
  The precise scaling of D(n) relates to the efficiency of algorithms that the heuristic pertains to—higher degree polynomials describe more time-consuming computations.
  However, while constant-degree polynomials may be evaluated in polynomial time, some other polynomial-time computations require slightly higher degree polynomials to express.
  A crucial example is approximating the spectral norm of a matrix with dimensions polynomial in n, which requires a polynomial of degree Θ(log n) to approximate accurately.
  Taking this into account, a low-degree lower bound with D(n) ≫log n is taken as evidence that no polynomial-time test exists.
  Similarly, we view a low-degree lower bound with D(n) ≫ n^δ for some δ∈ (0, 1) as suggesting a lower bound against tests with runtime O(exp(n^δ)).
  See <cit.> for further discussion.
  
  
  
    §.§.§ A Caveat: XOR-SAT
  
  
  
  In the planted 3-XOR-SAT problem, we are given m clauses of the form x_i x_j x_k = b for some choice of i,j,k ∈ [n] and b ∈{± 1}. The goal is to distinguish the case where the clauses are completely random from the case where there is a planted assignment of {± 1} values to the variables x_1,…,x_n such that all clauses are satisfied. This is a notable counterexample for many heuristics for average-case hardness, including sum-of-squares and all three methods mentioned above (see e.g., Lecture 3.2 of <cit.> or Chapter 18 of <cit.>). These heuristics predict that the distinguishing task is possible in polynomial time only when m ≳ n^3/2, whereas in reality the problem is much easier: Gaussian elimination can be used to decide with certainty whether or not there is a satisfying assignment. However, if we change the planted distribution so that only a 1-ε fraction of the clauses are satisfied, Gaussian elimination breaks down and the best known algorithms indeed require m ≳ n^3/2. In this sense, the above heuristics seem to predict the threshold for “robust” algorithms. We expect that a similar phenomenon is at play in the eSBM model: while there exist algorithms to solve the problem by exploiting brittle algebraic structure in the eigenvectors (see Remark <ref>), we conjecture (Conjecture <ref>) that the threshold predicted by the heuristics is the correct computational threshold for a noisy version of the problem.
  
  
  
  
  
  
  
   §.§ Notation
  
  
  We use standard asymptotic notation such as o(·) and O(·); unless stated otherwise, this always pertains to the limit n →∞ with other parameters (such as d, k, η) held fixed. We use e.g., o_d(·) or O_d(·) when considering the double limit n →∞ followed by d →∞; for example, f(n,d) = o_d(g(n,d)) means that for any > 0 there exists d_0 > 0 such that for all d ≥ d_0 there exists n_0 > 0 such that for all n ≥ n_0 we have |f(n,d)/g(n,d)| ≤. An event occurs with high probability (w.h.p.) if it has probability 1-o(1). We write f ∼ g to mean f/g → 1.
  
  Throughout, all graphs are assumed to be simple—i.e., without self-loops and multiple edges—unless stated otherwise. A d-regular graph has degree d at every vertex. _n, d denotes the uniform distribution over d-regular n-vertex graphs.
  
  We will use 𝕀_k denote the k × k identity matrix and _k for the k × k all-ones matrix; e_1,e_2,... are the standard unit basis vectors, and  will denote the all-ones vector. For matrices, · denotes the operator (spectral) norm and ·_ denotes the Frobenius norm. We use A for the ({0,1}-valued) indicator of an event A. We write [k] = {1,2,…,k} and = {0,1,2,…}.
  
  
  
  
  
  
  § MAIN RESULTS
  
  
  
  
   §.§ Setup and Definitions
  
  
  
  We consider a general framework that captures the problem of certifying bounds on max-k-cut in a random graph, as well as a Gaussian variant of this problem.
  
  
  For a labeling σ: [n] → [k], the associated partition matrix P = P^(σ)∈^n × n is given by
  
      P_i,j =  1    σ(i) = σ(j), 
       -1/(k-1)    σ(i) ≠σ(j).
  
  
  
  A basic fact is that P ≽ 0 and (P) = k-1. This can be seen by realizing P as the Gram matrix of a certain collection of vectors: assign each u ∈ [n] one of the k unit vectors in ^k-1 pointing to the corners of a simplex, according to its label σ(u) ∈ [k].
  
  Let Π be the set of all partition matrices. For a given matrix A ∈^n × n and a given k, we will be interested the problem of algorithmically certifying an upper bound on the value
  
      Γ_k(A) max_P ∈Π⟨ P,-A ⟩.
  
  If A_G ∈{0,1}^n × n is the adjacency matrix of a graph G = (V,E) (defined with (A_G)_i,i = 0), then ⟨ P^(σ), -A_G ⟩ = 2(k · m_σ(G) - |E|)/(k-1), where m_σ(G) is the number of monochromatic edges of G under the labeling σ. As a result,
  
      _k(G) = k-1/k(1 +  Γ_k(A_G)/2|E|).
  
  
  Thus, an upper bound on Γ_k(A_G) translates to an upper bound on _k(G), which in turn can be used to refute k-colorability. We now formally define the certification task.
  
  
      
      Let = _n be a sequence of distributions ^n × n and let 𝒜 = 𝒜_n : ^n× n→ be a sequence of algorithms. We say that 𝒜 certifies the upper bound B on Γ_k over ∼ if both of the following hold:
      
          
    (i) for every A ∈^n × n, 𝒜(A) ≥Γ_k(A), and
          
    (ii) if ∼_n then 𝒜_n() ≤ B with probability 1-o(1).
      
  
  
  Crucially, 𝒜(A) must always be a valid upper bound, even if A is atypical under . In exponential time it is possible to compute Γ_k(A) exactly and thus achieve perfect certification; we are interested instead in polynomial-time certification procedures.
  
  There is a simple spectral approach <cit.> to certifying bounds on Γ_k(A). Let λ_min = λ_min(A) denote the minimum eigenvalue of A. For any P ∈Π we have P ≽ 0 and A - λ_min I ≽ 0, so
  
      0 ≤⟨ P, A - λ_min I ⟩ = ⟨ P,A ⟩ - λ_min n
  
  and -λ_min n is an efficiently-computable upper bound on Γ_k(A). Our main results give evidence that it is computationally hard to improve upon this spectral bound when  is drawn from certain distributions : (i) random d-regular graphs, and (ii) Gaussian matrices.
  
  
  
   §.§ Random Regular Graphs
  
  
  We will be concerned with the following task of distinguishing two distributions, also called hypothesis testing or detection.
  
  
      Let _n and _n be probability measures on the same space Ω_n. We say that an algorithm t_n: Ω_n →{p,q} distinguishes _n and _n with high probability, or (equivalently) achieves strong detection (between _n and _n) if
      
      _n[t_n() = q] + _n[t_n() = p] = o(1)
  
      as n →∞.
  
  
  Our results for random regular graphs are conditional on a conjecture regarding computational hardness of detection in a noisy variant of the equitable stochastic block model (eSBM). The extra noise is crucial, as discussed in Remark <ref> and Section <ref>. Specifically, the noise takes the form of “rewiring” a small constant fraction of the edges as follows.
  
  
      If G = (V,E) is a d-regular n-vertex graph and δ > 0, let _δ(G) denote the random d-regular graph obtained from G by making ⌊δ n ⌋ `swaps.' That is, repeatedly choose a pair of distinct edges (i,j), (k,ℓ) uniformly at random[Here, the ordering of the tuples matters, so e.g., (i,j) and (j,i) should be chosen with equal probability.] conditioned on the following events: i  k, j ℓ, (i,k) ∉ E, and (j,ℓ) ∉ E. Remove edges (i,j) and (k,ℓ), and add edges (i,k) and (j,ℓ).
  
  
  Recall the definition of the eSBM (Definition <ref>) and the associated threshold d_KS^ eq(η) defined in (<ref>).
  
  
      
      Let ^ eq_n,d,k,η, δ denote the distribution over d-regular n-vertex graphs given by _δ() where ∼_n, d, k, η^ eq. Suppose δ > 0, η∈ [-1/k-1,1], k ≥ 2, and d < d_KS^ eq(η) are all fixed.
      Also suppose k | (1-η)d so that the equitable model is defined for an infinite sequence of values of n.
      Then, there exists no polynomial-time algorithm that with high probability distinguishes ^ eq_n,d,k,η,δ from _n, d as n →∞ (in the sense of Definition <ref>).
  
  
  The above conjecture implies the following result on hardness of certifying bounds on max-k-cut.
  
  
      
      Assume the eSBM conjecture (Conjecture <ref>) holds. Fix d > 0 and k ≥ 2 and let η∈ [-1/k-1,0] be such that |η| < 2√(d-1)/d and k  |  (1-η)d. Then for any ϵ > 0, no polynomial-time algorithm can certify, in the sense of Definition <ref>, the upper bound nd(|η|-ϵ)
      on Γ_k over _n, d. Equivalently, no polynomial-time algorithm can certify for ∼_n, d the bound
      
      _k() ≤k - 1/k(1 + |η| - ϵ).
  
  
  
  The proof idea is described in the Introduction; the full details are given in Section <ref>. The effects of the integrality condition k  |  (1-η)d are discussed in Section <ref> below; this condition can be ignored when d ≫ k^2.
  
  
  
  An important special case where Theorem <ref> is tight is η = -1/k-1, corresponding to refutation of near colorability. Here the integrality condition k  |  (1-η)d reduces to (k-1)  |  d. Thus for any d,k satisfying (k-1)  |  d and k > 1+d/2√(d-1) we have that for any ϵ > 0, no polynomial-time algorithm can certify _k() ≤ 1 - ϵ. There is an infinite sequence of (d,k) values with k ∼1/2√(d) for which the conditions on d,k are satisfied, namely d = 4(k-1)(k-2) for all k > 2. Thus, our result is asymptotically tight, matching the spectral algorithm in the double limit n →∞ followed by d →∞.
  
  
  
  
  As stated, Theorem <ref> only shows hardness of refuting a near-coloring, as opposed to an exact coloring. While we expect a similar hardness result to hold for exact coloring, this does not follow from the eSBM conjecture because the noise operator _δ prevents us from planting an exact coloring. Hardness of refuting exact coloring would follow from a variant of the eSBM conjecture where the noise operator only makes swaps that do not affect the value of the planted cut.
  
  
  Our next two results give concrete evidence for the eSBM conjecture using two different heuristics (discussed in Section <ref>): stability of belief propagation, and the local statistics hierarchy. Both of these methods predict d_KS^ eq(η) as the computational threshold for the eSBM.
  
  
  
      For k ≥ 4, the Kesten–Stigum threshold of the eSBM with parameters (n, d, k, η), defined as the smallest number d_KS^ eq so that, for all d > d_KS^ eq, the “uninformative” fixed point of the belief propagation iteration is unstable, is given by
      
      d_KS^ eq = d_KS^ eq(η) 2/η^2(1 + √(1 - η^2)).
  
  
  
  Further details, as well as the full analysis leading to the above result, can be found in Section <ref>.
  
  
      
      If d > d^ eq_KS(η), then there exist D sufficiently large and δ > 0 so that the degree-(2,D) Local Statistics algorithm with error tolerance δ can distinguish _n, d and ^ eq_n,d,k,η with high probability. If d ≤ d^ eq_KS(η), no such D and δ exist.
  
  
  Further details on the Local Statistics hierarchy, and the proof of Theorem <ref>, can be found in Section <ref>.
  
  
  
    §.§.§ Discussion of Integrality Condition
  
  
  
  The integrality constraints in the eSBM (Definition <ref>) and in the above results may seem somewhat mystifying. In this section we will try to shed some light on the limits of our method for quiet planting, and how they compare to the power of spectral refutation. The integrality condition k | (1-η)d from Theorem <ref> is required so that the equitable block model exists for an infinite sequence of values of n. This condition can be written as η d ≡ d k, which means η is constrained to lie in a certain grid of spacing k/d within the interval [-1/k-1,0]. In order to extract the strongest possible hardness result from Theorem <ref>, the goal is to pick η as to maximize |η| subject to the integrality condition and |η| < 2√(d-1)/d. If d ≫ k^2 then we have k/d≪2√(d-1)/d and so the grid allows η to be chosen extremely close to 2√(d-1)/d; this means the effects of the integrality condition are negligible and we essentially obtain the ideal hardness result (<ref>) which matches the spectral algorithm. In particular, our results are tight in the regime d →∞ with k fixed.
  
  As discussed in Remark <ref>, we also get tight results in the particular case η =  -1/k-1 corresponding to near-coloring, because the integrality condition simplifies in a helpful way.
  
  On the other hand, for small degree the integrality conditions can impose significant limitations. A particularly severe example is that of k=2 and d=3, which corresponds to Max-Cut in a random 3-regular graph. The spectral bound corresponds to
  
      MC_2() ≤1/2(1 + 2√(3-1)/3) ≈ 0.97.
  
  On the other hand, the integrality condition from Theorem <ref> requires that 2|3(1-η), in addition to the condition |η| <  2√(3-1)/3. Since 3(1+2√(3-1)/3) ≈ 5.83 the largest |η| admissible is such that that 3(1-η) = 4, corresponding to η = 1/3. This means that Theorem <ref> only addresses certification below
  
      MC_2() ≤1/2(1 + 1/3) = 2/3≈ 0.67.
  
  This is unfortunate since random 3-regular graphs have MC_2() > 0.88 with high probability <cit.>, and calculations from statistical physics <cit.> suggest the even larger value MC_2() ≈ 0.92. That is, using the equitable block model to plant a 2-cut in a 3-regular graph, by giving each vertex one neighbor in its own group and two neighbors in the other group, plants a cut that is smaller than naturally arising cuts in random 3-regular graphs. 
  
  In general, aside from the special case of near-coloring (Remark <ref>), our results are most compelling when k is small and d is large, so that the integrality condition in Theorem <ref> does not create a significant gap from the limiting threshold |η| = 2√(d-1)/d. We believe the investigation of quiet plantings in small-degree graphs to be an interesting direction of future research.
  
  
  
  
   §.§ The Gaussian k-Cut Model
  
  
  
  
    §.§.§ Hardness of Certification
  
  
  In this section we discuss a Gaussian analogue of the coloring problem, namely the problem of certifying upper bounds on Γ_k() where  is a GOE matrix defined as follows.
  
  
      
      The Gaussian orthogonal ensemble is the following distribution (n) over random matrices: ∼(n) is symmetric (_u,v = _v,u) with diagonal entries _u,u∼𝒩(0,2/n) and off-diagonal entries _u,v∼𝒩(0,1/n), where the values {_u,v :  u ≤ v} are independent.
  
  
  It is well known that (as n →∞) the eigenvalues of ∼(n) follow the Wigner semicircle law supported on [-2,2], and in particular, λ_min() → -2 almost surely. Thus, the spectral approach (see Section <ref>) certifies the upper bound Γ_k() ≤ (2 + o(1)) n. Our main results give rigorous evidence in support of the following conjecture, which states that improving upon this spectral bound requires fully exponential time.
  
  
      
      For any constants k ≥ 2, ϵ > 0 and δ > 0, there is no algorithm of runtime exp(O(n^1-δ)) that certifies the upper bound (2-ϵ)n on Γ_k() over ∼(n).
  
  
  Our evidence for this conjecture can be seen as a generalization of <cit.>, which handles the k=2 case. In Section <ref> we give a reduction from a certain hypothesis testing problem to the certification problem in question. In analogy to our results on coloring, this reduction can be seen as constructing a planted distribution that directly plants an eigenspace with no pushout effect; this planting is computationally quiet, conditional on hardness of the testing problem. The testing problem is a particular instance of the spiked Wishart model with a rank-(k-1) negative spike. In Section <ref> below, we state results analyzing the low-degree likelihood ratio (see Section <ref>) for this model; these results suggest that fully exponential time is required (in the appropriate parameter regime).
  
  As a by-product of our analysis, we give new bounds on the low-degree likelihood ratio for a wide class of multi-spiked matrix models (both Wigner and Wishart), which may be of independent interest. These results also extend to certain binary-values analogues of these problems, including (a variant of) the stochastic block model. These results are also discussed in Section <ref> below.
  
  
  
    §.§.§ Low-Degree Hardness for General Spiked Models
  
  
  
  We consider general variants of the spiked Wigner and Wishart models, defined as follows.
  
  
      Let = (_n) be a probability measure over ^n × n_, the symmetric n × n matrices. The general spiked Wigner model with spike prior  and signal-to-noise ratio λ∈ is specified by the following null and planted distributions over ^n × n_.
      
          
    * Under , draw ∼(n).
          
    * Under , let = λ + where ∼ and ∼(n), independently.
      
  
  
  
      
      Let = (_n) be a probability measure over ^n × n_. The general spiked Wishart model with spike prior , signal-to-noise ratio β > -1, and number of samples N ∈, is specified by the following null and planted distributions over (_1, …, _N) ∈ (^n)^N.
      
          
    * Under , draw _u ∼(0, 𝕀_n) independently for u ∈ [N].
          
    * Under , first draw ∼ and define
          
      =    if β≻ -𝕀_n, 
      
                      0    else.
  
          Then draw _u ∼( 0, 𝕀_n + β) independently for u ∈ [N].
      
  
  
  The purpose of (<ref>) is to ensure that 𝕀_n + β X is a valid covariance matrix. We will consider priors for which the first case of (<ref>) occurs with high probability. Specifically, we focus on the following class of priors that are PSD with constant rank.
  
  
      
      Fix an integer k ≥ 1. Let π be a probability measure supported on a bounded subset of ^k, satisfying [π] = 0 and (π) = 1. Let (π) denote the spike prior which outputs = 1/n^⊤, where  is n × k with each row distributed according to π. (We do not allow π to depend on n.)
  
  
  It is well known in random matrix theory that polynomial-time detection in the Wigner model is possible when |λ| > 1, by thresholding the maximum (or minimum if λ < 0) eigenvalue of  <cit.>. Similarly, poly-time detection in the Wishart model is possible when β^2 > n/N, by thresholding the maximum or minimum eigenvalue of the sample covariance matrix = 1/N∑_i _i _i^⊤ <cit.>. In the general setting above, we have the following bounds on the norm of the low-degree likelihood ratio L^≤ D (see Section <ref>), which suggest that fully exponential time is required to solve the detection problem below this spectral threshold. Our results are consistent with the computational thresholds predicted by <cit.>, where it was shown that the approximate message passing algorithm fails below the spectral threshold. The proofs are deferred to Section <ref>.
  
  
  
      
      Fix constants k ≥ 1 and λ∈. Fix π satisfying the requirements in Definition <ref>. Consider the general spiked Wigner model with spike prior (π). If |λ| < 1 then L^≤ D = O(1) for any D = o(n/log n).
  
  
  
      
      Fix constants k ≥ 1, β > -1, and γ > 0. Fix π satisfying the requirements in Definition <ref>. Consider the general spiked Wishart model with any N = N_n satisfying n/N →γ as n →∞, and with spike prior (π). If β^2 < γ then L^≤ D = O(1) for any D = o(n/log n).
  
  
  
      In the setting of Theorem <ref>, the first case of (<ref>) holds with high probability because β > -1 and →(π) = 1 (in probability). To see this, write = 1/n^⊤ = 1/n^⊤; being an average of n i.i.d. k × k matrices, 1/n^⊤ converges in probability to its expectation, which is (π).
  
  
  We also extend our framework to binary-valued problems. In Proposition <ref> we give a general result analyzing the low degree likelihood ratio in binary-valued problems via a comparison to the analogous Gaussian-valued problem. As an application, we study the following variant of the stochastic block model (SBM).
  
  
      
      The stochastic block model with parameters k ≥ 2, d > 0, η∈ [-1/(k-1),1] (constants not depending on n) is specified by the following null and planted distributions over n-vertex graphs.
      
          
    * Under , for every u<v the edge (u,v) occurs independently with probability d/n.
          
    * Under , each vertex is independently assigned a community label drawn uniformly from [k]. Conditioned on these labels, edges occur independently. If u,v belong to the same community then edge (u,v) occurs with probability (1+(k-1)η)d/n; otherwise (u,v) occurs with probability (1-η)d/n.
      
  
  
  Here k is the number of communities, d is the average degree, and η is a signal-to-noise ratio: the planted k-cut cuts a fraction k-1/k(1-η) of the edges on average. Known polynomial-time algorithms only succeed at distinguishing  from  above the so-called Kesten–Stigum (KS) threshold, i.e., when d η^2 > 1 <cit.>. We prove the following in Appendix <ref>.
  
  
      
      Consider the stochastic block model as in Definition <ref> with parameters k, d, η fixed. If dη^2 < 1 then L^≤ D = O(1) for any D = o(n/log n).
  
  
  Prior work <cit.> has already given a low-degree analysis of this variant of the SBM, showing that the problem is low-degree-hard below the KS bound. Our result offers two advantages: (i) the proof is streamlined, following easily from our general-purpose machinery, without the need for direct combinatorial calculations, and (ii) we bound L^≤ D for D all the way up to o(n/log n) instead of only n^0.01. As discussed in Section <ref>, item (ii) constitutes evidence that distinguishing  from  in the SBM requires fully exponential time exp(n^1-o(1)) below the KS bound.
  
  
  
  
  § REDUCTION FROM DETECTION TO CERTIFICATION
  
  
  In this section we give formal proofs, for both the graph and Gaussian models, that hardness of a particular detection problem implies hardness of certification.
  
  
  
   §.§ The Graph Model
  
  
  
  We now give the proof of Theorem <ref>, which shows that hardness of detection in the noisy eSBM model implies hardness of certifying bounds on max-k-cut.
  
  
  Assume for the sake of contradiction that some algorithm 𝒜 certifies the upper bound _k() ≤k-1/k(1+|η|-) when ∼_n,d. We will use this to distinguish between ^ eq_n,d,k,η,δ and _n, d for δ = d  (k-1)/5k; this contradicts Conjecture <ref> because the assumption |η| < 2√(d-1)/d implies d < d_KS^ eq(η). Our detection algorithm takes as input a graph G and outputs q (“null”) if 𝒜(G) ≤k-1/k(1+|η|-) and p (“planted”) otherwise. If ∼_n,d then 𝒜() ≤k-1/k(1+|η|-) with high probability by assumption, and so the distinguisher outputs q. Now consider the case ∼^ eq_n,d,k,η,δ. A graph drawn from _n, d, k, η^ eq has a planted k-cut of fractional size k-1/k(1+|η|), and the noise operator _δ can remove at most 2δ n edges from this cut. Thus,
  
      𝒜() ≥_k() ≥k-1/k(1+η) - 2δ n/|E|
  
  where
  
      2δ n/|E| = 4δ/d = 4/d·d(k-1)/5k < ·k-1/k.
  
  This implies 𝒜() > k-1/k(1+|η|-) and so the distinguisher outputs p.
  
  
  
  
  
   §.§ The Gaussian Model
  
  
  
  
      
      Let π_k be the distribution over ^k given by √(k) e_ - /√(k) where ∼ [k] uniformly at random. Let _k = (π_k) be the associated spike prior, as defined in Definition <ref>.
  
  
  Here, e_1,e_2,... denote the standard unit basis vectors and  denotes the all-ones vector.
  
  
      
      Suppose there exist constants k ≥ 2 and ϵ > 0 such that there is a time-t(n) algorithm to certify the upper bound (2-ϵ)n on Γ_k() over ∼(n). Then for some constants β∈ (-1,0) and γ > 1, there is a time-(t(n)+poly(n)) algorithm achieving strong detection in the general spiked Wishart model with spike prior _k.
  
  
  Note that the above parameters satisfy β^2 < γ, which is in the “hard” regime of the Wishart model. Thus, Theorem <ref> together with the low-degree-hardness of the Wishart model in that regime (Theorem <ref>) constitute rigorous evidence for Conjecture <ref>.
  
  
      Let 𝒜 be the purported certification algorithm. We will use this to solve detection in the Wishart model, given Wishart samples _1,…,_N. Sample ∼(n) and let _1 ≤⋯≤_n denote its (random) eigenvalues. Sample a uniformly random orthonormal basis _n-N+1,…,_n for span{_1,…,_N} and a uniformly random orthonormal basis _1,…,_n-N for the orthogonal complement ^⊥. Let = ∑_i=1^n _i _i _i^⊤. Our Wishart detection algorithm is as follows: if 𝒜() ≤ (2-ϵ)n then output q; otherwise, output p.
      
      We now prove that this achieves strong detection. If the Wishart samples were drawn from  then  is a uniformly random N-dimensional subspace and so ∼(n). This means 𝒜() ≤ (2-ϵ)n with high probability by assumption, and so our algorithm correctly outputs q. It remains to show that if the Wishart samples were drawn from , then Γ_k() > (2-ϵ)n with high probability, and so the algorithm is forced to output p.
      
      Suppose the Wishart samples were drawn from  with planted matrix . With high probability we are in the first case of (<ref>), i.e., = 1/n^⊤ where each row of  is drawn independently from π_k. Note that 1/k-1^⊤ is a partition matrix, and so
      
      Γ_k() ≥ -1/k-1⟨^⊤, ⟩.
  
      We can bound
      
      ⟨^⊤, ⟩   = ⟨^⊤, ∑_i=1^n _i _i^⊤⟩
         ≤⟨^⊤, _n-N∑_i=1^n-N_i _i^⊤ + _n ∑_i=n-N+1^n_i _i^⊤⟩
         = ⟨^⊤, _n-N(𝕀_n - ∑_i=n-N+1^n_i _i^⊤) + _n ∑_i=n-N+1^n_i _i^⊤⟩
         = ⟨^⊤, _n-N𝕀_n + (_n - _n-N) ∑_i=n-N+1^n_i _i^⊤⟩
  
      where we have used the fact that ∑_i=1^n _i _i^⊤ = 𝕀_n since {_i}_i ∈ [n] is an orthonormal basis. We will bound the pieces of this expression separately.
      
      First we bound ⟨^⊤,𝕀_n ⟩. The nonzero eigenvalues of ^⊤ are the same as the nonzero eigenvalues of ^⊤. Since ^⊤ is the sum of n i.i.d. k × k matrices, 1/n^⊤ converges in probability to its expectation, which is (π) = 𝕀_k - _k/k where _k is the k × k all-ones matrix. This means ⟨^⊤, 𝕀_n ⟩ = (^⊤) = n (1/n^⊤) = (1+o(1))n(k-1) with high probability.
      
      Next we bound ⟨^⊤,∑_i=n-N+1^n _i _i^⊤⟩. Recall that {_i}_i=n-N+1^n is an orthonormal basis for span{_1,…,_N}, and so ∑_i=n-N+1^n _i _i^⊤≼1/ where = 1/N∑_i=1^N _i _i^⊤ and  is the smallest nonzero eigenvalue of . Since  is a spiked covariance matrix, Theorem 1.2 of <cit.> gives → (√(γ)-1)^2 > 0 in probability. Therefore,
      
      ⟨^⊤,∑_i=n-N+1^n _i _i^⊤⟩≤⟨^⊤,1/⟩ = 1/ N∑_i=1^N ^⊤_i^2.
  
      For fixed U (and therefore fixed X), note that U^⊤_i follows a multivariate Gaussian distribution with mean zero and covariance
      
      [U^⊤_i _i^⊤ U] = U^⊤[_i _i^⊤] U = U^⊤ (I + β X) U = U^⊤ U + β/n U^⊤ UU^⊤ U.
  
      Recalling that 1/n^⊤→𝕀_k - _k/k, we have 1/n (^⊤ + β/n^⊤^⊤) → (1+β)(𝕀_k - _k/k) in probability. Thus,
      1/nN∑_i=1^N ^⊤_i^2 converges in probability to (1+β)(𝕀_k-_k/k) = (1+β)(k-1), and we can conclude that
      
      ⟨^⊤,∑_i=n-N+1^n _i _i^⊤⟩≤ (1+o(1))n/(1+β)(k-1) = (1+o(1))n(√(γ)-1)^2(1+β)(k-1)
  
      with high probability.
      
      The eigenvalues of  converge to the Wigner semicircle law on [-2,2], and so we have _n - _n-N≤ 4+o(1) with high probability. Also, by taking γ > 1 close enough to 1, we can ensure λ_n-N≤ -2 + ϵ/2 with high probability.
      
      Putting it all together, we now have
      
      Γ_k()    ≥ -1/k-1⟨^⊤, ⟩
         ≥ -1/k-1⟨^⊤, λ_n-N𝕀_n + (_n - _n-N) ∑_i=n-N+1^n_i _i^⊤⟩
         ≥ -1/k-1[(-2+ϵ/2)(1+o(1))n(k-1) +  (4+o(1))n(√(γ)-1)^-2(1+β)(k-1)] 
         > (2-ϵ)n
  
      for sufficiently large n, provided we choose β > -1 sufficiently close to -1. This completes the proof.
  
  
  
  
  § BELIEF PROPAGATION AND THE KESTEN–STIGUM TRANSITION
  
  
  
  In this section, we carry out a stability analysis of belief propagation (as discussed in Section <ref>) and derive the result presented in Theorem <ref>. The analysis resembles that of the original work <cit.> that predicted the Kesten–Stigum threshold in the ordinary stochastic block model, but the equitability constraints create additional technical complexity in our setting. We start with the special case of the equitable coloring model in Section <ref>, and generalize to the equitable block model in Section <ref>. Throughout this section, it turns out to be convenient to parametrize the equitable model in a different way (defined below) than used in the Introduction.
  
  
  
   §.§ The Equitable Coloring Model
  
  
  
  The equitable coloring model is obtained by setting η = 1k-1 in Definition <ref>; for brevity let's define
  
      c 1 + η/k,
  
  so that in the planted coloring, each vertex has exactly c neighbors of every other color. From the point of view of the vertices, this is a complicated constraint affecting a star of d+1 vertices. As a result, a factor graph with a variable node for each vertex, and a constraint node corresponding to each vertex and its neighbors, is not even locally treelike. Instead, we define a variable for each edge, giving a pair of colors. The constraint then demands that the d edges incident to each vertex agree on its color, and that the colors of their other endpoints are equitable.
  
  This lets us define a message-passing algorithm. Regarding each edge (u,v) of the graph ∼_n,d,k,(k-1)^-1^eq as a pair of directed edges u → v, v→ u, each directed edge u → v sends a message μ^u → v to vertex v consisting of the estimated probabilities μ^u → v_r,s that u and v are color r and s respectively, for each r, s ∈ [k] with r  s. Vertex v then sends out messages μ^v → w to the directed edges (v,w) which are computed as follows:
  
  
    * For each of v's neighbors u other than w, choose a pair of colors (r_u,s_u) independently from the distribution μ^u → v = (μ^u → v_rs).
  
    * Condition on the event that the s_u are identical for all u. Call this color s.
  
    * Condition on the event that all but one of the colors other than s appear c times in the list (r_u), and that one color appears c-1 times. Call this color t.
  
    * Then μ^v → w = (μ^v → w_st) is the resulting conditional distribution of the pair (s,t), i.e., the probability that v and w are color s and t respectively.
  
  Formally we can write
  
      μ^v → w_st = ψ^v → w_st/z^v → w
  
  where
  
      ψ^v → w_st   = ∑_(r_u : u ∈∂ v ∖ k) ∈ [k]^d-1( ∏_u μ^u → v_r_u,s)
      ( ∏_u ∈ [k], u  s |{ u: r_u=u }| =  c     u  s, t 
       c-1     u=t )
      
      
      z^v → w   = ∑_r,s ∈ [k]: r  sψ^v → w_rs  .
  
  
  Clearly the uniform messages μ^u → v_rs = 1/(k(k-1)) are a fixed point of this algorithm. We want to study its stability to small perturbations, and in particular the matrix of partial derivatives
  
      Y_rs, s't = ∂μ^v → w_s't/∂μ^u → v_rs  .
  
  To compute this matrix, suppose that we perturb the incoming message μ^u → v for a pair (r,s) with r  s,
  
      μ^u → v_r's' = 1/k(k-1) (1+δ_rr'δ_ss')
  
  where δ is the Kronecker delta, δ_rr' = 1 if r=r' and 0 otherwise. This perturbation does not respect the normalization ∑_rsμ^u → v_rs = 1, but this will simply show up as Y having zero row and column sums since normalization projects perturbations to the subspace perpendicular to the uniform vector.
  
  We then have several cases. If s'  s, for all t  s' then ψ^v → w_s't is unchanged from its value at the uniform fixed point, namely
  
      ψ^v → w_s't 
      = ( 1/k(k-1))^d-1d-1  c-1, c, …, c 
      = ( 1/k(k-1))^d-1c (d-1)!/c!^k-1ψ  .
  
  For s'=s and t=r, we have
  
      ψ^v → w_st   = ( 1/k(k-1))^d-1( 
      (1+) d-2  c-2, c, …, c + (k-2) d-2  c-1, c-1, c, … c) 
         = ψ( (1+) c-1/d-1 + (k-2) c/d-1) 
         = ψ( 1 +  c-1/d-1)   , 
           (t=r)
  
  where the two terms in the first line come from r_u=r and r_u  r,s respectively. 
  Finally, for s'=s and t  r, we have
  
      ψ^v → w_st   = ( 1/k(k-1))^d-1( 
      (1+) d-2  c-1, c-1, c, …, c 
      + d-2  c-2, c, … c 
      + (k-3) d-2  c-1, c-1, c, … c) 
         = ψ( (k-2 + ) c/d-1 + c-1/d-1) 
         = ψ( 1 +  c/d-1)   , 
           (t  r)
  
  where the three terms in the first line come from r_u=r, r_u=t, and r_u  r,s,t respectively. 
  
  While this level of bookkeeping is comforting, both (<ref>) and (<ref>) are simply ψ (1+ P) where P is the fraction of (d-1)-tuples that contribute to (<ref>) such that r_u=r. We can write (<ref>), (<ref>), and (<ref>) as
  
      ψ^v → w_s't = ψ( 1 + δ_ss'c - δ_rt/d-1).
  
  Summing over all distinct s', t gives the normalization factor 
  
      z^v → w   = k(k-1) ψ + ψ( c-1/d-1 + (k-2) c/d-1) 
         = k(k-1) ψ + ψ
         = k(k-1) ψ( 1 + /k(k-1))   ,
  
  with the multiplicative factor 1+ P where P=1/(k(k-1)) is now the probability that a random edge u → v has colors r and s on its endpoints.
  
  Combining (<ref>) with (<ref>), and (<ref>) gives
  
      μ^v → w_s't 
      = 1/k(k-1)( 1 + ( - δ_ss'δ_rt/d-1 + c δ_ss'/d-1 - 1/k(k-1)) + O(^2) ) 
        .
  
  Canceling the factor 1/(k(k-1)) gives the matrix of partial derivatives (<ref>),
  
      Y_rs, s't 
      = - δ_ss'δ_rt/d-1 + c δ_ss'/d-1 - 1/k(k-1)  .
  
  Using (<ref>) and (<ref>) the reader can check that the rows and columns of Y sum to zero, as alluded to above:
  
      ∀ r,s: ∑_s',t: 
       s'  t Y_rs,s't 
      = 0   , 
        ∀ s',t: ∑_r,s: 
       r  s Y_rs,s't 
      = 0   .
  
  
  To diagonalize Y, it is useful to treat the k(k-1)-dimensional space 𝒰 spanned by ordered pairs (r,s) with r  s as the space of k × k matrices U=(U_rs) with zeroes on the diagonal. Then we can interpret the three terms in (<ref>) as follows:
  
  
    * The term δ_ss'δ_rt is the transpose operator, sending U to U^⊤. 
  
    * The term δ_ss' sends U to (U J)^⊤ where J is the all-1s matrix.
  
    * The term -1/k(k-1) subtracts the mean entry of U from each entry of Y(U).
  
    * Finally, we set all the diagonal elements of Y(U) to zero.
  
  Thus we can rewrite (<ref>) as
  
      Y(U) = Π[ - 1/d-1 U^⊤ + c/d-1 (U J)^⊤ - 1/k(k-1) J U J ]
  
  where Π is the projection operator that sets the diagonal entries of a matrix to zero.
  
  To diagonalize Y, recall that if two linear operators commute, they share the same eigenvectors. Clearly Y commutes with relabelings of the colors, i.e., with the S_k-action that conjugates U with a permutation matrix. This action preserves the following subspaces of matrices:
  
  
    * The symmetric matrices with zero diagonal
  
    * The antisymmetric matrices
  
    * The matrices whose row (resp. column) sums are zero
  
    * The matrices whose rows (resp. columns) are uniform, other than being zero on the diagonal 
  
  …and their intersections. More abstractly, 𝒰 is the k(k-1)-dimensional combinatorial representation where S_k acts on distinct ordered pairs (r,s) by sending (r,s) to (π(r), π(s)). We can find the eigenvectors and eigenvalues of Y by decomposing 𝒰 into a direct sum of irreducible representations of S_k. This decomposition includes one copy of the trivial representation ρ_(k) = 𝕀, and one copy each of ρ_(k-2,1,1) and ρ_(k-2,2). (To avoid some case-checking we assume that k ≥ 4. In particular, if k = 3 then ρ_(k-2,2) disappears.) By Schur's Lemma, when restricted to each of these irreducible subspaces Y is a scalar matrix with a single eigenvalue. These are as follows:
  
  
    * The trivial representation is spanned by the matrix with 1s everywhere off the diagonal. By (<ref>) this has eigenvalue zero. 
  
    * The copy of ρ_(k-2,1,1) consists of antisymmetric matrices with zero row and column sums. These are annihilated by v and are eigenvectors of the transpose with eigenvalue -1. Thus they are eigenvectors of Y with eigenvalue +1/(d-1). This eigenspace has dimension (k-1)(k-2)/2. 
  
    * The copy of ρ_(k-2,2) consists of symmetric matrices with zero row and column sums and zeroes on the diagonal. These are annihilated by v and are eigenvectors of the transpose with eigenvalue +1. Thus they are eigenvectors of Y with eigenvalue -1/(d-1). This eigenspace has dimension (k-1)(k-2)/2 - 1 = k(k-3)/2. 
  
  
  However, we are not done. In addition to these multiplicity-free irreducible representations, 𝒰 includes two copies of the “standard” representation ρ_(k-1,1), one each in the symmetric and antisymmetric subspace. Each one has dimension k-1, and together they span an isotypic subspace of dimension 2(k-1). By Schur's lemma, when restricted to this subspace, Y is the tensor product of the identity with a 2 × 2 matrix, giving it two additional eigenvalues. One of these will turn out to be the dominant one and will control where the Kesten–Stigum transition occurs.
  
  This isotypic subspace is spanned by matrices of the form
  
      U_ij =  
      0     i = j 
      α    i=1, j  1 
      β    j=1, i  1 
      γ    i  1, j  1, i  j
        where  γ = - α+β/k-2  ,
  
  and their images under conjugation by permutation matrices, i.e., where the “special” row and column ranges from 1 to k.
  That is, 
  
      U = [ 0 α α ⋯ α; β 0 γ ⋯ γ; β γ 0   ⋮; ⋮ ⋮   ⋱ γ; β γ ⋯ γ 0 ]
  
  where γ is set so that U's entries sum to zero. The reader can check that these matrices are orthogonal to the other irreducible subspaces with respect to the trace inner product ⟨ U, U' ⟩ =  U^⊤ U'.
  
  Using (<ref>), we find that Y(U) is also of this form but with entries α' and β', where
  
      [ α'; β' ] 
      = m ·[ α; β ]  where   
      m = [      0      1; -1/d-1 -c/d-1 ]  .
  
  Thus Y on this isotypic subspace is m ⊗𝕀 where 𝕀 is the (k-1)-dimensional identity. The corresponding eigenvalues of Y are those of m, namely the roots κ of 
  
      (d - 1) κ^2 + c κ + 1 = 0   ,
  
  which are
  
      κ_± = -c ±√(c^2 - 4(d-1))/2 (d-1)  .
  
  When c^2 < 4(d-1) the discriminant is negative, so these eigenvalues are complex and lie on the unit circle |κ_±| = 1/√(d-1). But when c^2 > 4(d-1) they are real, and κ_+ > 1/√(d-1). 
  
  The full Jacobian of belief propagation is the tensor product of this local matrix Y with the non-backtracking matrix B. It is a consequence of Theorem 2 in <cit.> that, with high probability over  sampled from the equitable SBM with d < d_KS^eq, the spectrum of the non-backtracking matrix consists of a “trivial” eigenvalue d whose left and right eigenvectors is the all-ones vector, and remaining eigenvalues with modulus at most √(d-1) + o_n(1) in the complex plane. Since perturbations along the uniform eigenvector of B would violate the balance of colors, we are left with these remaining eigenavlues. Multiplying κ_+ by √(d-1) + o_n(1) tells us that the Kesten–Stigum transition, where the largest eigenvalue of the Jacobian exceeds 1 in absolute value, occurs when c^2≈4(d-1), with ≈ hiding o_n(1) terms. Given (<ref>) this is 
  
      c ≈ 2 ( (k-1)+√(k(k-2)))
  
  or 
  
      d 
          ≈ 2 (k-1)^2 ( 1 + √(k(k-2)/(k-1)^2))
          ≈2/λ^2( 1 + √( 1-λ^2 ))
  
  where λ = -1/(k-1). Solving this condition for λ in terms of d gives
  
      | λ | = 2√(d-1)/d + o_n(1)   .
  
  
  
  
   §.§ Generalizing to the Equitable Block Model
  
  
  
  Let 
  
      d = a + b(k-1)   .
  
  Recall that a legal labeling of the equitable block model on a d-regular graph is a k-coloring where each vertex has exactly a neighbors of its own color, and exactly b neighbors of each of the k-1 other colors. The case of equitable k-colorings corresponds to a=0 and b=c.
  
  We can generalize the message-passing algorithm of the previous section as follows. 
  Each directed edge (u,v) again sends a message μ^u → v to vertex v consisting of the estimated probability μ^u → v_rs that u and v are color r and s respectively, for each r, s ∈ [k] with r  s. Vertex v then sends out messages μ^v → w to the directed edges (v,w) which are computed as follows:
  
  
    * Give pairs (s,t) the prior distribution
  
      P(s,t) = 1/kd 
      a     (s=t) 
      
      b     (s  t)   .
  
  
    * Multiplicatively reweight this distribution by the probability that, if for each of v's neighbors u other than w we choose a pair of colors (r_u,s_u) independently from the distribution μ^u → v = (μ^u → v_rs), then:
  
  
    * s_u=s for all u, and
  
    * (if s=t) s appears a-1 times in the list (r_u), and every color other than s appears b times, 
  
    * (if s  t) s appears a times in the list (r_u), t appears b-1 times, and all other colors appear b times each.
  
  
    * Then μ^v → w = (μ^v → w_st) is the resulting posterior distribution of (s,t).
  
  
  Generalizing (<ref>) and (<ref>), we can write
  
      μ^v → w_st = ψ^v → w_st/z^v → w
  
  where
  
      ψ^v → w_st   = ∑_(r_u : u ∈∂ v ∖ k) ∈ [k]^d-1( ∏_u μ^u → v_r_u,s)
       a ∏_u ∈ [k] |{ u: r_u=u }| 
      =  
      a-1     u = s 
       b     u  s  
          (s=t)
      
       b ∏_u ∈ [k] |{ u: r_u=u }| =  
      a     u = s 
       
      b-1     u = t 
       
      b     u  s, t 
          (s  t) 
      
      
      z^v → w   = ∑_r,s ∈ [k]: r  sψ^v → w_rs  .
  
  Note that the factors of a and b in (<ref>), which did not appear in the coloring case, come from the prior distribution (<ref>). The reader can check that the prior distribution on (s,t) is now a fixed point of this algorithm, 
  
      μ^u → v_st = 1/kd 
      a     (s=t) 
      
      b     (s  t)   .
  
  At this fixed point, (<ref>) gives
  
      ψ^v → w_st =  
      a ψ    (s=t) 
      
      b ψ    (s  t)
  
  where
  
      ψa^a-1 b^b(k-1)/(kd)^d-1d-1  a-1, b, …, b
      = a^a b^b(k-1)-1/(kd)^d-1d-1  a, b-1, b, …, b
      = a^a b^b(k-1)/(kd)^d-1(d-1)!/a! b!^k-1  ,
  
  and where as always 0^0=0!=1. 
  
  We again consider perturbing the incoming message μ^u → v for a pair (r,s), 
  
      μ^u → v_r's' = (1+δ_rr'δ_ss') 1/kd 
      a     (r=s) 
      
      b     (r  s)   .
  
  As before, if s'  s then ψ^v → w_s't is unchanged for all t, and is still given by (<ref>).  For the other cases where s'=s, let us first assume that r  s. There are now three cases: t=s (now that some neighbors have the same color), t=r, and t ∉{r, s}. We have
  
      ψ^v → w_st   = 
       
      a ψ( 1 +  b/d-1)     t=s 
      
      b ψ( 1 +  b-1/d-1)     t=r 
       
      b ψ( 1 +  b/d-1)     t ∉{r,s}     (r  s)
  
  where in each case we multiply by 1+ P where P is the fraction of (d-1)-tuples that contribute to (<ref>) where r_u=r. Summing over all s', t gives
  
      z^v → w   = kd ψ +  b ψ( b-1/d-1 + (k-2) b/d-1 + a/d-1) 
         = kd ψ +  b ψ
         = kd ψ( 1 + b/kd) 
           (r  s)   .
  
  This multiplicative factor is 1+ P where P=b/(kd) is the prior probability that a random edge u → v has colors r, s on its endpoints where r  s.
  
  Analogously, if r=s=s' we have 
  
      ψ^v → w_st   = 
       
      a ψ( 1 +  a-1/d-1)     t=s 
      
      b ψ( 1 +  a/d-1)     t  s 
           (r = s)   ,
  
  and
  
      z^v → w   = kd ψ +  a ψ( a-1/d-1 + (k-1) b/d-1) 
         = kd ψ +  a ψ
         = kd ψ( 1 + a/kd) 
           (r = s)   ,
  
  where the multiplicative factors are again 1+ P where P is the fraction of (d-1)-tuples contributing to (<ref>), or in (<ref>) the prior probability P=a/(kd) of an edge having colors r=s on its endpoints.
  
  Putting all this together generalizes (<ref>) to
  
      μ^v → w_s't 
      = 1/kd
      a ( 1 + ( δ_ss'a-1/d-1 - a/kd) + O(^2) ) 
          [s'=t, r=s] 
      
      a ( 1 + ( δ_ss'b/d-1 - b/kd) + O(^2) ) 
          [s'=t, r  s] 
       
      b ( 1 + ( δ_ss'a/d-1 - a/kd) + O(^2) ) 
          [s'  t, r=s] 
      
      b ( 1 + ( δ_ss'b - δ_rt/d-1 - b/kd) + O(^2) ) 
          [s'  t, r  s]   ,
  
  the fourth case of which coincides with (<ref>) when a=0 and b=c. Comparing with (<ref>) and accounting for factors of a and b gives the matrix of partial derivatives, 
  
      Y_rs, s't 
      = -δ_ss'δ_rt/d-1 
      + ( δ_ss'/d-1 - 1/kd)  
      a     (s'=t) 
      
      b     (s'  t) 
        .
  
  The reader can check the normalization conditions: the rows of Y sum to zero, so that the uniform vector is a right eigenvector of eigenvalue zero, but the columns are orthogonal to the prior distribution (<ref>) so that it is a left eigenvector of eigenvalue zero. Thus (<ref>) becomes
  
      ∀ r,s: ∑_s',t Y_rs,s't 
      = 0   ,   ∀ s', t: ∑_r,s Y_rs,s't a     (r=s) 
       b     (r  s) 
      = 0   .
  
  
  At the risk of multiplying entities without necessity, we can also write Y in the style of (<ref>). If we think of Y's action by right multiplication on k^2-dimensional vectors as a linear operator on k-dimensional matrices U=(U_s't), then 
  
      Y(U) = -1/d-1 U^⊤ + 1/d-1 (Υ(U) J)^⊤ - 1/kd J Υ(U) J   ,
  
  where J is again the all-1s matrix and Υ is a linear operator on matrices that reweights diagonal and off-diagonal elements by a and b respectively, 
  
      Υ(U)_s't = U_s't 
      a     (s'=t) 
      
      b     (s'  t) 
        .
  
  
  As in the coloring case, we use representation theory to diagonalize Y. The k-dimensional matrices form a k^2-dimensional representation of S_k where permutation matrices act by conjugation. Since this representation sends pairs of colors (r,s) to (π(r), π(s)), this is the tensor product of the natural permutation representation with itself. The permutation representation is a direct sum of the trivial representation (spanned by the uniform vector) with the (k-1)-dimensional standard representation (spanned by vectors that sum to zero). Taking its tensor square and decomposing gives the representations described above, as well as the subspace spanned by diagonal matrices, giving one additional copy each of the trivial representation and the standard representation. 
  
  Thus in total we have a two-dimensional trivial subspace, one copy each of ρ_(k-2,1,1) and ρ_(k-2,2) with dimension (k-1)(k-2)/2 and k(k-3)/2 respectively, and a 3(k-1)-dimensional subspace consisting of three copies of the standard representation ρ_(k-1,1). We go through each of these subspaces, focusing on Y's right eigenvectors.
  
  First, the trivial subspace is spanned by the identity matrix 𝕀=(δ_s't) and the all-1s matrix J. As in (<ref>) J is a right eigenvector with eigenvalue zero, so Y(J)=0. Observing (<ref>), we have 𝕀^⊤ = 𝕀, Υ(𝕀) = a 𝕀, 𝕀=, and 𝕀 =k. This gives
  
      Y(𝕀) 
      = -1/d-1𝕀 + ( a/d-1 - a/d) 
      = -1/d-1𝕀 + a/d(d-1).
  
  Thus in this two-dimensional subspace Y acts as the matrix 
  
      1/d-1[  -1   0; a/d   0 ]
  
  giving the eigenvalues -1/(d-1) and 0.
  
  Next, as before the copy of ρ_(k-2,1,1) consists of antisymmetric matrices U with zero row and column sums. For these matrices we have Υ(U) = bU and UJ=0, while U^⊤ = -U. Thus they are again eigenvectors of Y with eigenvalue +1/(d-1).
  
  The copy of ρ_(k-2,2) consists of symmetric matrices U with zero row and column sums and zeroes on the diagonal. Now we have Υ(U) = bU, UJ=0, and U^⊤ = U, and (<ref>) again makes them eigenvectors with eigenvalue -1/(d-1). 
  
  This leaves the three copies of the standard representation. This isotypic subspace is spanned by matrices like those in (<ref>) but with nonzero diagonal entries, namely
  
      U_ij = δ    i=j=1 
      ζ    i=j  1 
      α    i=1, j  1 
      β    j=1, i  1 
      γ    i  1, j  1, i  j
        where  γ = - α+β/k-2  and  ζ = -δ/k-1  ,
  
  and their images under conjugation by permutation matrices, i.e., where the “special” row and column ranges from 1 to k.
  That is, 
  
      U = [ δ α α ⋯ α; β ζ γ ⋯ γ; β γ ζ   ⋮; ⋮ ⋮   ⋱ γ; β γ ⋯ γ ζ ]
  
  where γ and ζ are set so that U's entries sum to zero and U has zero trace. In particular, U is orthogonal to both  and 𝕀, and hence to the trivial subspace. The reader can confirm that It is orthogonal to ρ_(k-2,1,1) and ρ_(k-2,2) as well.
  
  Using (<ref>) and a little work, we find that Y(U) is also of this form but with entries α', β', δ', where
  
      [ α'; β'; δ' ] 
      = m ·[ α; β; δ ]  where   
      m = 1/d-1[       -b       -1   -a/k-1; b(k-1)-1        0        a;   b(k-1)        0      a-1 ]  .
  
  Thus Y on this isotypic subspace is m ⊗𝕀 where 𝕀 is the (k-1)-dimensional identity. The corresponding eigenvalues of Y are those of m, which are namely the roots κ of 
  
      -1/d-1  and  κ_± = a - b ±√( (a - b)^2 - 4 (d - 1) )/2 (d-1)  .
  
  Analogous with the coloring case, if (a-b)^2 < 4(d-1) these eigenvalues are complex and lie on the unit circle |κ_±| = 1/√(d-1). But when (a-b)^2 > 4(d-1), they are real, and κ_+ > 1/√(d-1).  
  
  We again multiply κ_+ by the modulus of the largest non-trivial eigenvalue of the non-backtracking matrix, √(d-1) + o_n(1), to obtain the dominant eigenvalue of the Jacobian of belief propagation. The Kesten–Stigum transition occurs when this eigenvalue exceeds the unit circle, or when 
  
      (a-b)^2 = 4(d-1) + o_n(1)  .
  
  Since in the equitable block model we have
  
      λ = a-b/d  ,
  
  this again occurs at 
  
      | λ | = 2 √(d-1)/d + o_n(1)  .
  
  
  
  
  
  
  § LOCAL STATISTICS
  
  
  
  Throughout this section, we will for the sake of brevity write = (_n) for the uniform distribution _n,d on d-regular graphs, and = (_n) for the equitable stochastic block model _n,k,d,η^eq from Definition <ref>. 
  
  As in the preceding text, we are most concerned with the behavior of the null and planted models when the number of vertices is very large, and we will write with high probability (w.h.p.) to describe a sequence of events that hold with probability 1 - o_n(1) in _n or _n as n→∞, with other parameters (d,k,η) held fixed. The constant in the o_n(1) may depend on these other parameters, and we will not make any attempt to quantify its rate, leaving us free to take union bounds over constantly many events.
  
  In this section we study a family of semidefinite programming algorithms for the  vs.  distinguishing problem. Like Sum of Squares, the Local Statistics algorithm is phrased in the language of polynomials. Let us define a set of variables x = {x_u,i} indexed by vertices u ∈ [n] and group labels i ∈ [k], and G = {G_u,v} indexed by pairs of distinct vertices. We think of the planted model as outputting a random evaluation of these variables, namely a pair (,), where ∈^n× k encodes the hidden community structure—with _u,i = 1 if (u) = i and zero otherwise—and ∈^[n] 2 is the Boolean vector indicating which edges are present in the graph. This allows us to regard polynomials p ∈[x,G] as statistics of the planted distribution , and we will in particular focus on the quantities _(,)∼  p(,). 
  
  The planted model outputs random variables  and  with a particular combinatorial structure: each variable is {0,1}-valued, and each vertex has exactly one label. This can be encoded in a set of polynomial constraints:
  
      G^2_u,v - G_u,v   = 0       ∀ (u,v) ∈[n]  2
      
          x^2_u,i - x_u,i   = 0       ∀ u ∈ [n], i ∈ [k] 
      ∑_i∈ [k]x_u,i - 1    = 0       ∀ u ∈ [n].
  
  Calling ℐ_k the ideal of [x,G] generated by the polynomials on the left hand side of the equations above, then for any p ∈ℐ_k, p(,) = 0. Moreover, the planted distribution has a pleasant symmetry property: the symmetric group S_n acts naturally and simultaneously on the variables x and G, with a permutation ξ acting as x_u,i↦ x_ξ(u),i and G_u,v↦ G_ξ(u),ξ(v), and for any polynomial p ∈[x,G], the expectation _(,)∼ p(,) is constant on the orbits of this action. The Local Statistics algorithm, given as input a graph G_0, endeavors to find a “pseudoexpectation” that mimics the conditional expectation [ · | G_0] on polynomials p(x,G_0) of sufficiently low degree. 
  
  
      
      The degree-(D_x,D_G) Local Statistics algorithm is the following SDP: given an input graph G_0, find : [x]_≤ D_x→ s.t.
      
          
    * (Positivity) p(x)^2 ≥ 0 whenever p^2 ≤ D_x 
          
    * (Hard Constraints) p(x,G_0) = 0 for every p ∈ℐ_k
          
    * (Moment Constraints) p(x,G_0) ≈_(,)∼ p(,) whenever _G p(x,G) ≤ D_G, _x p(x,G) ≤ D_x, and p is fixed under the S_n action.
      
  
  See, e.g., the survey <cit.> for detailed discussion of how optimization problems of this form can be solved as SDPs.
  
  We use the Local Statistics SDP for the  vs.  hypothesis testing problem as follows: given  sampled from one of these two distributions, we run Local Statistics, outputting p if the SDP is feasible, and q otherwise. The symbol ≈ in the moment constraints indicates that we will permit some additive error; this is necessary so that, when ∼, the SDP is with high probability satisfiable, by setting p(x,G_0) =  p(,). In fact, we will instantiate these moment constraints only on the elements of a certain combinatorially meaningful basis, and we will allow different additive error for different basis elements. In so doing we automatically satisfy positivity and the hard constraints, and the additive slack allows for for fluctuations of the p(,) around their expectations. When we make this precise below, we will write this additive slack in terms of an `error tolerance' δ > 0. 
  
  
      Let  and  be as in Definition <ref>. If (dη)^2 > 4(d-1) then there exists δ > 0 so that the degree (2,2) Local Statistics algorithm with error tolerance δ can distinguish  and . If (dη)^2 ≤ 4(d-1), then there do not exist such a D and δ.
  
  
  The proof of Theorem <ref> closely follows <cit.>. As in that work, we will first study a simpler SDP hierarchy for the  vs.  hypothesis testing problem, and then show that its feasiblity is equivalent to that of degree (2,D) local statistics SDP.  We begin with some standard facts about non-backtracking walks, which will be a central tool in our analysis.
  
  
  
   §.§ Non-Backtracking Walks
  
  
  
  Let A_G be the adjacency matrix for a d-regular graph G (which may have self-loops and multi-edges). A length-s non-backtracking walk on G is an alternating sequence of vertices and edges v_1, e_1,v_2,e_2,...,v_s without terms of the form v,e,w,e,v. The matrices sG whose u,v entries count the number of such walks between vertices u and v are given by
  
      0G   = 1 
      1G   = A_G 
      2G   = A^2_G - d 
      s+1G   = AsG - (d-1)s-1G     s ≥ 2.
  
  In particular, sG = q_s(A_G), for a sequence of monic univariate polynomials q_s ∈[z], with q_s = s, which are known to be orthogonal with respect to the Kesten-McKay measure
  
      d(z) d/2π√(4(d-1) - z^2)/d^2 - z^2|z| <  dz
   
  on the interval (-,). This fact has appeared innumerable times in the literature, dating back at least to <cit.>. Thus the polynomials q_s are a basis for the Hilbert space of square integrable functions on this interval, equipped with the inner product
  
      ⟨ f, g ⟩_∫ f(z)g(z) d(z),
  
  and associated norm
  
      f_^2 ⟨ f, f ⟩_ = ∫ f(z)^2 d(z),
  
  and in particular for any polynomial f ∈[z], we have the orthogonal decomposition
  
      f = ∑_s ≥ 0⟨ f, q_s ⟩_/q_s^2_q_s.
  
  
  We record for later use that
  
      q_s_^2 = q_s(d) =  1     s=1 
       d(d-1)^s-1    s > 1 ;
  
  this is equal to the number of vertices at depth s in a rooted d-regular tree, or equivalently n^-1 times the total number of length-s non-backtracking walks in a d-regular graph on n vertices. For a derivation of this and other related facts, the reader may refer to <cit.> or <cit.>, but should beware of differing normalization conventions.
  
  We will also require some standard and generic properties sequences of univariate polynomials orthogonal with respect to a measure on an interval of  <cit.>: each q_s has s roots in the interval (-,), the union of these roots over all s ≥ 0 are dense in this interval, and we have a nonnegative quadrature rule
  
   
      For each s, call r_1 < r_2 < ⋯ < r_s there roots of q_s. There exist weights w_1,...,w_s ≥ 0 with the property that
      
      ⟨ f, q_s ⟩_ = ∑_i ∈ [s] f(r_i) q_s(r_i) w_i
  
      for every polynomial f of degree at most 2s - 1.
  
  
  
  
   §.§ The Symmetric Path Statistics SDP
  
  
  In this section we study a simplified version of the Local Statistics SDP, which will ultimately be key to our analysis of the full Local Statistics SDP. Let (,) ∼, thinking of  as a collection of k vectors _1,...,_k ∈{0,1}^n. One can check that the partition matrix for the planted labelling, in the sense of Definition <ref>, is
  
      k/k-1(∑_i ∈ [k]_i _i^⊤ - 1/k_k ) 
      Since deterministically _1 + ⋯ + _k = 1, we as well have   = k/k-1(∑_i ∈ [k]_i_i^⊤ - 1/k∑_i,j_i_j^⊤)
  
  As we observed in the Introduction,  is PSD with ones on the diagonal, and (k/n) is the orthogonal projector onto the (k-1)-dimensional subspace spanned by _1,...,_k and orthogonal to the vector of all-ones.
  
  We will be particularly interested in the inner products ⟨, s⟩, which count non-backtracking walks on , with weight 1 if the endpoints share a group label, and -(k-1)^-1 if they do not. The following is a consequence of Lemma <ref> in the sequel.
  
  
      For every s ≥ 1 and increasing, nonnegative function Δ(n),
      
      [ | ⟨, s⟩ - q_s(dη) n | > Δ(n) ] = O(n/Δ(n)^2).
  
  
  
  The Symmetric Path Statistics SDP, given as input a graph G_0, attempts to find a “pseudo-partition matrix,” i.e. PSD matrix with ones on the diagonal, and whose inner products with the matrices sG_0 are equal to q_s(dη)n, at least up to the fluctuations in Lemma <ref>.
  
  
      
      The level-D Symmetric Path Statistics Algorithm with error tolerance δ > 0, on input a d-regular graph G_0 on n vertices, is the following SDP: find P≽ 0 so that
      
          
    * P_u,u = 1 for every u ∈ [n]
          
    * ⟨P, _n ⟩∈ [-δ n^2, δ n^2]
          
    * ⟨P, sG_0⟩∈ q_s(dη)n + [-δ n, δ n] for every s ∈ [D].
      
  
  
  
      
      Let  and  be as in Definition 8.1. If (dη)^2 > 4(d-1), then for every D ≥ 2 there exists an error tolerance δ > 0 at which the level D Symmetric Path Statistics SDP can w.h.p. distinguish  and . If (dη)^2 ≤ 4(d-1), then no such D and δ exist.
  
  
  
      By Lemma 8.5, this SDP is with high probability feasible on input ∼. Our proof will therefore show that when η^2 is sufficiently large, the SDP for some constant D is infeasible on input ∼, whereas for η^2 sufficiently small, it is feasible for every constant D. 
      
      First, fix D ≥ 2 and assume (dη)^2 > 4(d-1). We will show that there exists δ > 0 so that with high probability the level-D Symmetric Path Statistics is infeasible on input ∼. Our strategy will be to find a polynomial f ith the property that f(A_) ≽ 0 with high probability, but we can deduce ⟨ P, f(A_) ⟩ < 0 from the affine constraints in Definition <ref>.
      
      Let f be a degree D polynomial which is strictly positive on the closed interval [-2√(d-1),2√(d-1)] and satisfies f(dη) < 0; our assumption on η ensures that this is possible, for instance by setting f(z) = 2(d-1) + 12(dη)^2 - z^2. From our preliminaries on non-backtracking walks and the polynomials q_s we know
      
      f = ∑_s = 0^D ⟨ f,q_s⟩_/q_s^2_  q_s.
  
      When ∼, A_ has an eigenvalue at d whose eigenvector is the all-ones vector and by Friedman's Theorem <cit.> its remaining eigenvalues with high probability have absolute value at most 2√(d-1) + o(1). Our assumptions on f therefore imply f(A_) - f(d)/n = f(A_ - d/n) ≽ 0 with high probability.
      
      On the other hand, if ≽ 0 is a feasible solution for the degree-D Symmetric Path Statistics SDP on input ∼_n, then
      
      0 
                 ≤⟨, f(A_) - f(d)/n ⟩
         = ∑_s = 0^D ⟨ f, q_s ⟩_/q_s^2_⟨, q_s(A_)⟩ + δ |f(d)| n 
         ≤∑_s = 0^D ⟨ f,q_s ⟩_/q_s^2_q_s(dη) n + δ( f^2_ + |f(d)|)n 
         = (f(dη) + δ( f^2_ + |f(d)|))n < 0,
  
      if we set δ sufficiently small.
      
      We can now turn to the case (dη)^2 ≤ 4(d-1), seeking to prove that on input ∼, with high probability every level of the Symmetric Path Statistics hierarchy is feasible, for every error tolerance δ. We will use the following lemma, which may be proved by adapting the proof of <cit.>. The proof proceeds by setting  equal to a mild modification of the matrix g(A_) - g(d)_n/n.[The referenced result in <cit.> was proved for an SDP which shared constraints (1) and (2) from Definition <ref>, but in which constraint (3) read ⟨ P,sG_0⟩ = λ^s q_s^2_ n. The proof may be adapted simply by adopting the hypotheses below, changing every instance of the aforementioned constraints, and taking some care with the δ slack.]
      
      
          
          Assume there exists a constant-degree polynomial g ∈[z] that is strictly positive on [-2√(d-1),2√(d-1)] and satisfies
          
      ⟨ g, q_s⟩_∈ q_s(dη) + [-δ,δ].
  
          for every s = 1,...,D. Then the level-D Symmetric Path Statistics SDP with error tolerance δ is w.h.p. feasible on input ∼.
      
      
      Lemma 8.9 in hand, we need only to construct such a polynomial. Assume that (dη)^2 ≤ 4(d-1), so that dη∈ [-2√(d-1),2√(d-1)], the interval in which lie the roots of every polynomial q_s. Let P ≫ D, and write r_1 < r_2 < ⋯ < r_P for the roots of q_P. Let I ⊂ [P] contain the indices of the (D + 1)/2 roots of q_P closest to dη, and set
      
      g_η = 1/ζ∏_i ∉ I(z - r_i)^2,
  
      where ζ is a normalizing factor to ensure that ⟨ g_η, 1 ⟩_ = 1. 
      
      This polynomial is certainly nonnegative, and its degree is 2P - D - 1. From Lemma 8.4, then, there exist w_1,...,w_P ≥ 0 so that for any s = 0,...,D
      
      ⟨ g_η, q_s ⟩_ = ∑_i ∈ I w_i g_η(r_i) q_s(r_i).
  
      In particular, setting s = 0 and recalling the definition of ζ, we have
      
      1 = ⟨ g_η, 1 ⟩_ = ∑_i ∈ I w_i g_η(r_i).
  
      This means that for any s = 0,...,D, the inner product ⟨ g_η, q_s ⟩ is a weighted average of q_s evaluated at the (D + 1)/2 roots of q_P closest to the point dη. Since the roots of the q polynomials are dense in (-2√(d-1),2√(d-1)), and dη is in the closure of this interval, for each D and δ > 0, there exists a constant P for which |⟨ g_η, q_s ⟩_ - q_s(dη)| < δ for every s = 0,..,D. 
  
  
  
  
   §.§ Partially Labelled Subgraphs
  
  
  We are now ready to study the full Local Statistics algorithm. To start, we will need to develop a basis for the symmetric polynomials appearing as affine moment matching constraints in Definition <ref>. Because p(,) = 0 for any p ∈ℐ_k, a constraint shared by the pseudoexpectation, it would suffice to study the subspace of [x,G]/ℐ_k fixed under the S_n action inherited from [x,G]. However, it is computationally favorable to work in a slightly larger vector space instead.
  
  
      
      Let us write 𝕊[x,G]_≤ D_x,D_G⊂[x,G] for the vector space of polynomials that (1) satisfy _x ≤ D_x and _G ≤ D_G, (2) are symmetric with respect to the S_n action, (3) are multilinear in G and x, and (4) for which at most one of x_u,1,...,x_u,k appears in each monomial, for every u ∈ V.
  
  
  Every polynomial appearing as a moment constraint in the level-(D_x,D_G) Local Statistics algorithm belongs to 𝕊[x,G]_≤ D_x,D_G. We now give a combinatorially structured basis for this vector space, similar to the `shapes' of <cit.>.
  
  
      
      A partially labelled graph (H, S, τ) consists of a graph H, a subset S ⊂ V(H), and a map τ : S → [k]; we say that a graph is fully labelled if S = V(H), and in this case write (H,τ) for short. A homomorhism from (H,S,τ) into a fully labelled graph (G,σ) is a map ϕ : V(H) → V(G) that takes edges to edges and agrees on labels; an occurrence of (H,S,τ) in (G,σ) is an injective homomorphism. For each partially labelled graph (H,S,τ) there is an associated polynomial in 𝕊[x,G],
      
      p_(H,S,τ)(x,G) = ∑_ϕ : V(H)  [n]∏_(u,v) ∈ E(H)G_ϕ(u),ϕ(v)∏_u ∈ Sx_ϕ(u),τ(u).
  
      Each point in the zero locus of ℐ_k may be identified with a fully labelled graph (G,σ). Evaluated at such a point, this polynomial counts the number of occurrences of (H,S,τ) in (G,σ). Finally, _x p_(H,S,τ) = |S| and _G p_(H,S,τ) = |E(H)|.
  
  
  
      
      The polynomials p_(H,S,τ) with |E(H)| ≤ D_G and |S| ≤ D_x are a vector space basis for 𝕊[x,G]_≤ D_x,D_G
  
  
  
      Let s : [x,G] →𝕊[x,G] be the map that sends a polynomial p to the sum over its S_n orbit. The vector space 𝕊[x,G]_≤ D_x,D_G is spanned by the images under s of the multilinear monomials with x-degree D_x and G-degree D_G in [x] in which at most one of x_u,1,...,x_u,k appears for each u ∈ [n]. From each such monomial m(x,G) one can extract a partially labelled graph (H_m,S_m,τ_m), where |S_m| ≤ D_x, |E(H_m)| ≤ D_G, and H_m is a subgraph of the complete graph: E(H_m) is the union of all pairs (u,v) appearing as an index of a G variable, S_m is the union of all u occurring as an index of an x variable, V(H_m) is the union of S and the endpoints of every edge, and τ(u) = i if the variable x_u,i appears. Because S_n acts transitively on [n], the orbit of m(x) corresponds to every possible injection V(H_m)  [n], and thus
      
      s(m(x,G)) = p_(H_m,S_m,τ_m)(x,G).
  
      This shows that the p_(H,S,τ) span. To see that they are independent, observe that each monomial appears as a term in exactly one p_(H,S,τ). 
  
  
  In view of this lemma, the moment constraints in Definition <ref> are equivalent to the requirement that p_(H,S,τ)(x,G_0) ≈ p_(H,S,τ)(,) for every (H,S,τ) with at most D_G edges and D_x distinguished vertices, up to isomorphism. In order to instantiate and analyze the Local Statistics algorithm, we now need to compute these expectations, and bound the fluctuations around them.
  
  
  
   §.§ Local Statistics in the Planted Model
  
  
  Instead of working directly in , we will as usual work in the configuration model , a distribution on multigraphs with two key properties: (i) with probability bounded away from zero as n→∞, ∼ is simple, and (ii) the conditioal distribution of  on this event is equal to . In this model, conditional on a balanced partition σ, we adorn each vertex in every group i with dM_i,j `half-edges' labelled i → j, and then for each i,j ∈ [k] randomly match the i→ j half-edges with the j→ i half-edges. When k = 1, this is the usual configuration model on d-regular graphs, and when k=2 and M_i,i = 0, it gives bipartite regular graphs. Thus many results we prove for  will apply to  as well. 
  
  
      
      Write 𝒢_n and 𝒢_n for the sets of all d-regular, n-vertex graphs and multigraphs, respectively. If ℰ_n ⊂𝒢_n is a sequence of events holding w.h.p. in _n, then ℰ_n ∩𝒢_n holds w.h.p. in _n.
  
  
  
      Since _n[𝒢_n] is bounded away from zero and [ℰ_n] = 1 - o_n(1), we have
      
      _n[ℰ_n ∩𝒢_n] = _n[ℰ_n ∩𝒢_n]/_n[𝒢_n]≥_n[𝒢_n] - o_n(1)/_n[𝒢_n] = 1 - o_n(1).
  
  
  
  As a warm-up, let us recall some standard calculations of subgraph probabilities in these two simpler situations. 
  
  
      
      Let  be a multi-graph produced by the d-regular configuration model on n vertices. If H is a simple graph, the probability that a fixed injection ϕ : V(H)  V() is a homomorphism is
      
      ∏_v ∈ V(H)d!/(d - (v)) !·(dn - 2|E(H)|-1)!!/(dn - 1)!! = ∏_v ∈ V(H)d!/(d - (v))!· (dn)^-|E(H)| + O(n^-|E(H)| - 1).
  
      Similarly, let (,σ) be generated by the d-biregular configuration model on 2n vertices, σ : V() → [2] its left/right labelling. If (H,τ) is a simple bipartite graph with left/right labelling τ, then the probability that a fixed injection ϕ :V(H)  V() agreeing on labels is a homomorphism is
      
      ∏_v∈ V(H)d!/(d - (v))!·(dn - |E(H)|)!/(dn)! =  ∏_v∈ V(H)d!/(d - (v))!· (dn)^-|E(H)| + O(n^-|E(H)| - 1).
  
  
  
  
      In the case of the d-regular configuration model, once an injective ϕ has been chosen, there are d!(d - (v))! ways to choose (v) stubs from the d available at each vertex v to be matched with the appropriate stubs at each intended neighbor of v, and then (d_n - 2|E(H)| - 1)!! ways to match the remaining stubs. On the other hand, the total number of multi-graphs possible to output is (dn - 1)!!. The calculation is analogous in the bipartite regular case.
  
  
  We will use Lemma <ref> to compute local statistics in the planted model, but first we will need a bit more notation. Let (H,S,τ) be a partially labelled graph, and τ an extension of τ, i.e. τ: V(H) → [k], and τ|_S = τ; for each i,j ∈[k] and u ∈ V_i(H), write _j(u) for the number of neighbors that u has in group j according to τ. Let us define
  
      (dM)^(H,S)_τ∑_τ: τ|_S = τ∏_v ∏_j ∈ [k] dM_τ(v), j (dM_τ(v),j - 1) ⋯ (dM_τ(v),j - _i → j(v) + 1)/∏_(u,v) ∈ E(H) dM_τ(u),τ(v)
  
  if dM_i,j≥_j(v) for every i,j ∈ [k] and v ∈τ^-1(i), and zero otherwise. Note that this operation is multiplicative on disjoint unions: 
  
      (dM)_τ_1 ⊔τ_2^(H_1⊔ H_2,S_1⊔ S_2) = (dM)_τ_1^(H_1,S_1) (dM)_τ_2^(H_2,S_2).
  
  Finally, let us write χ(H)  |V(H)| - |E(H)| and (H) for the number of connected components.
  
  Since we are aiming to prove high probability statements regarding p_(H,S,τ)(,) for (,) ∼ by studying the configuration model, we need to extend the quantities p_(H,S,τ)(x,G) to the case when G is a multigraph with self-loops. For convenience, we will define an occurrence of (H,S,τ) in a fully labelled, loopy multigraph as an occurence of (H,S,τ) in the simple graph obtained by deleting all self-loops and merging all multiedges between each pair of vertices. Our key lemma computes the expected number of occurrences in the configuration model.
  
  
      
      Let (H,S,τ) be a partially labelled graph on O(1) edges, and  (,) be drawn from the configuration model . Then
      
      p_(H,S,τ)(,) = (n/k)^χ(H)(dM)^(H,S)_τ + O(n^χ(H) - 1).
  
  
  
  
      Let V() = [n], fix a labelling σ : [n] → [k], and let  be drawn from the configuration model. Fix an extension τ of τ. If ϕ: V(H)  V() is an injection that agrees on labels, applying Lemma 8.9 to the multigraphs on each set of vertices σ^-1(i) and between each pair of sets σ^-1(i) and σ^-1(j),
      
      [ϕ is an occurrence]    = (n/k)^|E(H)|·∏_i≤ j (dM_i,j)^-|E_i,j(H,τ)|·∏_v ∈ V(H,τ)∏_i,j(d M_i,j)!/(dM_i,j - _j(v))!
              + O(n^-|E(H)| - 1),
  
      and there are (n/k)^V(H) + O(n^|V(H)| - 1) injective choices for ϕ that agree on labels.
      
      Finally, writing Φ(H,S,τ) for the total number of occurrences of (H,S, τ) in , and Φ(H,τ) for the number of occurrences of the fully labelled graph (H,τ),
      
      Φ(H,S,τ)
                 = ∑_τ: τ|_S = τΦ(H,τ) 
         = (n/k)^χ(H) (dM)^(H,S)_τ + O(n^|V(H)| - |E(H)| - 1).
  
  
  
  This lemma has some immediate consequences. First, it tells us that occurrences of partially labelled forests are sharply concentrated.
  
  
      
      Let (H,S,τ) = _t ∈ [(H)] (H_t,S_t,τ_t) be a partially labelled graph with O(1) vertices, (H) connected components H_t, and no cycles. Then for any function f(n) > 0, 
      
      [| p_(H,S,τ)(,) - (n/k)^(H)∏_t ∈ [(H)] (dM)^(H_t,S_t)_τ_t| > f(n) ]    = O(n^2(H) - 1/f(n)^2).
  
  
  
  
      The expectation [p_(H,S,τ)(,)^2] is a sum over all pairs of injective, label-consistent maps ϕ_1,ϕ_2, of the probability that both maps are occurrences. The image of two disjoint copies of H under these two injective maps is a graph H' that is either H⊔ H, or is obtained by identifying some pairs of vertices whose τ labels agree—each pair with one vertex from each copy of H. We can promote H' to a partially labelled graph by taking the induced partial labelling τ' from τ. Thus, let us think of the pair ϕ_1,ϕ_2 as a single injective map φ :V(H')  V() that agrees with τ'. Thus
      
      [p_(H,S,τ)(,)^2]
                 = ∑_H' p_(H',S',τ')(,) 
         = ∑_H'((n/k)^χ(H') (dM)_τ'^(H',S' + O(n^χ(H') - 1)).
  
      When H' = H⊔ H, from our observation above
      
      (dM)_τ'^(H',S') = ((dM)_τ^(H,S))^2 = (∏_t ∈ [(H)] ((dM)_τ_t^(H_t,S_t)))^2.
   
      As H has no cycles, every other H' satisfies χ(H') < 2χ(H). Thus since (H) = χ(H), the assertion is true in the configuration model by Chebyshev, and transfers immediately to the planted model. For good measure, an application of the triangle inequality shows as well that
      
      [ | p_(H,S,τ)(,) - ∏_t ∈ [(H)]p_(H_t,S_t,τ_t)(,)| > f(n) ] = O(n^2(H) - 1/f(n)^2).
  
  
  
  Thus with high probability, the counts of partially labelled forests enjoy concentration of ± o(n^(H)). On the other hand, an immediate application of Markov in  tells us that there are very few occurrences of partially labelled graphs with cycles.
  
  
      
      Let (H,S,τ) be a partially labelled graph with O(1) edges and at least one cycle. Then for any function f(n) > 0,
      
      [ p_(H,S,τ)(,) > f(n)] = O(n^(H) - 1/f(n)).
  
  
  
  In particular, we will need later on the fact that there are very few vertices within constant distance of a constant length cycle. The proof is once again Markov, combined with a union bound.
  
  
      
      Let ∼ or . Fix constants L and C, and call a vertex bad if it is at most L steps a way from a cycle of length at most C. Then w.h.p. there are fewer than f(n) bad vertices, for any increasing function f(n).
  
  
  We can now restate the local statistics algorithm more precisely. 
   
  
      
      The degree-(D_x,D_G) Local Statistics algorithm with error tolerance δ is the following SDP. Given an input graph G_0, find : [x]_≤ D_x→ s.t.
      
          
    * (Positivity) p(x)^2 ≥ 0 whenever p^2 ≤ D_x 
          
    * (Hard Constraints) p(x,G_0) = 0 for every p ∈ℐ_k
          
    * (Moment Constraints) For every (H,S,τ) with at most D_x distinguished vertices, D_G edges, and ℓ connected components,
          
      p_(H,S,τ)(x,G_0) = (dM)_τ^(H,S)(n/k)^χ(H)±δ n^(H).
  
      
  
  
  The n^χ(H) vs. n^(H) scaling may seem ad hoc, but as promised above we have arranged things so that the the SDP is w.h.p. feasible when its input is drawn from the planted model.
  
  
      
      Fix D_x,D_G constant, and δ > 0. with high probability, the degree-(D_x,D_G) Local Statistics Algorithm with error tolerance δ is feasible on input ∼.
  
  
  
      Let (,) ∼, and for each p(x,G) ∈[x,G]_≤ D_x,D_G define
      
      p(x,) = p(,).
  
      This satisfies positivity, as p(x,)^2 = p(,)^2 ≥ 0, and obeys the hard constraints because (,) lies in the zero locus of ℐ_k. Finally, let (H,S,τ) be a partially labelled graph. If H has a cycle, then by Corollary 8.15, w.h.p.
      
      |p_(H,S,τ)(,) - (n/k)^χ(H) (dM)_τ^(H,S)| ≤ p_(H,S,τ)(,) + O(n^χ(H)) ≤δ n^(H).
  
      On the other hand, if H has no cycles, then χ(H) = (H) and w.h.p.
      
      |p_(H,S,τ)(,) - (n/k)^χ(H)(dM)_τ^(H,S)| ≤δ n^(H)
  
      by Proposition 8.14. There are only constantly many partially labelled subgraphs with at most D_x vertices and D_G edges, so a union bound finishes the proof.
  
  
  Finally, we end this subsection with the proof of Lemma <ref>, which concerned the affine constraints in the Symmetric Path Statistics SDP
  
  
      Recall the partition matrix
      
      = k/k-1(∑_i ∈ [k]_i _i^⊤ - 1/k∑_i,j ∈ [k]_i _j^⊤)
  
      from Section 8.2, where each _i ∈{0,1}^n is the indicator vector for membership in the ith group. We are interested in ⟨, s⟩.
      
      Let (P_s,{0,s},{i,j}) denote a path of length s with distinguished endpoints labelled i and j, and write its vertices as V(P_s) = {0,1,...,s}. From Lemma <ref>, w.h.p. for (,)∼,
      
      p_(P_s,{0,s},{i,j}(,) = 1/k (dM)_i,j^(P_s,{0,s}n ± o(n).
  
      Expanding the right hand side,
      
      (dM)_i,j^(P_s,{0,s}))   = ∑_τ: τ|_S = τ∏_v ∈ V(P_s)∏_j' ∈ [k] dM_τ(v),j'(dM_τ(v),j' - 1)⋯(dM_τ(v),j' - _j(v))/∏_(u,v) ∈ E(P_s) dM_τ(u),τ(v)
         = ∑_τ: τ|_S = τ dM_i,τ(1)∏_t = 1,...,s-1(dM_τ(t),τ(t+1) - {τ(t+1)=τ(t-1)}) 
         = q_s(dM)_i,j.
  
      The expression in the second to last line counts the number of non-backtracking walks of length s between vertices i and j on the multi-graph whose adjacency matrix is dM; from Section <ref> these may be enumerated using the polynomial q_s applied to dM. 
      
      Now, let us define s as the n× n matrix whose entries count self-avoiding (as opposed to non-backtracking) walks on . By definition
      
      p_(P_s,{0,s},{i,i})(x,) = ∑_u,v(s)_u,v· x_u,ix_v,j.
  
      Thus, with high probability
      
      ⟨, s⟩   = k/k-1(∑_i p_(P_s,{0,s},{i,i})(,) - 1/k∑_i,jp_(P_s,{0,s},{i,j})(,)) 
         = 1/k-1⟨ q_s(dM), 𝕀 - /k ⟩ n ± o(n) 
         = 1/k-1( q_s(dM) - q_s(d)) n + o(n)
         = q_s(dλ)n + o(n).
  
      The last equality follows from the fact that the spectrum of dM consists of an eigenvalue d with multiplicity one, and an eigenvalue dλ with multiplicty k-1.
      
      We need finally to ensure that the same inner product constraint holds for the matrices s. It is an easy consequence of Lemma 8.16 that w.h.p. for ∼, the matrices s and s disagree in at most o(n) rows. Thus, since the L^1 norm of every row is bounded by a constant (by degree-regularity), w.h.p. s - s_F^2 = o(n). Since X is PSD with ones on the diagonal, every off-diagonal element has magnitude at most one—thus
      
      ⟨ X,s⟩ = ⟨ X,s⟩ + o(n),
  
      and we are done.
  
  
  
  
   §.§ Proof of Theorem <ref>: Upper Bound
  
  
  We will show that if (dλ)^2 > 4(d-1), then the degree (2,D) Local Statistics algorithm can distinguish  and  for every D ≥ 2. Specifically, we will show that for any such D, with high probability over input ∼ there exists a δ at which the SDP is infeasible. Our goal, here and in the proof of the lower bound, will be to reduce to our characterization of the Symmetric Path Statistics SDP in Theorem 8.7.
  
  Assume that  is a feasible pseudoexpectation for the degree (2,D) Local Statistics SDP with tolerance δ>0, on input ∼, and consider the matrix X with entries
  
      _u,v = k/k-1(∑_i ∈ [k] (x_u,i - 1/k)(x_v,i -  1/k)) = k/k-1(∑_i ∈ [k] x_u,ix_v,i -  1/k∑_i,j∈[k] x_u,ix_v,j).
  
  We will show that  is a feasible solution to the level-D Symmetric Path Statistics SDP with the input , at some tolerance δ' = cδ—thus by Theorem 8.7, when (dλ)^2 > 4(d-1) and δ is sufficiently small, we will have a contradiction. We observe first that X is PSD with ones on the diagonal—these facts follow immediately from the hard constraints in Definition 8.17, which tell us that x_u,i^2 =  x_u,i for every u and i, and ∑_i ∈ [k] x_u,i = 1 for every u. 
  
  We turn now to the moment constraints, with the goal of showing
  
      ⟨, s⟩   = q_s(dλ)n ±δ' n       ∀ s ∈ [D] 
      ⟨, ⟩   = 0 ±δ' n^2.
  
  Rehashing our calculations from the proof of Lemma <ref>, we find that w.h.p.
  
      ⟨, s⟩   = ⟨, s⟩ + o(n) 
         = k/k-1(∑_i p_(P_s,{0,s},{i,i})(x,) - 1/k∑_i,jp_(P_s,{0,s},{i,j})(x,)) + o(n) 
         = 1/k-1⟨ q_s(dM), 𝕀 - /k ⟩ n ±k/k-1· 2kδ n + o(n) 
         = q_s(dλ)n ±k^3/k-1δ n + o(n).
  
  
  To verify that X has the correct inner product against the all-ones matrix, consider two partially labelled subgraphs: a single vertex labelled i ∈ [k], and two disjoint vertices both labelled i ∈ [k]. The sum of their corresponding polynomials is ∑_u,v x_u,ix_v,i, and identically in the planted model
  
      ∑_u,v_u,i_v,i = (n/k)^2.
  
  Our pseudoexpectation is required to match this up to an additive δ(n + n^2), the n and n^2 terms respectively coming from the additive slack in the one vs. two vertex graphs. Thus
  
      ⟨, ⟩ = k/k-1(n^2/k ±δ(n^2 + n) - n^2/k) = 0 ±2k/k-1δ n^2.
  
  
  
  
   §.§ Proof of Theorem <ref>: Lower Bound
  
  
  Assume that (dλ)^2 ≤ 4(d-1); we need to explicitly construct a degree-(2,D) pseudoexpectation that is with high probability feasible for ∼. Our tactic will be to show that such an operator can be constructed from a feasible solution to the Symmetric Path Statistics SDP guaranteed us by Theorem 8.7. 
  
  Before building the degree-(2,D) pseudoexpectation asserted to exist in the theorem statement, we will first prove a series of structural lemmas showing that it suffices to check only a subset of the moment constraints of a Local Statistics pseudoexpectation. 
  
  First, we show that the moment constraints regarding the pseudo-expected counts of partially labelled graphs containing cycles are satisfied more or less for free.
  
  
      
      Let ∼, and = () be a degree (D_x,D_G) pseudoexpectation, perhaps dependent on , that satisfies positivity and the hard constraints. For every error tolerance δ, w.h.p.  satisfies the moment constraints for all partially labelled subgraphs containing a cycle.
  
  
  
      It is a routine sum-of-squares calculation that for any monomial μ(x),
      
      (μ(x))^2 ≤μ(x)^2 = μ(x),
  
      meaning that |μ(x)| ≤ 1. Thus for any (H,S,τ),
      
      | p_(H,S,τ)(x,)| = | ∑_ϕ: V(H)  [n]∏_(α,β) ∈ E(H)_ϕ(α),ϕ(β)∏_α∈ S x_ϕ(α),τ(α)| ≤|∑_ϕ : V(H)∏_(α,β) ∈ E(H)_ϕ(α),ϕ(β)|,
  
      and the right hand side is simply the number of occurrences of the unlabelled graph H in . From Proposition 8.15, if H has (H) connected components and at least one cycle, (i) w.h.p. this quantity is smaller than δ' n^(H) for every δ' > 0, and (ii) χ(H) < (H). Thus trivially, if we set δ' < δ, w.h.p.
      
      | p_(H,S,τ)(x,) - (dM)_τ^(H,S)| ≤δ' n^(H) + (dM)_τ^(H,S)n^χ(H)≤δ n^(H).
  
  
  
  It therefore suffices to check only the moment constraints for partially labelled forests. In fact, only a subset of these are important.
  
  
      
      Let (H,S,τ) be a partialy labelled tree. The pruning of (H,S,τ) is the unique partially labelled subtree in which every leaf belongs to S. The pruning of an unlabelled graph is the empty graph, and the pruning of a forest is defined tree-by-tree. We say that a partially labelled forest is pruned if it is equal to its pruning.
  
  
  
      
      Let (H,S,τ) be a partially labelled forest with maximal degree d, (H,S,τ) its pruning, and write  and  for the vertex degrees in H and H respectively. If X is a symmetric nonnegative integer matrix with row and column sums equal to d, then
      
      X^(H,S)_τ/X^(H,S)_τ = ∏_v ∈ V(H)∏_q = (v)^(v)-1 (d - q).
  
  
  
  
      Let's reason combinatorially. Any such matrix X can be thought of as the adjacency matrix for a d-regular multigraph with self-loops; let's fix X and call this graph Γ. Since Γ's vertex set is [k], we will think of it as a fully labelled graph. By multiplicativity on disjoint unions, we may freely assume that (H,S,τ) is a tree. Let's choose a root r ∈ V(H) ⊂ V(H); having done so, E(H) is in bijection with V(H) ∖ r (and similarly for E(H) and V(H)). Let's write p(v) for the unique parent of every vertex. We can thus write
      
      X_τ^(H,S) = ∑_τ:τ|_S = τ   ∏_j ∈ [k] X_τ(r),j(X_τ(r),j - 1) ⋯ (X_τ(r),j - _j(r) + 1) 
             ×∏_v ∈ V(H) ∖ r∏_j ∈ [k] X_τ(v),j⋯ (X_τ(v),j - _j(v) + 1)/X_τ(v),τ(p(v)).
  
      Thinking of each τ as a map V(H) → V(Γ), the summand above gives the number of ways to map η: E(H) → E(Γ) with the following constraints: (1) each edge (u,v) must be mapped to one of the X_τ(u),τ(v) edges between τ(u) and τ(v), and (2) no two edges in E(H) with the same endpoint may be mapped to the same edge in Γ. We'll call the pair (τ, η) a locally injective occurrence of (H,S,τ) in the fully labelled graph Γ. Thus the expression X_τ^(H,S) gives the number of such occurrences.
      
      The same argument applies to the pruning (H,S,τ). Now, the graph (H,S,τ) consists pruning (H,S,τ), plus some trees hanging off the edges. For each locally injective occurrence of (H,S,τ), there are
      
      ∏_v ∈ V(H)∏_q = (v)^(v) - 1(d - q)
  
      ways to extend it to a locally injective occurrence of (H,S,τ), since Γ is d-regular.
  
  
  
      
      Let ∼, (H,S,τ) be a partially labelled forest, and (H,S,τ) its pruning. Then w.h.p.
      
      p_(H,S,τ)(x,) - n^(H) - (H)(dM)^(H,S)_τ/(dM)^(H,S)_τ p_(H,S,τ)(x,)_1 = o(n^(H)),
  
      where ·_1 is the coefficient-wise L^1 norm.
  
  
  
      Let (H,S,τ) be a partially labelled forest, (H,S,τ) its pruning. If ϕ: V(H)  V() is an occurrence of (H,S,τ), then we call ϕ : V(H)  V() an extension of ϕ if its an occurrence of (H,S,τ) and agrees with ϕ on V(H). Let's write Φ for the set of occurrences of (H,S,τ) in (,σ), and for each ϕ∈Φ, write Ξ(ϕ) for its set of extensions. Thus, incorporating Lemma 8.20,
      
      p_(H,S,τ)(x,) - n^(H) - (H)(dM)^(H,S)_τ/(dM)^(H,S)_τ p_(H,S,τ)(x,)_1 
                 ≤∑_ϕ∈Φ| |Ξ(ϕ)| - n^(H) - (H)∏_v ∈ V(H)∏_q = (v)^(v) - 1(d - q)|.
  
      
      By Proposition 8.15, with high probability there are o(n^(H) occurrences of H whose  |E(H)| neighborhoods in  either intersect or contain a cycle, so we can safely restrict the right hand side above to the remaining ones. Let's fix such an occurrence and enumerate the possible extensions. First, for each connected component J of H, and its corresponding component J of H, because  is d-regular and locally treelike in the neighborhood of ϕ(J), there are exactly
      
      ∏_v ∈ V(J)∏_q = (v)^(v) - 1 (d-q)
  
      ways to extend ϕ to the remainder of J. Having already chosen how to extend the occurrence on these connected components, call K the union of all connected components in H that have no distinguished vertex. We need to find an injective homomorphism from K into  that does not collide with ϕ(H) or the portion of the extension that we have already constructed. Since |V(H)| = O(1), there are
      
      n^(H) - (H)∏_v ∈ V(K)∏_q = 0^(v) - 1(d-q) + O(n^(H) - (H) - 1)
  
      ways to do this. Since |Φ| = O(n^(H)), 
      
      ∑_ϕ∈Φ| |Ξ(ϕ)| - n^(H) - (H)∏_v ∈ V(H)∏_q = (v)^(v) - 1(d - q)| = O(n^(H)) · O(n^(H) - (H) - 1) = O(n^(H) - 1)
  
      as desired.
  
  
  
      
      Let ∼ and = () be a degree-(D_x, D_G) pseudoexpectation, perhaps dependent on . If  w.h.p. satisfies the moment constraints for pruned partially labelled forests, w.h.p. it does so for every partially labelled forest.
  
  
  
      This is a direct consequence of Lemma 8.21. Retaining (H,S,τ) and (H,S,τ) from the proof of that lemma, since the pseudoexpectation of any monomial has absolute value at most one,
      
      p_(H,S,τ)(x,) = (dM)_τ^(H,S)/(dM)_τ^(H,S) p_(H,S,τ)(x,) ± o(n^ℓ) = (dM)_τ^(H,S)±δ n^ℓ
  
      for every δ > 0. We can take a union bound over all finitely many (H,S,τ).
  
  
  We are finally ready to describe our own degree (2,D) pseudoexpectation. Our key building block will be the feasible solution ≽ 0 to the degree-D Symmetric Path Statistics on input ∼ SDP whose asymptotic almost sure existence is guaranteed us by Theorem 8.7. Recall that this matrix satisfies
  
      
    * _u,u = 1 for every u ∈ [n]
      
    * ⟨, ⟩ = 0
      
    * ⟨, s⟩ = q_s(dλ) ±δ n for every s = 1,...,D.
  
  A degree-2 pseudoexpectation : [x]_≤ 2→ may be expressed as a (1 + nk)×(1 + nk) block matrix
  
      [   1 l^⊤;   l   Q ] = [     1 l^⊤_1     ⋯ l^⊤_n;   l_1 Q_1,1     ⋯ Q_1,n;     ⋮     ⋮     ⋱     ⋮;   l_n Q_n,1     ⋯ Q_n,n ]
  
  where (l_u)_i =  x_u,i and (Q_u,v)_i,j =  x_u,ix_v,j. Our construction will set (l_u)_i = 1/k for every u and i, and
  
      Q = 1/k(_nk/k + ⊗ (𝕀 - _k/k) )
  
  
  Let us first check the hard consstraints. For positivity it suffices to observe that
  
      Q - ll^⊤ = 1/k⊗ (𝕀 - _k/k) ≽ 0,
  
  as ,(𝕀 - _k/k) ≽ 0. We also have
  
      x_u,i^2 = (Q_u,u)_i,i = 1/k(1/k + (1 - 1/k)_i,i) = 1/k =  x_u,i
  
  since _u,u = 1 for every u∈ [n]. It remains only to check that (x_u,1 + ⋯ + x_u,k)p(x) =  p(x) for every p(x) of degree one. For this it is sufficient to verify that
  
      (x_u,1 + ⋯ + x_u,k)x_v,j = ∑_i (Q_u,v)_i,j = 1/k∑_i (1/k + _u,v(1 - _k/k)_i,j) = 1/k =  x_v,j.
  
  
  Finally, we need to verify the moment constraints. By Lemmas 8.21-22, if we do so only on the minimal partially labelled forests with at most two distinguished vertices, then w.h.p. the remainder of the moment constraints are satisfied. A minimal partially labelled forest with one distinguished vertex is just a single vertex with a label i ∈ [k]; the associated polynomial in this case is just x_1,k + ⋯ + x_n,k, and its required pseudoexpectation is n/k ±δ n, since there are identically n/k vertices with each label in the planted model. Our pseudoexpectation assigns a value of
  
      ∑_ux_u,i = ∑_u (l_u)_i = n/k
  
  as desired. 
  
  A minimal partially labelled forest on two vertices is either a path of length s ∈ [d] with endpoints labelled i,j ∈ [k], or two isolated vertices labelled i,j ∈ [k]. In the former case, the pseudoexpectation is required to read 1kq(dM)_i,jn ±δ n Recycling some calculations from Section 8.4, our pseudoexpectation on this polynomial reads
  
      ⟨ Q_i,j, s⟩   = ⟨ Q_i,j,s⟩± o(n) 
         = 1/k(⟨_n/k, s⟩ + ⟨, s⟩ (𝕀 - _k/k)_i,j) 
         = 1/k(q_s(d)(/k)_i,j + q_s(dλ)(𝕀 - _k/k)_i,j)n ± (δ/k)n  
         = 1/kq_s(dM)_i,j± (δ/k)n.
  
  The last line follows since dM = d_k/k + dλ (𝕀 - _k/k) is the spectral decomposition of dM. 
  
  Finally, we verify the case of two disjoint vertices labelled i,j∈[k]. The polynomial here is ∑_u≠ v x_u,ix_v,j, and the pseudoexpectation is requried to give a value of (n/k)^2 ±δ n^2. As needed, our pseudoexpectation gives
  
      ⟨ Q_i,j,_n ⟩ = 1/k(⟨_n/k, _n⟩ + ⟨,_n⟩(𝕀 - _k/k)_i,j) = (n/k)^2,
  
  as ⟨,_n⟩ = 0.
  
  
  
  
  
  
  
  
  
  
  
  § LOW-DEGREE ANALYSIS OF SPIKED MODELS
  
  
  
  In this section, we develop machinery for low-degree analysis of general spiked Wigner and Wishart models, culminating in the proofs of Theorems <ref> and <ref>.
  
  
  
   §.§ Preliminaries
  
  
  
      A random vector  is ε-local c-subgaussian if for any fixed vector v with v≤ε,
      
      exp(⟨ v,⟩) ≤exp(c/2v^2).
  
  
  
  It is straightforward to verify the following fact.
  
  
      Suppose  is ε-local c-subgaussian. For a (non-random) scalar α 0, α is ε/|α|-local c α^2-subgaussian. Also, the sum of n independent copies of  is ε-local cn-subgaussian.
  
  
  
      
      If a random vector  is ε-local c-subgaussian then it admits the following local Chernoff bound: for any v = 1 and 0 ≤ t ≤ε c,
      
      {⟨ v,⟩≥ t}≤exp(-t^2/2c).
  
  
  
  
      Apply the standard Chernoff bound argument: for any α > 0,
      
      {⟨ v,⟩≥ t}   = {exp(α⟨ v,⟩) ≥exp(α t)}
         ≤[exp(α⟨ v,⟩)] / exp(α t) 
         ≤exp(c α^2/2-α t)       provided α≤ε.
  
      Set α = t/c to complete the proof.
  
  
  
      
      If a random vector ∈^k is ε-local c-subgaussian then for any δ > 0 and any 0 ≤ t ≤ε c / (1-δ),
      
      {x≥ t }≤ C(δ,k) exp(-1/2c (1-δ)^2 t^2 )
  
      where C(δ,k) is a constant depending only on δ and k.
  
  
      Let 𝒩⊆^k be a δ-net of the unit sphere in ^k, in the sense that for any v ∈^k,
      
      max_u ∈𝒩 ⟨ u,v ⟩≥ (1-δ) v
  
      where u = 1 for all u ∈𝒩. Let C(δ,k) = |𝒩|. Using a union bound and the local Chernoff bound (Proposition <ref>), for all 0 ≤ t ≤ε c / (1-δ),
      
      {≥ t }≤{max_u ∈𝒩 ⟨ u,⟩≥ (1-δ) t }≤ C(δ,k) exp(-1/2c (1-δ)^2 t^2 ).
  
  
  
  
      
      Let δ > 0. If a random vector ∈^k is ε-local c-subgaussian with c < (1-δ)^2/2 then
      
      [≤ε c/(1-δ)exp(^2)] ≤ 1 + C(δ,k)/(1-δ)^2/(2c) - 1
  
      where C(δ,k) is a constant depending only on δ and k.
  
  
  
      Let Δ = ε c/(1-δ), and integrate the tail bound from Proposition <ref>:
      
      [≤Δexp(^2)]    = ∫_0^∞{≤Δexp(^2) ≥ t} dt 
         ≤ 1 + ∫_1^exp(Δ^2){exp(^2) ≥ t} dt 
         = 1 + ∫_1^exp(Δ^2){≥√(log t)} dt 
         ≤ 1 + C(δ,k) ∫_1^∞exp(-1/2c (1-δ)^2 log t ) dt 
         = 1 + C(δ,k)/(1-δ)^2/(2c) - 1.
  
  
  
  
  
   §.§ The Wigner Model
  
  
  
      We start with a formula for L^≤ D^2 from <cit.> (adapted slightly for the case of symmetric Gaussian noise):
      
      L^≤ D^2 = _,'exp^≤ D(λ^2 n/2⟨,' ⟩)
  
      where ' is an independent copy of  and exp^≤ D(x) = ∑_d=0^D x^d/d! denotes the Taylor series truncation of exp. Write L^≤ D^2 = L_1 + L_2 where L_1 is the small deviations term
      
      L_1 _,'⟨,' ⟩≤Δexp^≤ D(λ^2 n/2⟨,' ⟩),
  
      and L_2 is the large deviations term
      
      L_2 _,'⟨,' ⟩ > Δexp^≤ D(λ^2 n/2⟨,' ⟩),
  
      where Δ > 0 is a small constant to be chosen later. Lemmas <ref> and <ref>, proved in the following two subsections, show that for some choice of Δ, L_1 and L_2 are both O(1), completing the proof.
  
  
  
  
    §.§.§ Small Deviations
  
  
  
      In the setting of Theorem <ref>, if |λ| < 1 then there exists Δ > 0 such that L_1 = O(1) for any D.
  
  
  
      Note that
      
      ⟨,' ⟩ = 1/n^2⟨^⊤, '(')^⊤⟩ = 1/n^2_^2
  
      where = ^⊤'. In particular, ⟨,' ⟩≥ 0. Since exp^≤ D(x) ≤exp(x) for all x ≥ 0,
      
      L_1 ≤ _^2 ≤Δ n^2exp(λ^2/2n_^2 ).
  
      We have = ∑_i=1^n _i where the _i are independent k × k matrices, each distributed as (')^⊤. Since  has bounded support, the moment-generating function M(T) = exp(⟨ T, _i ⟩) exists in a neighborhood of T = 0 (in fact, it exists everywhere) and thus, by the defining property of the MGF, has gradient ∇ M(0) = [_i] = 0 and Hessian (Hess  M)(0) = (_i) = ()^⊗ 2≼𝕀_k^2. Thus for any η > 0 there exists ε > 0 such that
      
      M(T) ≤exp(1/2 (1+η) T_^2)     for all T_≤ε.
  
      In other words, _i is ε-local (1+η)-subgaussian. From Fact <ref>, this implies  is ε-local (1+η)n-subgaussian, and λ/√(2n) is ε√(2n)/λ-local (1+η)λ^2/2-subgaussian. Since λ^2 < 1, we can choose δ > 0 and η > 0 such that (1+η)λ^2 < (1-δ)^2. Letting Δ = (ε (1+η) / (1-δ))^2 and using Proposition <ref>,
      
      L_1 ≤ λ/√(2n)_≤λ√(Δ n/2)exp(λ/√(2n)_^2 ) = O(1).
  
  
  
  
  
  
    §.§.§ Large Deviations
  
  
  
      In the setting of Theorem <ref>, for any constants λ∈ and Δ > 0, and for any D = o(n/log n), we have L_2 = o(1).
  
  
  
      Recall from above that  is ε-local (1+η)n-subgaussian. By Proposition <ref> (taking t to be n times a small constant),
      
      {⟨,' ⟩ > Δ}≤{_ > √(Δ) n } = exp(-Ω(n)).
  
      The boundedness of  guarantees |⟨,' ⟩| ≤ n^C for some constant C > 0, and so
      
      L_2 ≤exp(-Ω(n)) ∑_d=0^D (λ^2 n/2 n^C)^d ≤exp(-Ω(n)) (D+1) n^O(D),
  
      which is o(1) provided D = o(n / log n).
  
  
  
  
   §.§ The Wishart Model
  
  
  
      In Appendix <ref> we derive a formula for L^≤ D^2 in the general spiked Wishart model. The version we will need here is summarized in Proposition <ref>. The formula takes the form
      
      L^≤ D^2 = _,'∑_d=0^D r_d(β,β')
  
      for some polynomials r_d. As in the Wigner case, we write L^≤ D^2 = L_1 + L_2 where
      
      L_1 _,'⟨,' ⟩≤Δ∑_d=0^D r_d(β,β')
  
      and
      
      L_2 _,'⟨,' ⟩ > Δ∑_d=0^D r_d(β,β')
  
      for a small constant Δ > 0 to be chosen later. Lemmas <ref> and <ref>, proved in the following two subsections, show that for some choice of Δ, L_1 and L_2 are both O(1), completing the proof.
  
  
  
  
    §.§.§ Small Deviations
  
  
  Before bounding the small deviations term in Lemma <ref>, we state two deterministic facts that will be useful in the proof.
  
  
      
      For n × m matrices A and B,
      
      (𝕀_n - AA^⊤ BB^⊤) = (𝕀_m - A^⊤ B B^⊤ A).
  
      
  
      If A,B are square and A is nonsingular, this can be shown by taking determinants on both sides of the equation (I - AA^⊤ BB^⊤)A = A(I - A^⊤ BB^⊤ A). For the general case, pad A,B with zeros to make them square, and consider a sequence of nonsingular matrices converging to A.
  
  
  
  
      
      For any η > 0 there exists ε > 0 such that for all 0 ≤ t ≤ε, we have (1-t)^-1≤exp((1+η)t).
      
  
      Letting f(t) = (1-t)^-1 and g(t) = exp((1+η)t), we have f(0) = g(0) = 1 and f'(0) = 1 < 1+η = g'(0).
  
  
  We are now ready to bound the small deviations term.
  
  
      
      In the setting of Theorem <ref>, if β^2 < γ then there exists Δ > 0 such that L_1 = O(1) for any D.
  
  
  
      Since ≽ 0, we have from Proposition <ref>(c,d) that r_d(β,β') ≥ 0. Analogous to (<ref>), we have either ⟨,' ⟩ = 0 or ⟨,' ⟩ = 1/n^2_^2. 
      Recall from Definition <ref> that, when drawing from , we first draw ∼, and then threshold to form  as:
      
      =    if β≻ -𝕀_n, 
      
                  0    else.
  
      
      We can upper bound L_1 by dropping the low-degree truncation and using Proposition <ref>(b):
      
      L_1    ≤_,' ⟨,' ⟩≤Δ∑_d=0^∞ r_d(β,β') 
         = _,' ⟨,' ⟩≤Δ(𝕀_n - β^2 ')^-N/2
         ≤ 1 +  _^2 ≤Δ n^2(𝕀_n - β^2 ')^-N/2
  
      where the +1 in the last line covers the second case of (<ref>). 
      Let {_i} be the eigenvalues of ^⊤ (which are nonnegative). Let η > 0 (to be chosen later), take ε according to Lemma <ref>, and choose Δ≤ε/β^2. Note that _^2 = ∑_i _i. Provided _^2 ≤Δ n^2, we have _i ≤Δ n^2 for all i, i.e., β^2 n^-2_i ≤ε, and so
      
      (𝕀_n - β^2 ')^-N/2   = (𝕀_n - β^2 n^-2^⊤' '^⊤)^-N/2
         = (𝕀_n - β^2 n^-2^⊤' '^⊤)^-N/2using Proposition <ref>
         = (𝕀_n - β^2 n^-2^⊤)^-N/2
         = ∏_i (1 - β^2 n^-2_i)^-N/2
         ≤∏_i exp((1+η)β^2 n^-2_i)^N/2using Lemma <ref>
         = exp((1+η)β^2 N/2n^2∑_i _i ) 
         = exp((1+η)β^2 N/2n^2_^2 ).
  
      We now have
      
      L_1 ≤ 1 +  _^2 ≤Δ n^2exp((1+η)β^2 N/2n^2_^2 ).
  
      Comparing this to (<ref>), we see that we have reduced to the case of Wigner small deviations. In place of λ^2, we have (1+η) β^2 N/n→ (1+η) β^2/γ. Thus, provided β^2 < γ, we can choose η > 0 and Δ > 0 small enough so that L_1 = O(1).
  
  
  
  
    §.§.§ Large Deviations
  
  
  
      
      In the setting of Theorem <ref>, for any constants β > -1, γ > 0, and Δ > 0, and for any D = o(n/log n), we have L_2 = o(1).
  
  
  
      Consider the case β > 0 so that β≽ 0; the case β < 0 is handled similarly. We will use the formula for r_d given in Proposition <ref>(c): 
      
      r_d(β,β') = ∑_d_1, …, d_N ∈ 2
      ∑_i = 1^N d_i = d∏_i = 1^N 1/d_i!_∼( 0, β) 
      ' ∼( 0, β'), ' ^d_i.
  
      
      Let {_i,_i} be an eigendecomposition of , and let _i = _i _i _i^⊤ so that = _1 + ⋯ + _k. Let _i ∼𝒩(0,β_i) independently so that ∑_i=1^k _i ∼𝒩(0,β). Similarly define _i', _i', '. For fixed ,',{_i},{'_i},
      
      [⟨,' ⟩^d] 
              ≤^d '^d = ^d ·'^d.
  
      The boundedness of  guarantees ∑_i _i^2 = _^2 ≤ n^C for some constant C > 0. 
      Recall that _i ∼(0, β_i _i_i^⊤), so for  a standard Gaussian vector, _i has the same law as √(β_i)·⟨_i, ⟩_i.
      Since _i is a unit vector, _i then has the same law as √(β_i)· |⟨_i, ⟩|, which in turn has the same law as √(β_i)· |_1|.
      So, for d even, _i^d = (β_i)^d/2 (d-1)!! ≤β^d/2 n^Cd/4 d^d.
      This means
      
      ^d 
              ≤(∑_i=1^k _i)^d 
              ≤(k max_i _i)^d 
              ≤ k^d ∑_i=1^k _i^d 
              ≤ k^d+1β^d/2 n^Cd/4 d^d.
  
      Since ^d = 1 when d = 0, we can rewrite this as ^d ≤ k^2dβ^d/2 n^Cd/4 d^d ≤ (dn)^O(d). Thus for d_1,…,d_N ∈ 2ℕ with ∑_i d_i = d ≤ D,
      
      ∏_i=1^N [⟨,' ⟩^d_i] ≤∏_i=1^N (d_i n)^O(d_i)≤ (Dn)^O(D).
  
      
      Now we have
      
      r_d(,') ≤ N^D (Dn)^O(D)
  
      and so
      
      L_2 ≤{⟨,' ⟩ > Δ}∑_d=0^D N^D (Dn)^O(D).
  
      Similarly to (<ref>) we have {⟨,' ⟩ > Δ}≤exp(-Ω(n)) and so L_2 = o(1) provided D = o(n/log n).
  
  
  
  
  
  
  
  
  
  
  
  
  alpha
  
  
  
  
  
  
  
  
  § LOW-DEGREE ANALYSIS OF GENERAL WISHART MODELS
  
  
  In this section we derive the formula (<ref>) for L^≤ D^2 in the general spiked Wishart model.
  
  
  
   §.§ Hermite Polynomial Facts
  
  
  We first define and give the key facts that we will use about the Hermite polynomials, the orthogonal polynomials with respect to the standard Gaussian measure.
  
  
      
      The univariate Hermite polynomials are the sequence of polynomials h_k(y) ∈[y] for k ∈, defined by the recursion
      
      h_0(y)    = 1, 
      
              h_k + 1(y)    = yh_k(y) -  h_k^'(y).
  
      The n-variate Hermite polynomials are the polynomials H_α(y) ∈[y_1, …, y_n] indexed by α∈^n and H_α(y) = ∏_i = 1^n h_α_i(y_i).
      Finally, the normalized n-variate Hermite polynomials are H_α(y) = (α!)^-1/2 H_α(y), where we abbreviate α! = ∏_i = 1^n α_i!.
  
  
  The main and defining property of the Hermite polynomials is their orthogonality, which we record below.
  
      For any α, β∈^n,
      
      _∼(0, I)[H_α() H_β()] = δ_αβ.
  
  
  
  
  Beyond this, the key additional tool for our analysis is a generalization of the following fact from the “umbral calculus” of Hermite polynomials (a proof will be subsumed in our more general result below).
  
  
      Let x > -1.
      Then,
      
      _∼(0, 1 + x)h_k() = 
               
                  (k-1)!! · x^k/2    k  even
      
                  0     k  odd
  
  
  Note that the formula on the right-hand side is that for the moments of a Gaussian random variable with variance x, but we extend it to apply even for negative x, which is the “umbral”  case of the result, admitting an interpretation in terms of a fictitious Gaussian of negative variance—even if x ∈ (-1, 0), the right-hand side may be viewed formally as the value of  “_∼(0, x)^k.” 
  A thorough exposition of such analogies arising in combinatorics and the theory of orthogonal polynomials is given in <cit.>.
  
  In fact, the same holds even for multivariate Gaussians.
  The correct result in this case is given by imitating the formula for the moments of a multivariate Gaussian, via Wick's (or Isserlis') formula.
  While Proposition <ref> is well-known in the literature on Hermite polynomials and the umbral calculus, we are not aware of previous appearances of the formula below.
  
      
       Let X ∈^n × n_ with X ≻ -𝕀_n.
       For α∈^n viewed as a multiset of elements of [n], let 𝒫(α) be the set of pairings of elements of α, and for each P ∈𝒫(α) write X^P denote the product of the entries of X located at paired indices from P.
       Then,
       
      _∼( 0, I + X) H_α() = ∑_P ∈𝒫(α) X^P.
  
   
   Note that if X ≽ 0, then the right-hand side equals _∼( 0, X) x^α by Wick's formula, but we again have an umbral extension to non-PSD matrices X.
   
       Define
       
      ℓ_α_∼(0, I + X) H_α().
  
       Let e_i ∈^n have ith coordinate equal to 1 and all other coordinates equal to zero, and write 0 ∈^n for the vector with all coordinates equal to zero.
       Clearly ℓ_0 = 1 and ℓ_e_i = 0 for any i ∈ [n].
       We then proceed by induction and use Gaussian integration by parts:
       
      ℓ_α + e_i   = _∼(0, I + X)h_α_i + 1(_i)∏_j ∈ [n] ∖{i} h_α_j(_j) 
         = _∼(0, I + X)(_i h_α_i(_i) - h_α_i^'(_i))∏_j ∈ [n] ∖{i}  h_α_j(_j) Definition <ref>
         = _∼(0, I + X)[∑_k = 1^n(I + X)_ik∏_j ∈ [n] h_α_j^(δ_jk)(_j) - ∏_j ∈ [n] h_α_j^(δ_ij)(_j)] integration by parts
         = ∑_k ∈ [n] 
      α_k > 0X_ik_∼(0, I + X)∏_j ∈ [n] h_α_j^(δ_jk)(_j) 
         = ∑_k ∈ [n] 
      α_k > 0α_k X_ik_∼(0, I + X)∏_j ∈ [n] h_α_j - δ_jk(_j) 
         = ∑_k ∈ [n] 
      α_k > 0α_k X_ikℓ_α - e_kinductive hypothesis
  
       so ℓ_α satisfy the same recursion and initial condition as the sum-of-products formula on the right-hand side of (<ref>).
   
  
  
  
   §.§ Components of the LDLR
  
  
  Let ,  be as in the general spiked Wishart model (Definition <ref>), and let L be the associated likelihood ratio. Throughout this section, we assume without loss of generality that (i) β = 1 (since β can be absorbed into X), and (ii) the prior  is supported on X for which X ≻ -𝕀_n. For α∈ (^n)^N, we denote
  
      m_α   _∼ H_α()L(), 
      m_α   _∼H_α()L() = 1/√(α!)m_α.
  
  
  We may compute these numbers as follows.
  For any α∈ (^n)^N, we have, passing to an expectation under  rather than  and then using Proposition <ref>,
  
      m_α   = _∼ H_α() 
         = _∼∏_i = 1^N _∼(0, I + ) H_α_i(y) 
         = _∼∏_i = 1^N(∑_P ∈(α_i)^P).
  
  
  
  
   §.§ Taylor Expansion of the LDLR
  
  
  
      Suppose  is as in Definition <ref>. 
      Denote by 𝒯^≤ D the operation of truncating the Taylor series of a function that is real-analytic in a neighborhood of zero to degree-D polynomials.
      For the sake of clarity, this will only ever apply to the variable named t.
      Then,
      
      L^≤ D^2 = _, ^'∼𝒯^≤ D[(𝕀_n - t^2^')^-N / 2](1),
  
      by which we mean evaluation of the function of t on the RHS at t=1.
  
  
      We have
      
      L^≤ D^2 
                 = ∑_|α| ≤ Dm_α^2 
         = _, ^'∼∑_|α| ≤ D∏_i = 1^N1/α_i!(∑_P ∈𝒫(α_i)^P)(∑_P ∈𝒫(α_i) (^')^P) 
         = _, ^'∼∑_d = 0^D ∑_|α| = d∏_i = 1^N1/α_i!(∑_P ∈𝒫(α_i)^P)(∑_P ∈𝒫(α_i) (^')^P).
  
      On the other hand, we may expand the right-hand side of (<ref>) by repeatedly differentiating with respect to t to extract Taylor coefficients.
      In doing so we will repeatedly apply the chain rule, and since d/dt(I - tA) = (A) each derivative will be a rational function in (t, X, X^'). Therefore, the Taylor coefficients are some rational functions r_d(X, X^') (depending on N) for d ∈, and for these coefficients
      
      _, ^'∼𝒯^≤ D[(𝕀_n - t^2^')^-N / 2](1) = _, ^'∼∑_d = 0^D r_d(, ^').
  
      We will show that in fact termwise equality holds, inside the expectations, namely
      
      r_d(X, X^') = ∑_|α| = d∏_i = 1^N1/α_i!(∑_P ∈𝒫(α_i) X^P)(∑_P ∈𝒫(α_i) (X^')^P)  r_d^'(X, X^')
  
      for each d ∈ and for all (deterministic) X, X^'∈^n × n_.
      Since either side of (<ref>) is a rational function of (X, X^'), it suffices to show that this is true on a set of matrices of positive measure.
      We will show that it holds for all X, X^'≽ 0.
  
      In this case, we have the convenient Gaussian interpretation of the expression for r_d^'(X, X^') from Wick's formula:
      
      r_d^'(X, X^') 
                 = ∑_|α| = d∏_i = 1^N1/α_i!(_∼( 0, X)^α_i)(_∼( 0, X^')^α_i) 
         = __1, …, _N ∼( 0, X) 
      _1^', …, _N^'∼( 0, X^')∑_|α_i|  even
       |α| = d∏_i = 1^N1/α_i!
              (_i)^α_i(_i^')^α_iand grouping by the values of |α_i|,   = __1, …, _N ∼( 0, X) 
      _1^', …, _N^'∼( 0, X^')∑_d_1, …, d_N ∈ 2
      ∑_i = 1^N d_i = d1/∏_i = 1^N d_i!∑_α_1, …, α_N ∈^n 
       |α_i| = d_i∏_i = 1^N d_iα_i∏_j = 1^n ((_i)_j(_i^')_j)^α_i(j)
         = __1, …, _N ∼( 0, X) 
      _1^', …, _N^'∼( 0, X^')∑_d_1, …, d_N ∈ 2
      ∑_i = 1^N d_i = d∏_i = 1^N _i, _i^'^d_i/d_i!
         = ∑_d_1, …, d_N ∈ 2
      ∑_i = 1^N d_i = d∏_i = 1^N 1/d_i!_∼( 0, X) 
      ^'∼( 0, X^'), ^'^d_i.
  
      From here, we introduce the moment-generating function of the inner overlap variables.
      Define
      
      ϕ_X, X^'(t) 
              _∼( 0, X) 
      ^'∼( 0, X^')exp(t, ^') = ∑_d = 0^∞t^d/d!_∼( 0, X) 
      ^'∼( 0, X^'), ^'^d.
  
      Then, r^'_d(X, X^') is simply the coefficient of t^d in the Taylor series of ϕ_X, X^'(t)^N.
      
      On the other hand, we may actually compute ϕ_X,X^'(t):
      
      ϕ_X,X^'(t)
                 = _, ∼( 0,  𝕀_n)exp(t^⊤√(X)√(X^')) 
         = _∼( 0,  𝕀_2n)exp(^⊤[[             0 t/2√(X)√(X^'); t/2√(X^')√(X)             0 ]] ) which may be calculated as a moment generating function of the “matrix χ^2” variable gg^⊤, giving   = ([[            𝕀_n -t√(X^')√(X^');   -t√(X^')√(X)            𝕀_n ]])^-1/2
         = ( 𝕀_n - t^2√(X)X^'√(X))^-1/2and applying Proposition <ref>,   = ( 𝕀_n - t^2XX^')^-1/2.
  
      Thus r^'_d(X, X^') is also the coefficient of t^d in the Taylor series of (𝕀_n - t^2XX^')^-N/2, whereby r^'_d(X, X^') = r_d(X, X^'), completing the proof.
  
  
  Implicit in the above proof are the following facts which we have made use of in Section <ref>.
  
  
      Consider the general spiked Wishart model (Definition <ref>), and assume (without loss of generality) that β = 1 and  is supported on X for which X ≻ -𝕀_n. The following formulas hold:
      
          
    (a) L^≤ D^2 = _,^'∼∑_d=0^D r_d(,^') for some polynomials r_0,…, r_d, …, 
          
    (b) ∑_d=0^∞ r_d(X,X^') = (𝕀_n - X X^')^-N/2,
          
    (c) if X ≽ 0 and X^'≽ 0 then r_d(X,X^') = ∑_d_1, …, d_N ∈ 2
  ∑_i = 1^N d_i = d∏_i = 1^N 1/d_i!_∼( 0, X) 
  ^'∼( 0, X^'), ^'^d_i, and
          
    (d) if X ≼ 0 and X^'≼ 0 then r_d(X,X^') = ∑_d_1, …, d_N ∈ 2
  ∑_i = 1^N d_i = d∏_i = 1^N 1/d_i!_∼( 0, -X) 
  ^'∼( 0, -X^'), ^'^d_i.
      
  
  
  
  
  
  § EXPONENTIAL LOW-DEGREE HARDNESS FOR SBM
  
  
  
  The goal of this section is to prove Theorem <ref>. We first prove a general statement that reduces binary-valued models to the analogous Gaussian model.
  
  
  
   §.§ Comparing Binary-Valued Models to Gaussian
  
  
  
      
      Consider the following general binary-valued problem.
      
          
    * Under the null distribution , we observe ∈^N where _i are independent, satisfy [_i] = 0 and [_i^2] = 1, and each take two possible values: _i ∈{a_i,b_i} with a_i < b_i.
          
    * Under the planted distribution , a signal ∈^N is drawn from some prior, and then _i ∈{a_i,b_i} are drawn independently (conditioned on ) such that [_i | _i] = _i. (This requires _i ∈ [a_i,b_i].)
          
      In the above setting,
      
      L^≤ D^2 ≤∑_d=0^D 1/d!_,'⟨,' ⟩^d
  
      where ' denotes an independent copy of .
  
  
  The significance of (<ref>) is that the right-hand side is the exact formula for L^≤ D^2 in the following additive Gaussian model (see <cit.>): under , ∼𝒩(0,𝕀_N); and under , =  + with ∼𝒩(0,𝕀_N) and  drawn from some prior. Thus, Proposition <ref> can be interpreted as saying that a binary-valued problem is at least as hard as the corresponding Gaussian problem.
  
  
      The Fourier characters χ_S(Y) = ∏_i ∈ S Y_i for S ⊆ [N] with |S| ≤ D are orthonormal with respect to , in the sense that _∼ [χ_S() χ_T()] = S = T. They also span the subspace of degree ≤ D polynomials, since for any r ∈, any Y_i^r can be written as a degree-1 polynomial in Y_i. Thus, {χ_S}_|S| ≤ D is an orthonormal basis for the degree ≤ D polynomials. It is a standard fact that this allows us to write L^≤ D^2 = ∑_|S| ≤ D(_∼[χ_S()])^2 (see e.g., <cit.>). We will use S to denote a subset of [N] and use α to denote an ordered multi-set of [N], with χ_α(Y) ∏_i ∈α Y_i. Now compute
      
      L^≤ D^2    = ∑_|S| ≤ D (_∼χ_S())^2 
         = ∑_|S| ≤ D (_χ_S())^2 
         (∗)≤∑_d=0^D ∑_|α| = d1/d! (_χ_α())^2     see below
         = ∑_d = 0^D ∑_|α| = d1/d!_,'χ_α() χ_α(') 
         = ∑_d = 0^D 1/d!_,'⟨,' ⟩^d.
  
      To see that inequality (∗) holds, note that it would be an equality if restricted to ordered multi-sets α that contain distinct elements.
  
  
  
  
  
  
   §.§ Stochastic Block Model
  
  
  We now specialize to the case of the stochastic block model (Definition <ref>), and use Proposition <ref> to reduce to a certain spiked Wigner model.
  
  
      It will be convenient to consider a modification of the SBM that allows self-loops. Specifically, the edge (i,i) occurs with probability d/n under  and with probability (1+η/√(2)(k-1))d/n under . It is clear from the variational formula (<ref>) for L^≤ D that revealing this extra information can only increase L^≤ D.
      
      In order to place the SBM in the setting of Proposition <ref>, take N = n(n+1)/2 with a variable _i,j for every i ≤ j. Let p = d/n. In order to ensure _[_i,j] = 0 and _[_i,j^2] = 1, take _i,j = b √((1-p)/p) if edge (i,j) is present, and _i,j = a  -√(p/(1-p)) otherwise.
      
      We now define  appropriately. Conditioned on the community structure, edge (i,j) occurs with probability (1+_i,j)p where _i,i = η(k-1)/√(2) and _i,j (for i < j) is either η(k-1) or -η depending on whether i and j belong to the same community or not, respectively. Using the fact pb + (1-p)a = 0 (twice), this means we should take
      
      _i,j = [_i,j | _i,j] = (1+_i,j)pb + [1-(1+_i,j)p]a = _i,j p (b-a) = -_i,j a = _i,j√(p/1-p).
  
      Let  be the n × k matrix whose ith row is √(k) e__i - /√(k) where _i ∈ [k] is the community assignment of vertex i. One can check that (^⊤)_i,j = k _i = _j - 1 and so _i,j = η√(p/1-p) (^⊤)_ij for i < j, and _i,i = η/√(2)√(p/1-p) (^⊤)_i,i. Therefore ⟨,' ⟩ = η^2/2p/1-p⟨^⊤, '(')^⊤⟩. By Proposition <ref>,
      
      L^≤ D^2 ≤∑_d=0^D 1/d!(η^2/2p/1-p⟨^⊤, '(')^⊤⟩)^d.
  
      Comparing this to (<ref>) reveals that this is precisely the expression for L^≤ D^2 in the general spiked Wigner model with spike prior _k (see Definition <ref>), except in place of λ^2 we have η^2 d/1-p = (1+o(1))η^2 d. Therefore, appealing to the Wigner result (Theorem <ref>), we have L^≤ D = O(1) provided d η^2 < 1.
  
  
  
  
  
  
  