SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four

Introduction

Let $G(n,p)$ be the Erdős-Rényi random graph where each edge is present in $G$ with probability $p$ independently of others. It is an easy calculation that the largest clique in $G\sim G(n,\frac{1}{2})$ is of size $(2+o(1))\cdot\log{(n)}$ with high probability. Recovering such a clique using an efficient algorithm has been a long standing open question in theoretical computer science. As early as 1976, Karp [Kar76] suggested the impossibility of finding cliques of size even $(1+\varepsilon)\log{(n)}$ for any constant $\varepsilon>0$ in polynomial time. Karp’s conjecture was remarkably prescient and has stood ground after nearly $4$ decades of research.

Lack of algorithmic progress on the question motivated Jerrum [Jer92] and Kucera [Kuc95] to consider a relaxed version known as the planted clique problem. In this setting, we are given a graph $G$ obtained by planting a clique of size $\omega$ on a graph sampled according to $G(n,\frac{1}{2})$. Information theoretically, the added clique is identifiable as long a $\omega\gg\log{(n)}$. The goal is to recover the added clique via an efficient algorithm for as small an $\omega$ as possible. This variant is also connected to the question of finding large communities in social networks and the problem of signal finding in molecular biology [PS000]. Despite attracting a lot of attention, the best known polynomial time algorithm can only find planted cliques when their size $\omega=\Omega(\sqrt{n})$ [AKS98, FK03]. The LS+ semi-definite programming hierarchy leads to the state of the art trade off: planted cliques of size $\omega\approx\sqrt{\frac{n}{2^{d}}}$ can be recovered in time $n^{O(d)}$ for any $d=O(\log{(n)}$.

Recently, this difficulty of finding cliques of size $\omega\ll\sqrt{n}$ has led to an increasing confidence in planted clique being a candidate for an average case hard problem and has inspired new research directions in cryptography [ABW10], property testing [AAK+07], machine learning [BR13], algorithmic game theory [DBL09, ABC11] and mathematical finance [DBL10].

In this paper we are interested in understanding the Sum of Squares (SoS, also known as Lasserre) semi-definite programming (SDP) hierachy [Las01, Par00] for the planted clique problem. This is a family of algorithms, paramterized by a number $d$ called the degree, where the $d^{th}$ algorithm takes $n^{O(d)}$ time to execute. The sum of squares hierarchy can be viewed as a common generalization and extension of both linear programming and spectral techniques, and as such has been remarkably successful in combinatorial optimization. In particular it captures the state of the art algorithms for problems such as Sparsest Cut [ARV04], MAX CUT [GW95], Unique Games/Small Set Expansion [ABS10, BRS11, GS12]. Recently, [BBH+12] showed that a polynomial time algorithm from this hierarchy solves all known integrality gap instances of the Unique Games problem, and similar results have been shown for the hard instances of MAX-CUT [DMN13] and Balanced Separator [OZ13]. Very recently, [LRS15] showed that the sum of squares algorithm is in fact optimal amongst all efficient algorithms based on semidefinite programming for a large class of problems that includes constraint satisfaction and the traveling salesman problem. Moreover, Barak, Kelner and Steurer [BKS14, BKS15] used the SoS hierarchy to give improved algorithms to average case problems such as the dictionary learning problem and the planted sparse vector problem that have at least some similarity to the planted clique problem.Thus several researchers have asked whether the SoS hierarchy can yield improved algorithms for this problem as well.

The first published work along these lines was of Meka, Potechin and Wigderson [MPW15] who showed that for every $d\geqslant 2$, the degree $2d$ SoS cannot find planted cliques of size smaller than $\approx n^{\frac{1}{2d}}$.We use $\approx$ to denote equality up to factors polylogarithmic in $n$ (the size of the graph) and with an arbitrary dependence on the degree parameter $d$. Deshpande and Montanari [DM15] independently proved a tighter lower bound of $\approx n^{1/3}$ for the case of degree $4$. In the main result of this paper, we extend the prior works and show that the first non trivial extension of the spectral algorithm, namely the SoS algorithm of degree $4$, cannot find cliques of size $\approx\sqrt{n}$, a bound optimal within $\operatorname{poly}\log{(n)}$ factors. Our lower bound for degree $4$ is obtained by a careful “correction” to the certificate used by [MPW15] and [DM15] in their lower bounds.

A similar result was obtained in an independent work by Raghavendra and Schramm [RS15]. In our second main result, we give a tight analysis of the certificate considered by [MPW15] and [DM15] and show that it yields a lower bound of $n^{\frac{1}{d+1}}$.

The certificate of [MPW15, DM15] is sufficient to show an $\Omega(\sqrt{n/2^{d}})$ lower bound for the degree $d$ $LS+$ hierarchy [FK03] (which is a weaker SDP that also runs in time $n^{O(d)}$). However, a generalization of an argument of Kelner (see Section 10) shows that this is not the case for the SoS hierarchy, and our analysis of this certificate is tight. Hence our work shows that to get stronger lower bounds for higher degree SOS it is necessary and sufficient to utilize more complicated constructions of certificates than those used for weaker hierarchies. Whether this additional complexity results in an asymptotically better tradeoff between the running time and clique size remains a tantalizing open question.

Technical Overview

The SoS semidefinite programming hierarchy yields a convex programming relaxation for the planted clique problem. That is, we derive from the input graph $G$ a convex program $\mathcal{P}_{G}$ such that if the graph had a clique of size $\omega$ then $\mathcal{P}_{G}$ is feasible. To show that the program fails to solve the planted clique problem with parameter $\omega$, we show that with high probability there is a solution (known as a certificate) for the program $\mathcal{P}_{G}$ even when $G$ is a random graph from $G(n,1/2)$ (which in particular will not have a clique of size $\gg\log n$).

It is known that such an approach cannot work to obtain a $\approx\sqrt{n}$ lower bound for the SoS program of degree $4$ and higher. That is, this natural certificate does not satisfy the conditions of the SoS program. Hence to obtain our lower bound for degree $4$ SoS we need to consider a more complicated certificate, that can be thought of as making a global “correction” to the simple certificate of [MPW15, DM15]. For higher degrees, we have not yet been able to analyze the corresponding complex certificate, but we are able to give a tight analysis of the simple certificate, showing that it certifies an $\omega\approx n^{1/(d+1)}$ lower bound on degree $2d$ SoS relaxation. The key technical difficulty in both our work and prior ones is analyzing the spectrum of random matrices that have dependent entries. Deshpande and Montanari [DM15] achieved such an analysis by a tour-de-force of case analysis specifically tailored for the degree $4$ case. However, the complexity of this argument makes it unwieldy to extend to either the case of the more complex certificate or the case of analyzing the simple certificate at higher degrees. Thus, key to our analysis is a more principled representation-theoretic approach, inspired by Grigoriev [Gri01a], to analyzing the spectrum of these kind of matrices. We hope this approach would be of use in further results for both the planted clique and other problems.

We now give an informal overview of the SoS program for planted clique, the [MPW15, DM15] certificate, our correction to it, and our analysis. See Section 3 and [BS14] for details.

2 The “Simple Moments”

The simplest form of such a pseudo-distribution is to set

3 There is such a thing as too simple

4 Fixing the simple moments

for every clique $S$. Note that when $\omega=\varepsilon\sqrt{n}$, the correction factor would typically be of the form $1\pm\Theta(\varepsilon)$.While it might seem that there is a chance for these pseudo-expectations to be negative, if $\omega<\sqrt{n}/\operatorname{polylog}(n)$ then it is exceedingly unlikely that there will exists an $S$ such that $|r_{S}|>n/\omega$, and so we ignore this issue in this overview.

If we now focus on the contribution of the $n^{4}$ terms where the $j_{k}$’s are all distinct, we see that each such set $S$ yields the term

5 Analyzing the corrected moments

The above gives some intuition why the corrected moments might be better than the simple moments for one set of polynomials. But a priori it is not at all clear that those polynomials encapsulated all the issues with the simple moments. Moreover, it is also unclear whether or not the correction itself could introduce additional issues, and create new types of negative eigenvectors. Ruling out these two possibilities is the crux of our analysis.

Because of the dependencies in the random matrix $\mathcal{M}$, the deviation from expectation varies according to the eigenspace. Thus, in [DM15], the deviation from the expectation is analyzed by first decomposing along the eigenspaces $V_{0},V_{1},V_{2}$.

A second technical idea is required to carry out this decomposition. Because of the symmetries present in the spaces $V_{0},V_{1},V_{2}$, this decomposition is very nearly the same as splitting up the matrix $\mathcal{M}$ in an ostensibly unrelated way. Each entry $\mathcal{M}(I,J)$ of $\mathcal{M}$ for $I,J\in{{[n]}\choose{2}}$ is the $0/1$ indicator for the presence of a clique on $I\cup J$. This indicator is just the AND of all the $\pm 1$ indicators $g_{b}$ for the presence of the edges $b\in\mathcal{E}(I\cup J)$. Taking a Fourier decomposition of this suggests a way to decompose $\mathcal{M}$ as \mathcal{M}=\sum_{\text{subsetsS$of edges on$4nodes}}\mathcal{M}_{S},This is not quite the whole picture, see Section 7.1.1. where the matrix $\mathcal{M}_{S}$ corresponds to the Fourier character $S$. The matrices $\mathcal{M}_{S}$ can be matched up to the subspaces $V_{0},V_{1},V_{2}$ in such a way that those matrices with larger spectral norm (corresponding to larger deviations from expectation) have subspaces with smaller eigenvalues in their kernels!

The foregoing is missing one subtlety. Some monomial matrices $\mathcal{M}_{S}$ do not match nicely to a single subspace. Instead they form cross terms: for example, having $V_{2}$ in the left kernel but not in the right kernel (not all these matrices need be symmetric). In fact, it is just such a matrix which keeps the simple moments from remaining PSD beyond $\omega\approx n^{1/3}$.

For the four nodes $a_{1},a_{2},b_{1},b_{2}$, consider the monomial $g_{a_{1},b_{1}}g_{a_{1},b_{2}}$ and the corresponding matrix $\mathcal{M}_{S}(\{a_{1},a_{2}\},\{b_{1},b_{2}\})\approx(\omega^{4}/n^{4})g_{a_{1},b_{1}}g_{a_{1},b_{2}}$. The entries $\mathcal{M}_{S}$ do not depend on $a_{1}$, and so there are many repeated rows, which creates a much larger spectral norm for $\mathcal{M}_{S}$ than if it had independent entries. [DM15] prove the (tight) bound $\|\mathcal{M}_{S}\|\approx\omega^{4}/n^{7/2}$. At the same time, it turns out only to have $V_{2}$ in its left kernel, not its right one. Appealing to the above picture, in order to have $\omega^{4}/n^{7/2}\ll\omega^{5/2}/n^{2}$, we must have $\omega\ll n^{1/3}$.

We make one further observation about the matrix $\mathcal{M}_{S}^{\prime}$ from the previous section: its rows are the tensor squares of the $\pm 1$ neighborhood indicator vectors $r_{i}$ from above. Our fix to the simple moments, described above as adjusting individual pseudo-expectations, amounts roughly to adding to $\mathcal{M}$ the matrix $(\omega^{5}/n^{5})\sum_{i}(r_{i}^{\otimes 2})(r_{i}^{\otimes 2})^{\dagger}$. This carves out of $V_{2}$ (our worst subspace from an eigenvalue perspective) a new subspaces space $V_{1.5}$ with eigenvalues lower-bounded by $\lambda_{1.5}\approx\omega^{5}/n\gg\omega^{2}/n^{2}$. Now instead of matching the bad matrix $\mathcal{M}_{S}$ to $V_{1}$ and $V_{2}$ as a cross term, we can match it to $V_{1}$ and $V_{1.5}$ as a cross term. Then we only need $\omega^{4}/n^{7/2}\ll\sqrt{\lambda_{1}\lambda_{1.5}}\approx\omega^{4}/n^{7/2}$. With some care in the details, the above picture can be made precise.

However, a crucial point is that the matrix $N=(\omega^{5}/n^{5})\sum_{i}(r_{i}^{\otimes 2})(r_{i}^{\otimes 2})^{\dagger}$ doesn’t satisfy the clique constraints (in that all entries $I,J$ with $I\cup J$ not a clique should be ). A chunk of our proof goes into analyzing the discrepancy between the matrix $N$ and its zeroed out version. Our analysis here requires the use of new combinatorial tools (Section 6.4) combined with the trace moment method.

As we have alluded to already, a key technical step in our proof is to show that certain Fourier-decomposed matrices of the form discussed above have some of the subspaces $V_{0},V_{1},V_{2}$ in their kernels. In the analysis of simple moments for degree $4$, [DM15] use explicit entries for canonical forms of eigenvectors in $V_{0},V_{1}$ to accomplish this. However this approach hits analytical roadblocks for the analysis in case of higher degrees. Canonical forms for the eigenvectors are hard to pin down explicitly from the literature in algebraic combinatorics.

A similar approach was utilized heavily by Grigoriev [Gri01a] to prove a sum of squares lower bound for the knapsack problem. While for degree $4$ either explicit eigenvectors or our approach will work, although the latter takes some more elbow grease, ours is absolutely vital for our tight analysis of the MPW moments for the higher degrees. We hope that such an approach will be useful for proving better (approaching $\omega\approx\sqrt{n}$) integrality gap for Sum of Squares relaxations of higher degree for Planted Clique and other related problems.

The analysis of the MPW operator at higher degrees also presents other new challenges that do not show up in the special case of degree $4$ analyzed in [DM15]. [DM15] deal with the optimization version of the degree $4$ SOS program which could be potentially weaker than the one we analyze here (and thus our lower bound is technically stronger). Working with the “optimization” version simplifies the analysis in [DM15] a little bit as the matrix $\mathcal{M}$ has entries that only have local dependence on the graph $G$. We explicitly work with the feasibility version of the degree 4 SOS program and thus, must deal with the additional complexity of the entries of $\mathcal{M}$ having a global dependence. As in [MPW15], we deal with this situation by separating $\mathcal{M}$ into matrices $L$ and $\Delta$ such that $L$ has only local dependence on the graph $G$. [MPW15] deal with $\Delta$ by a simple entrywise bound, however, employing such a bound yields no improvement over the bound proved in [MPW15] for us. It turns out that we have to do a fine grained analysis of the $\Delta$ matrix itself by a decomposition for $\Delta$ such that each piece is essentially only locally dependent on the graph. Once we have such a decomposition, our ideas from the analysis of $L$ can be extended to that setting as well.

Finally, our argument for analyzing the spectral norms of each of the pieces of encountered in the decompositions also needs to be much more general than in case of [DM15] to handle higher degrees. For this, we identify a simple combinatorial structure that controls the norm bounds and allows a general hammer for computing the norms of all the matrices that appear in this analysis. Our proofs here are based on the trace power method and build on the combinatorial techniques in [DM15].

6 Preview of Technical Toolkit

In this section we give a preview of the key lemmas that allow us to carry out the analyses described thus far. We have simplified some issues for the sake of exposition; details may be found in Section 6.

We are concerned with the matrices in the aforementioned Fourier decomposition. Let $B\subseteq[d]\times[d]$ be a bipartite graph on $2d$ vertices. Let $Q_{B}$ be an ${{[n]}\choose{d}}\times{{[n]}\choose{d}}$ matrix with entries

(We are ignoring what happens if $I\cap J\neq\emptyset$.)

This first lemma bounds the spectral norm of such a matrix in terms of the shape of $B$.

We also want to show that these matrices have nontrivial kernels, so we can bound their negative eigenvalues against the parts of the simple moments with larger positive eigenvalues. The following allows us to carry out this matching of Fourier decomposition matrices to eigenspaces $V_{0},\ldots,V_{d}$ of the expectation matrix.

7 Related Work

There’s a large amount of work on understanding Linear and Semidefinite Programming based hierarchies. A detailed survey on the sum of squares hierarchy and references to works related can be found in [BS14]. The earliest works on proving SoS lower bounds were due to Grigoriev [Gri01a, Gri01b] who showed that degree $\Omega(n)$ SoS does not beat the random assignment for 3SAT or 3XOR even on random instances from a natural distribution. Some of these lower bounds were rediscovered by Schoenebeck [Sch08]. Lower bounds for SOS essentially rely on gadget reductions from 3SAT or 3XOR and this approach has been understood in some detail [Tul09, BCV+12]. An exception to this methodology is the recent work of Barak et al. in proving SoS lower bounds for pairwise independent CSPs [BCK15]. Even though the lower bounds for CSPs are for random instances, the average-case nature of the problem does not show up as a main analytic issue. There has recently been a surge of interest in understanding the performance of SoS on average-case problems of interest in machine learning, both in proving upper and lower bounds [HSS15, BM15, MW15, GM15, BKS15].

For the planted clique problem, Feige and Krauthgamer gave an analysis of the performance of the LS+ semidefinite heirarchy tight to within constants [FK00, FK03] giving the state of the art algorithm for finding planted cliques in any fixed polynomial time. Other algorithmic techniques not based on convex relaxations have been studied and shown to fail for planted clique beyond $\omega\approx\sqrt{n}$, most prominantly Markov Chain Monte Carlo (MCMC) [Jer92]. Recently, Feldman et. al. [FGR+13] showed a lower bound for (a variant of) the planted clique problem in the restricted class of statistical algorithms that generalize MCMC based methods and many other algorithmic techniques. Frieze and Kannan [FK08] proposed an approach for the planted clique problem through optimizing a degree-$3$ polynomial related to the random graph. Such polynomials are NP hard to optimize in the worst case but the belief is that the random nature of the polynomials might be helpful. This approach was generalized to higher degree polynomials by Brubaker and Vempala [BV09].

There has also been recent work on variants of the problem that define Gaussian versions of the planted clique and more generally, the hidden submatrix problems showing, for example, strong inditinguishability results about the spectrum of the associated matrices with and without planting [MRZ14]. Finally, the present work builds heavily on independent papers of Meka, Potechin, and Wigderson [MPW15] and Deshpande and Montanari [DM15], which we have already thoroughly discussed.

Section 3 contains preliminaries. Section 4 contains definitions and the necessary background on the simple moments, a.k.a. the MPW operator. Section 5 contains the formal definition of our corrected degree $4$ moments. Section 6 lays out the technical framework for the analyses of the corrected degree $4$ moments and for the tightened bounds on the MPW operator at higher degrees. Here we define the Fourier decompositions alluded to above and carry out representation-theoretic arguments about their kernels. Section 7 and Section 8 use the tools we have built thus far to prove the main theorems. In Section 9 we prove a technical concentration result for small subgraphs of $G(n,1/2)$ required for the analysis. In Section 10 we sketch Kelner’s argument showing that our analysis of the MPW moments is nearly optimal.

Preliminaries

We will use the following general notation in the paper.

$G$ will denote a draw from $G(n,\frac{1}{2})$ unless otherwise stated.

For a square symmetric matrices $Q,R$, we write $Q\succeq R$ to mean $Q-R$ is positive semidefinite.

For any matrix $M$, $||M||$ denotes its largest singular value, or, equivalently, $||M||=\max_{x:||x||_{2}=1}||Mx||^{2}.$

For matrices $M,N$ of same dimensions, $M\odot N$ denotes their entrywise or Hadamard product, i.e., $(M\odot N)(I,J)=M(I,J)\cdot N(I,J)$ for every $I,J$.

For a graph $G$ and any set of two vertices of $G$, $e$, $g_{e}$ denotes the $\{-1,1\}$ indicator of the edge $e$ being present in $G$. That is, $g_{e}=+1$ if $e$ is an edge in $G$ and $-1$ otherwise.

For a set $I$ of vertices of $G$, $\mathcal{E}(I)={I\choose 2}$, the set of all pairs from $I$.

For a pair of subsets of vertices $I,J$ of $G$, $\mathcal{E}_{ext}(I,J)=\mathcal{E}(I\cup J)\setminus(\mathcal{E}(I)\cup\mathcal{E}(J)),$ the set of cut edges between $I$ and $J$.

For a subspace $V$, $\Pi_{V}$ denotes the projector to $V$.

Following [BBH+12] and many subsequent papers, we work with SoS using the language of pseudo-expectations.

Let $p_{0},\ldots,p_{k}\in\mathcal{P}_{d}^{n}$. If a pseudo-expectation satisfying the constraints $\{p_{0}=0,\ldots,p_{k}=0\}$ exists, it can be found in time $n^{O(d)}$. If none exists, a certificate of infeasibility of these equations is found instead.

The following observations (actually both the same observation in different forms) will come in handy in our analysis.

by our assumptions on $P_{i}MP_{j}$ and Cauchy-Schwarz. For each $i,j$, we know $\frac{1}{k}(\|P_{i}x\|\lambda_{i}+\|P_{i}x\|\lambda_{j})\geqslant\frac{2}{k}\|P_{i}x\|\|P_{j}x\|\sqrt{\lambda_{i}\lambda_{j}}$, which implies that the whole expression is nonnegative. ∎

The MPW Operator

For any set $I\subseteq[n]$, let $x_{I}$ be the monomial $\Pi_{i\in I}x_{i}$.

Further, we set $C_{2d}=C_{2d}(G)$ be the number of $2d$-cliques in $G$.

Our analysis improves upon the analysis in [MPW15] and generalizes the improved analysis for the special case of $d=2$ done in [DM15]. By a generalization of the counter example due to Kelner, our analysis can actually be shown to be tight. We defer the details of the counter example to the full version. In the remaining part of this section, we begin the task of proving Theorem 4.4 by introducing certain simplifications and computing the eigen values of the expected value of the matrix under $G(n,\frac{1}{2})$.

Observe that for any $I,J$, $\mathcal{M}^{\prime}(I,J)$ is chosen so as to depend only on the edges with one end point in $I$ and the other in $J$. Intuitively, this corresponds to thinking of $I$ and $J$ as being cliques in $G$ by addition of some edges. Moreoever, $\mathcal{M}^{\prime}(I,J)$ is chosen so that $\mathcal{M}^{\prime}(I,J)=M(I,J)$ whenever $I,J$ are actually cliques in $G$. Thus, as noted above, we have the following fact (which is Lemma 5.1 in [MPW15]).

$\mathcal{M}$ is PSD if $\mathcal{M}^{\prime}$ is PSD.

Thus, the following lemma completes the proof of Theorem 4.4.

2 The Expectation Matrix

We first describe the entries of the matrix $\mathcal{M}^{\prime}$.

Next, we need a basic fact about the (shared) eigenspaces of all the set symmetric matrices, in particular, their number and dimensions which follows from the following well known result from classical theory of Johnson schemes.

For $0\leqslant j\leqslant d$, $dim(V_{j})={n\choose j}-{n\choose{j-1}}$.

Using a nice basis for the matrices in $\mathcal{J}$, one can obtain the following estimates of the eigenvalues of $E$ on $V_{i}$ for each $0\leqslant i\leqslant d$:

Let $\omega<\frac{n-2d}{3d2^{d-1}}$ and $d\leqslant\omega/2$. Let $\lambda_{j}(E)$ be the eigenvalue of $E$ on $V_{j}$ as defined in Fact 4.9. Then,

The Corrected Operator for Degree Four

In this section, we present the pseudodistribution that we will use to show an almost optimal lower bound on the degree $4$ SOS algorithm. Our pseudodistribution is obtained by “correcting" the one described in the previous section. The correction itself is inspired by an explicit polynomial described by Kelner who showed that the pseudodistribution from the previous section for degree $4$ does not satisfy positivity for $\omega\gg n^{1/3}$.

Let $\gamma>0$ be a real parameter to be chosen later. Let $\operatorname{\mathcal{L}}$ be the linear operator on the linear space of homogeneous, multilinear polynomials of degree $4$ such that:

For $\omega>0$ and $c\ll\omega$, there exists $x$, $x=\omega\pm O(c/\omega^{3})$, such that ${x\choose 4}={\omega\choose 4}+c$.

We first use the correction operator $\operatorname{\mathcal{L}}=\operatorname{\mathcal{L}}_{\gamma}$ to define the corrected moments on all multilinear monomials of degree $4$. For every $S\subseteq[n]$, $|S|=4$, we set:

Then we know there exists $\omega^{\prime}=\omega\pm O(c/\omega^{3})>0$ satisfying ${\omega^{\prime}\choose 4}\stackrel{{\scriptstyle\textrm{def}}}{{=}}{\omega\choose 4}+c$ (using Fact 5.2). Thus, the degree $4$ moments we defined “think” $\sum_{i}x_{i}=\omega^{\prime}$. We use this relationship to extend the definition to all the monomials. For every $S\subseteq[n]$, $|S|=3$,

Furthermore, if $G\sim G(n,1/2)$, then with probability $1-O(n^{-25})$, $|\omega^{\prime}-\omega|<O(\gamma\log(n)^{2}\omega^{2}/n^{5/2})$.

There is $\omega_{0}=\Omega(\sqrt{n}/\operatorname{polylog}n)$ and $\gamma=\Theta(1)$ so that for $\omega\leqslant\omega_{0}$, with probability at least $1-1/n$ over the draw of $G\sim G(n,\frac{1}{2})$, $\mathcal{N}^{\prime}\succ 0$.

We prove the first item; the others are similar.

The proof is by several applications of McDiarmid’s inequality. By a standard Chernoff bound there is a universal constant $C_{0}$ so that for every $s\in[n]$ and every $i,j,k\in[n]$, with probabilty $1-O(n^{-40})$,

for some other universal constant $C_{1}$. So by McDiarmid’s inequality there is $C_{2}$ so that with probability $1-O(n^{-34})$,

By a similar argument there is $C_{3}$ so that for every $s,i\in[n]$, with probability $1-O(n^{-30})$,

for some other constant $C_{4}$. The result follows by a final application of McDiarmid’s inequality (we lose a factor of $n$ at this step as opposed to the $\sqrt{n}$ at previous steps because there are $\approx n^{2}$ edges to be revealed). ∎

We can now complete the proof of Lemma 5.5 using Lemma 5.7 and Fact 5.2.

In Section 6, we develop some general tools for analyzing the matrices that we encounter before going on to prove Theorem 4.4 and Lemma 5.6.

Tools

We provide background in the required tools from basic representation theory below.

For a finite dimensional complex vector space $V$, let $Hom(V,V)$ be the set of all linear maps from $V$ into $V$. For any finite group $G$ and $\pi:G\rightarrow Hom(V,V)$, the pair $(\pi,V)$ is said to be a representation of $G$ if $\pi$ satisfies, for any $g_{1},g_{2}\in G$,

where the “$\cdot$” on the LHS corresponds to the group operation and on the RHS, the composition of linear maps on $V$. When the map $\pi$ is clear from the context (as some natural action of the group $G$ on $V$), we abuse notation and just say that $V$ is a representation of $G$.

Let $(\pi,V)$ be a representation of a group $G$. A subspace $W\subseteq V$ is said to be a subrepresentation if for every $w\in W$, $\pi(g)w\in W$ for every $g\in G$. That is, $W$ is a stable or invariant subspace for all the linear maps $\pi(g)$, one for each $g\in G$. Observe that in this case, $(\pi,W)$ is another representation of $G$. A representation $(\pi,V)$ of $G$ is said to be irreducible if for any subspace $W$ invariant under all the linear maps $\pi(g)$ for $g\in G$, $W=V$ or $W=\{0\}$.

Suppose $(\pi,V)$ and $(\pi^{\prime},W)$ are representations of a group $G$. Suppose $L:V\rightarrow W$ is a linear map such that for any $g\in G$ and $v\in V$,

Then, for any irreducible representation $V_{i}\subseteq V$ under $\pi$, $L(V_{i})\subseteq W$ is an irreducible representation in $W$ under $\pi^{\prime}$.

2 Eigenspaces of the Set Symmetric Matrices

The set of all set symmetric matrices is known as the Johnson scheme in algebraic combinatorics. All such matrices commute and thus share eigenspaces. While the matrices in the Johnson scheme are well studied, the description of the eigenspaces in the literature is hard to use for the purpose of our proofs. We thus take a more direct approach and use basic representation theory in what follows to identify a simple symmetry condition on the eigenspaces of set symmetric matrices which will be useful to understand the spectral properties of the matrices we study.

Then, $v\in V_{0}\oplus V_{1}\oplus\cdots\oplus V_{t}$.

3 Kernels of Patterned Matrices

In this section we design some general tools to understand the spectral structure of matrices that have restricted variations around the set symmetric structure discussed in the previous section. The main tool we will use to establish these results is Lemma 6.4 shown in the previous section. Before moving on to this task, we describe a high level overview of what we intend to do. The following paragraph can be skipped to dive directly into the technical details without the loss of continuity.

The study of the eigenspaces of set symmetric matrices lets us completely understand the spectral structure of the expectation matrix $E$. In the next section when we analyze the spectrum of $\mathcal{M}^{\prime}$, we will encounter matrices that depend on the underlying graph $G$ and thus are not set symmetric. However, if the dependence on the underlying graph $G$ is in some sense limited, we hope that some of the nice algebraic properties that set symmetry grants us should perhaps continue to hold. In our case, we will be able to decompose $E$ into various pieces and for each of these pieces, the entry at $(I,J)$ has dependence on the graph $G$ based only on the status (edge vs no edge) of a small number of pairs $(i,j)\in I\times J$. The goal of this section is to develop tools to understand certain (coarse) spectral properties of such matrices.

and the right automorphism group of $B$ as

We are now ready to define patterned matrices:

When $q=0$, we write $Q_{B,f}$ for the corresponding patterned matrix.

The following result describes the kernels of certain symmetrized sums of $Q_{B,Z,f}$ and is the main claim of this section.

We first show that $u$ above is well defined in that the definition does not depend on the specific subset $I_{T}$ used so long as $I_{T}\supseteq T$. We adopt the notation (that ignores the “direction” of action) $B^{\sigma}\stackrel{{\scriptstyle\textrm{def}}}{{=}}\sigma\circ B$ only for the calculations that follow.

We can equivalently write the claim above as:

This completes the proof using Lemma 6.4. ∎

4 Concentration for Locally Random Matrices over G​(n,12)𝐺𝑛12G(n,\frac{1}{2})

For $d\geqslant 2$, $d=O(\log{(n)})$, and a bipartite graph $B\in\mathcal{B}$, let $Q=Q_{B,f}$ be a patterned matrix with $f(x)=\prod_{b\in B}x_{b}$. That is,

The next main result of this section considers a different class of matrices that appear in the analysis in Section 8.

Let $U\subseteq\times$ be a bipartite graph on $4$ vertices and suppose $U$ is nonempty. Let $M\in{{[n]}\choose{2}}\times{{[n]}\choose{2}}$ be a matrix with the entry at $\{a_{1},a_{2}\}$, $\{b_{1},b_{2}\}$ for $a_{1}\leqslant a_{2}$ and $b_{1}\leqslant b_{2}$ are given by

The proofs of both these results are based on the standard idea of analyzing the trace of higher powers of a matrix to prove bounds on its spectral norm. The proof of Lemma 6.11 is similar to the proofs via the trace power method for bounding the norms of matrices as presented in [DM15]. The general format we present here will come in handy for multiple applications to various matrices in Section 7. Lemma 6.12 deals with somewhat more complicated matrices that appear in the analysis of the corrected operator for degree $4$ lower bound. Nevertheless, as is common in such proofs, the analysis is based on a combinatorial analysis of the terms that make non zero contribution to the trace powers combined with the simplifying effect of random partitioning based arguments. We describe the details of the proof in the following section.

It is enough to show that $Q^{\prime}$ occurs as a principal submatrix of $Q$. For this, take the submatrix of rows and columns of $M$ indexed by tuples $(a_{1},\ldots,a_{d})$ in sorted order, i.e., with $a_{1}\leqslant a_{2}\leqslant\ldots a_{d}$. ∎

We will use the following lemma to break dependencies in certain random matrices by decomposing them into matrices whose entries, while still dependent, have additional structure.

Suppose $Q(I,J)=0$ when $I\cap J\neq\emptyset$. Let $(S_{1}^{1},\ldots,S_{k}^{1}),\ldots,(S_{1}^{r},\ldots,S_{k}^{r})$ be a sequence of partition of $[n]$ into $k$ bins. Each partition induces a matrix based on $Q$ as follows:

Then, there is a family of partitions $(S_{1}^{1},\ldots,S_{k}^{1}),\ldots,(S_{1}^{r},\ldots,S_{k}^{r})$ such that $Q=\sum_{i=1}^{r}Q_{i}$ with $r\leqslant O(k^{k}\log n)$.

where $T^{i}_{(a_{1},\ldots,a_{d}),(b_{1},\ldots,b_{d})}$ is the set of indices $j$ so that $j,(a_{1},\ldots,a_{d}),(b_{1},\ldots,b_{d})$ respect the partition $(S_{1}^{i},\ldots,S_{k}^{i},T^{i})$ and do not respect any partition $(S_{1}^{i^{\prime}},\ldots,S_{k}^{i^{\prime}},T^{i^{\prime}})$ for any $i^{\prime}<i$.

Then, there is a family $(S_{1}^{1},\ldots,S_{k}^{1},T^{1}),\ldots,(S_{1}^{r},\ldots,S_{k}^{r},T^{r})$ of partitions of $[n]$ so that $Q=\sum_{i=1}^{r}Q_{i}$ with $r\leqslant O((k+1)^{k+1}\log n)$.

We present the proof of 1; the proof of 2 is almost identical. For $r$ to be chosen later, we pick partitions $(S_{1}^{1},\ldots,S_{k}^{1}),\ldots,(S_{1}^{r},\ldots,S_{k}^{r})$ uniformly at random and independently so that each is partition of $[n]$ into sets of size $n/k$ each.

Call $(a_{1},\ldots,a_{d}),(b_{1},\ldots,b_{d})$ good at step $i$ if $a_{j},b_{j}\in S_{j}^{i}$ for every $j<k$ and $a_{j},b_{j}\in S_{k}^{i}$ if $j\geqslant k$. It is enough to show that after $r\leqslant O(k^{k}\log n)$ steps the probability that every $\{a_{1},\ldots,a_{d},b_{1},\ldots,b_{d}\}$ of size $2d$ is good at some step $i\leqslant r$.

Fix some $(a_{1},\ldots,a_{d}),(b_{1},\ldots,b_{d})$ with $|\{a_{1},\ldots,a_{d},b_{1},\ldots,b_{d}\}|=2d$. It is good at step $i$ with probability at least $k^{-k}$. Since the steps are independent, after $r$ steps

which is at most $1/n^{10d}$ for some $r=O(k^{k}\log n)$.

Taking a union bound over all $O(n^{2d})$ tuples $(a_{1},\ldots,a_{d}),(b_{1},\ldots,b_{d})$ with $|\{a_{1},\ldots,a_{d},b_{1},\ldots,b_{d}\}|=2d$ completes the proof. ∎

The usefulness of the above definition is captured by the following claim:

4.2 Graph-Theoretic Definitions and Lemmas

In this section, we set up some notation and definitions helpful in our proofs of the main results of this section. The next few definitions and notation are generalization of the ones used in [DM15] to general degrees $d$ and are useful in the proof of Lemma 6.11.

Let $G$ be a graph. A labeled $U$-ribbon $R$ is a tuple $(R,F)$ where $R$ is a $U$-ribbon and $F:R\rightarrow G$ is a map labeling each vertex of $R$ with a vertex in $G$. We require that for $(u,v)$ an edge in $R$, $F(u)\neq F(v)$.

Let $(R,F)$ be a labeled $U$-ribbon where $U$ has $2d$ vertices. We say $(R,F)$ is disjoint if for every $i$,

Let $(R,F)$ be a labeled $U$-ribbon where $U$ has $2d$ vertices. We say that $(R,F)$ is contributing if no element of the multiset $\{(F(u),F(v))\,:\,(u,v)\in R\}$ occurs with odd multiplicity.

The following combinatorial lemma will serve as a tool in the proofs of the main results for this section.

The assumption on $U$ implies that $R$ contains the cycles

The next few definitions and notation are needed in the proof of Lemma 6.12.

Where $G$ is a graph, a labeled fancy $U$-ribbon is a tuple $(R,F)$ where $R$ is a fancy $U$-ribbon and $F:R\rightarrow G$ labels each vertex of $R$ with a vertex in $G$. We require for any edge $(u,v)\in R$ that $F(u)\neq F(v)$.

When $U$ is empty the proof is similar: there are two paths, $\{a_{i}^{1},b_{i}^{1},c_{i}\}$ and $\{a_{i}^{2},b_{i}^{2},c_{2}\}$. ∎

4.3 Proofs of Lemma 6.11 and Lemma 6.12

By Lemma 6.13 it is enough to prove the analogous claims for the $n^{d}\times n^{d}$ matrix $Q$ with entries given by

By multiplying $Q$ by suitable permutation matrices $P,P^{\prime}$ to give $PQP^{\prime}$, we may assume in the $2$-matching case above that the matching is $\{(1,1),(2,2)\}$ and in the nonempty graph case that the edge contained is $(1,1)$ (where we think of the vertex set of $U$ as $[d]\times[d]$). Note that $\|Q\|=\|PQP^{\prime}\|$.

We apply Lemma 6.14 to obtain a family of matrices $\{Q_{i}\}_{i\in[r]}$ for some $r=O(3^{3}\log n)=O(\log n)$ satisfying $Q=\sum_{i}Q_{i}$. On any entry $(a_{1},\ldots,a_{d}),(b_{1},\ldots,b_{d})$ on which $Q_{i}$ is nonzero it is equal to $Q$ at that entry, and furthermore for each $Q_{i}$ there is a partition $(S_{1}^{i},\ldots,S_{3}^{i})$ of $[n]$ so that if $Q_{i}[(a_{1},\ldots,a_{d}),(b_{1},\ldots,b_{d})]\neq 0$ then $a_{1},b_{1}\in S_{1}^{i},a_{2},b_{2}\in S_{2}^{i}$, and $a_{j},b_{j}\in S_{3}^{i}$ for all $j>2$.

Taking a union bound over the $\log n$ matrices $Q_{i}$, we get that

and so by the triangle inequality applied to $\|M\|=\|\sum_{i}Q_{i}\|$, we get

We first handle the case when $U$ is non empty. By Lemma 6.13 it is enough to prove the analogous statement for the $n^{2}\times n^{2}$ matrix, also by abuse of notation denoted $Q$, which is the sum of matrices (abusing notation again) $Q_{k}$ with entries given by

By multiplication with an appropriate permutation matrix (which cannot change the spectral norm), we may assume that $U$ contains the edge $(1,1)$. We begin with 2 from Lemma 6.14, whose hypotheses are satisfied by our convention $y_{a,a}=0$. This gives a family $Q_{1},\ldots,Q_{r}$ with $r=O(3^{3}\log n)=O(\log n)$ so that $\sum_{i=1}^{r}Q_{i}$ and a corresponding family of partitions $(S^{1}_{1},S^{1}_{2},T^{1}),\ldots,(S_{1}^{r},S_{2}^{r},T^{r})$. Lemma 6.14 guarantees that $Q_{i}[(a_{1},a_{2}),(b_{1},b_{2})]=\sum_{k\in T}y_{k,a_{1}}y_{k,a_{2}}y_{k,b_{1}}y_{k,b_{2}}\prod_{(i,j)\in U}y_{a_{i},b_{j}}$ for some $T\subseteq T^{i}$ when $a_{1},b_{1}\in S_{1}^{i}$ and $a_{2},b_{2}\in S_{2}^{i}$ and is zero otherwise.

By a union bound and triangle inequality, we then get

The proof in the case of $U$ empty is similar, using Lemma 6.23 in the empty $U$ case.

Analyzing Deviations for the Degree-d𝑑d MPW Operator

In this section, we use the tools developed in Section 6 to analyze the spectrum of the deviation matrix $D=\mathcal{M}^{\prime}-E$ and prove Lemma 4.7.

As noted in Section 7, we decompose $\mathcal{M}^{\prime}=E+D$. For any $I,J\in{{[n]}\choose{d}}$, $D(I,J)$ depends on a) $\deg(I\cup J)$ and b) whether $\mathcal{E}_{ext}(I,J)\subseteq G$. If $D(I,J)$ depended only on b) above, then it could be decomposed into a sum of patterned matrices defined in Section 6; analyzing these is tractable. Our first step is thus to get rid of the dependence on $\deg(I\cup J)$—the only part depending on the entire graph. We will obtain a matrix $L$ that depends only on whether $\mathcal{E}_{ext}(I,J)\subseteq G$ or not (and thus is “locally random" in the sense of [MPW15]).

and $p(i)=2^{-(d-i)^{2}}$ for each $i$. We set $L(I,J)$ for every $I,J\in{{[n]}\choose{d}}$ to be

The first is regarding the high level approach. The approach of [DM15] used explicit expressions for a canonical set of eigenvectors in $V_{1}$ to obtain similar conclusions as us for the case of $d=2$. This approach gets unwieldy very quickly because the explicit entries of eigenvectors for $V_{i}$ for $i>1$ are hard to work with [BI84]. We tackle this issue by developing an argument that doesn’t need explicit entries of the eigenvectors. Instead, we use basic representation theory (Section 6.3) to identify a set of symmetries satisfies by vectors in $V_{i}$ for each $i$ and use it obtain the conclusions we require.

Second, [DM15] deal with the optimization version of the degree $4$ SOS program which, as noted in the introduction, could be potentially weaker than the one we analyze here (and thus our lower bound is technically stronger). This simplifies the analysis in [DM15] a little bit as the matrix $\Delta$ defined above is identically zero for the operator analyzed. We explicitly work with the feasibility version of the degree 4 SOS program and thus, must deal with the additional complexity of handling $\Delta$. It turns out that we have to do a fine grained analysis of the $\Delta$ matrix itself. The decomposition we use for $\Delta$ is somewhat different from the case of $L$ even though, the analysis of each piece of the decomposition proceeds similar to the case of $L$.

Third, for the special case of $d=2$, essentially the only matrix one has to analyze is the $L_{0}$, the matrix obtained by zeroing out all entries $(I,J)$ in $L$ such that $I\cap J\neq\emptyset$: a uniform bound on spectral norm of the remaining component suffices. However, for higher $d$, one has to deal with the “non-disjoint" entries with some care and an argument analogous to the one in [DM15] fails to show PSDness of $\mathcal{M}^{\prime}$ beyond $\omega\approx n^{\frac{1}{2d}}$ giving no asymptotic improvement over [MPW15].

Finally, our argument for analyzing the spectral norms of each of the pieces also needs to be much more general than in case of [DM15] to handle higher degrees. For this, we identify a simple combinatorial structure (size of maximum matchings in appropriate bipartite graphs on $2d$ vertices) that controls the bounds and could also be used to obtain slick proofs of the conclusions required in [DM15] in the context of analyzing $\mathcal{M}^{\prime}$ for $d=2$. Our combinatorial argument itself is a generalization of the one given by [DM15] for this case.

With probability at least $1-\frac{1}{n}$ over the draw of $G\sim G(n,\frac{1}{2})$, each $0\leqslant i\leqslant d$ satisfies

The next lemma does a (even more) fine grained analysis of the spectrum of $\Delta$:

With probability at least $1-\frac{1}{n}$ over the draw of $G\sim G(n,\frac{1}{2})$, for each $0\leqslant i\leqslant d$:

We can now use Lemma 7.2 and Lemma 7.3 to complete the proof of Lemma 4.7.

For each $0\leqslant i,j\leqslant d$, we compute $\Pi_{i}\mathcal{M}^{\prime}\Pi_{j}$ and use Lemma 3.4. We write $\mathcal{M}^{\prime}=E+L+\Delta$. First, $\Pi_{i}^{\dagger}E\Pi_{j}=0$ whenever $i\neq j$ as $\Pi_{i}$ are projectors to eigenspaces of $E$. Let $\lambda_{0},\lambda_{1},\ldots,\lambda_{d}$ be the eigenvalues of $E$ on eigenspaces $V_{0},V_{1},\ldots,V_{d}$. From Lemma 4.10, we have:

In what follows, all our statements hold with probability at least $1-O(1)/n$:

Using Lemma 7.2 and Lemma 7.3, for every $i\geqslant 2$,

Then, it is easy to check that for any $\omega=O(n^{\frac{1}{d+1}})$,

Next, we bound the cross terms $|\Pi_{i}(L+\Delta)\Pi_{j}|$ for $i\neq j$. Again, using Lemma 7.2 and Lemma 7.3, we have for $i,j\geqslant 2$:

For $\omega\leqslant O(n^{\frac{1}{d+1}})$, it is again easy to check that, for $i,j\geqslant 2$, the above expression is at most $\frac{2}{d}\sqrt{\lambda_{i}\lambda_{j}}$.

In the case when one of $i,j$ is at most $1$, we have the bound

In this case, it is easy to check that so long as $\omega=O(n^{\frac{1}{d+1}}/\operatorname{poly}\log{(n)})$,

By an application of Lemma 3.4, the proof is complete. ∎

We first describe the high level idea of the proof.

We start by decomposing $L=\sum_{q=0}^{d}L_{q}$ where $L_{q}(I,J)=L(I,J)$ if $|I\cap J|=q$ and otherwise. Notice that each $L_{q}$ then is obtained by a scaling an appropriate $0/1$ matrix.

Most illuminating is the disjoint case $L_{0}$, which is nonzero only at entries $I,J$ with $I\cap J=\emptyset$. For any disjoint $I,J$, $L_{0}(I,J)$ depends only whether $\mathcal{E}_{ext}(I,J)\subseteq G$, which, one could write as an appropriately scaled AND function of the indicators $g_{e}$ of edges $e\in\mathcal{E}_{ext}(I,J)$. We can expand this AND function in the monomial (parities of subsets of $g_{e}$ variables) basis. Each such monomial corresponds to the bipartite graph $B$ that contains the pairs $e\in\mathcal{E}_{ext}(I,J)$ that constitute the monomial. This gives a decomposition of $L_{0}$ into $2^{d^{2}}-1$ (since the constant term is , $L$ being zero mean) components, $L_{0}^{B}$ for each non empty, labeled bipartite graph on $[d]\times[d]$.

We can bound the spectral norm of each of the pieces $L_{0}^{B}$ by direct application of tools derived in Section 6.4. The main work in this section goes into showing that depending upon the structure of $B$, an appropriate selection of subspaces $V_{i}$ lie in left or right kernels of $L_{0}^{B}$. Thus, for a fixed term $\Pi_{i}L\Pi_{j}$, some $L_{0}^{B}$ do not contribute. We identify the maximum spectral norm among contributing terms to obtain the final bound.

To accomplish this goal, we rely heavily on the tools built in Section 6.3 which give us a handle on the symmetries of the eigenspaces $V_{0},V_{1},\ldots,V_{d}$. This requires some work based on representation theory of finite groups and is presented in Lemma 6.4 and Lemma 6.9.

The case of $L_{q}$ for $q\neq 0$ needs even finer decomposition. We decompose each $L_{q}$ ($q>0$) into matrices that identify the “pattern" of the $q$ intersecting vertices. In [MPW15] a similar idea is used to reduce the task of bounding the spectral norm of $L_{q}$ to a calculation similar to one in the case of $L_{0}$. However, unlike [MPW15], we also require properties of the kernels of the components of the decomposition. After restricting to a fixed intersection pattern of $q$ vertices, we thus resort to using a generalization of the kernel analysis used for the $L_{0}$ case. We now proceed with the proof plan as described beginning with the decomposition of each $L_{q}$.

1.1 Decomposing L𝐿L

We start by decomposing $L$ further as $L=\sum_{q=0}^{d}L_{q}$ where for any $I,J\in{{[n]}\choose{d}}$,

Recall that $\mathcal{B}$ is the set of all bipartite labeled graphs with left and right vertex sets labeled by $[d]$ and $[d]$. Recall also from Section 6.3 that for any $I,J\subseteq[n]$ with $|I|=|J|=d$, the graph $\zeta_{I,J}(B)$ is a copy of $B$ on vertex sets $I,J$ where the correspondence between $I$ and $[d]$ and $J$ and $[d]$ is determined by the sorting map $\zeta$. Finally, recall that for a graph $G$ on $[n]$, we let $g_{b}$ be the $\pm 1$ indicator for the presence of edge $b$ in $G$, and by convention $g_{b}=0$ when $b=(i,i)$ for any $i\in[n]$. For any $B\in\mathcal{B}$, define an ${{[n]}\choose{d}}\times{{[n]}\choose{d}}$ matrix

We think of $L_{0}$ as a rescaling and centering of a $0/1$ matrix whose entries are the AND of the $\pm 1$ indicators for the edges in $\mathcal{E}_{ext}(I,J)$. Decomposing these ANDs into monomials over those $\pm 1$ indicators, we see that each monomial corresponds exactly to one bipartite graph $B$, and the centering of $L_{0}$ corresponds to removing the constant monomial, which corresponds to the empty bipartite graph. Every other monomial recieves equal weight $2^{-d^{2}}$ in this expansion, and so from these observations it becomes routine to verify that

Similarly, we further decompose $L_{q}$ for $q>0$. Here things are a bit more involved. Let us motivate our decomposition by understanding the structure of the matrix $L_{q}$ for $q>0$ a little bit. Consider an entry $(I,J)$ such that $I\cap J=K$. Then, $\mathcal{E}_{ext}(I,J)\subseteq\mathcal{E}_{ext}(I\setminus K,J\setminus K)$. Thus, the edge structure in the bipartite subgraph on vertex sets $I\setminus K$ and $J\setminus K$ decides the value of $L(I,J)$ for any graph $G$ and we can hope to a get a patterned matrix. We now follow this intuition.

We now define a matrix which is nonzero only on entries which intersect in at least $q$ places:

Finally, it is again easy to verify that:

1.2 Spectral Analysis of L𝐿L

In order to prove Lemma 7.2, we will first use the decomposition described in the previous section to write $L_{q}$ as a sum of appropriate patterned matrices. We will then partition the sum into groups, each group corresponding to an equivalence class of (left or right) similar bipartite graphs $B$. We will infer some properties about the kernel and finally use the spectral norm bounds from Section 6.4 to complete the proof.

With probability at least $1-1/n^{10}$ over the draw of $G\sim G(n,\frac{1}{2})$,

Before proving the three claims above, we show how they imply Lemma 7.2:

For the second part, fix an $i\geqslant 2$. We first show that some terms in the decomposition in (7.3) do not contribute to $\left|\Pi_{i}^{\dagger}L_{q}\Pi_{i}\right|$.

In the remaining part of this section, we complete the proofs of Claims 7.6 and 7.5.

1.3 Proof of Claims

In this section, we obtain quick proofs of the three claims above using the tools developed in Section 6.

The proof is by appealing to Fact 3.3. Observe that

The next is a direct application of Lemma 6.9.

Finally, we prove Claim 7.5 using Lemma 6.11.

where $K\subseteq[n]$ is some fixed subset of size $q$ such that $K\cap I^{\prime}=K\cap J^{\prime}=\emptyset$.

2 Proof of Lemma 7.3

We now move on to analyzing the spectrum of the matrix $\Delta$.

The high level plan of the proof is similar to that of Lemma 7.2. We define $\Delta_{i}$ for each $0\leqslant i\leqslant d$ as follows:

We further split $\Delta_{q}=\sum_{K:|K|=q}\Delta_{q,K},$ where:

First, we observe that $\Delta_{0}=0$. This is because $\deg(I\cup J)$ when $I$ and $J$ are disjoint is exactly $1$ and doesn’t depend on the graph. Thus, $\Delta=\sum_{i=1}^{n}\Delta_{i}.$ As before we would like to spot patterned matrices in each $\Delta_{i}$ to show that appropriate eigenspaces $V_{j}$ lie in the kernel of $\Delta_{i}$. In case of $\Delta_{q}$, however, there’s a difference how this needs to be done. This is because each entry $(I,J)$ of $\Delta_{i}$ potentially depends on the edges from every vertex in the graph $G$ to $I$ and $J$. This is unlike the case of $L$ where the $(I,J)$ entry depends only on the edges between $I$ and $J$ (in fact that’s the reason we separated $L$ from $\Delta$ in the analysis). Nevertheless, we give a decomposition below that will help us make claims similar to the ones in the case of analyzing $L$ in this case too.