Switching Graph Matrix Norm Bounds: From i.i.d. to Random Regular Graphs

Xu, Jeff

doi:10.4230/LIPIcs.CCC.2025.11

Switching Graph Matrix Norm Bounds:
From i.i.d. to Random Regular Graphs

Jeff Xu

Carnegie Mellon University, Pittsburgh, PA, USA

Abstract

In this work, we give novel spectral norm bounds for graph matrix on inputs being random regular graphs. Graph matrix is a family of random matrices with entries given by polynomial functions of the underlying input. These matrices have been known to be the backbone for the analysis of various average-case algorithms and hardness. Previous investigations of such matrices are largely restricted to the Erdős-Rényi model, and tight matrix norm bounds on regular graphs are only known for specific examples. We unite these two lines of investigations, and give the first result departing from the Erdős-Rényi setting in the full generality of graph matrices. We believe our norm bound result would enable a simple transfer of spectral analysis for average-case algorithms and hardness between these two distributions of random graphs.

As an application of our spectral norm bounds, we show that higher-degree Sum-of-Squares lower bounds for the independent set problem on Erdős-Rényi random graphs can be switched into lower bounds on random $d$ -regular graphs. Our main conceptual insight is that existing Sum-of-Squares lower bounds analysis based on moment methods are surprisingly robust, and amenable for a light-weight translation. Our result is the first to address the general open question of analyzing higher-degree Sum-of-Squares on random regular graphs.

Keywords and phrases:

Semidefinite programming, random matrices, average-case complexity

Funding:

Jeff Xu: Supported in part by NSF CAREER Award #2047933.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Semidefinite programming

Related Version:

Full Version: https://arxiv.org/abs/2411.14314

Acknowledgements:

We would like to thank Pravesh Kothari, Madhur Tulsiani and Aaron Potechin for various discussions. We thank the anonymous reviewer for pointing out that our particular SoS lower bound application in the regime of poly-logarithmic average-degree can also be obtained from Kim-Vu’s sandwich conjecture, and all reviewers for their helpful suggestions for improving our writing.

DOI:

10.4230/LIPIcs.CCC.2025.11

Event:

40th Computational Complexity Conference (CCC 2025)

Editors:

Srikanth Srinivasan

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

It is well-known in random graph theory that random $d$ -regular graph denoted as $G_{d}(n)$ and Erdős-Rényi random graph $G(n,\frac{d}{n})$ share various phase transition thresholds at least in the leading order, eg. connectivity threshold, independence/chromatic number (see [14] for more examples) . For algorithmists, one intriguing question to ask is whether its algorithmic variant holds: for average-case computational problems (of both algorithms and hardness), can the result and the analysis be transferred from one distribution to another under some general condition? Crucially, this question remains unclear in various situations as analysis of average-case problems (eg. [21, 36, 25] and see more examples in [1]), especially those appealing to a spectral reasoning, is usually brittle in the presence of correlation of the underlying input.

Motivated by the above question, we study the certification question of independent sets in sparse random graphs. In general, a certification question refers to the algorithmic task of finding an efficiently certifiable upper bound on the given input. Via moment methods, the largest independent set have its size tightly concentrated at $\Theta(\frac{n\log d}{d})$ on both distributions of Erdős-Rényi and $d$ -regular. However, on the algorithmic side, the best known algorithm [18] employ spectral techniques, and for both distributions yield a bound of $O(\frac{n}{\sqrt{d}})$ which is essentially off by an $O(\sqrt{d})$ factor from the ground-truth. It is a major open question whether the gap of $O(\sqrt{d})$ may be closed, and the independent set problem has been serving as a prototypical example of information-v.-computation gap in the statistics inference community. In this context, Sum-of-Squares semidefinite programming hierarchy arises as a testbed for algorithmic intractability for average-case problems as the general theory of $\mathsf{NP}$ -hardness does not apply. Capturing spectral techniques that give the sated $O(\frac{n}{\sqrt{d}})$ bound, SDP hierarchy is a natural candidate to turn to for a possibly improved upper bound. The Sum-of-Squares hierarchy of SDP relaxations [33, 38] is a hierarchy of increasingly powerful families parameterized by the SoS-degree: it captures the best known algorithms for many worst-case combinatorial optimization problems [16] and yield improved and even optimal algorithms for statistical inference problems in the average-case setting [17, 21, 34, 40, 30, 20, 27, 19, 2]. As a result of the power of Sum-of-Squares in algorithmic design, establishing lower bounds against it for statistical inference problems has been a major research direction, and such hardness is usually seen as strong evidence for algorithmic intractability.

Starting from the seminal work of [6] that resolves the planted clique problem within the Sum-of-Sqaures framework in the last decade, there is a line of work that continues to investigate the limit of these algorithms on random graphs [35, 39, 37, 24, 26, 29]: specifically, our work is directly inspired by [24, 29] that study the independent set problem on $G(n,\frac{d}{n})$ , and a concrete question we ask is whether one can switch Sum-of-Squares lower bounds from Erdős-Rényi to random regular graphs.

The particular aforementioned results do not extend to the $d$ -regular graph setting and it is cast as an explicit open question whether one may obtain similar results in $G_{d}(n)$ . Despite several results for basic SDP on random $d$ -regular graphs [4, 12] and such results being anticipated given the results on Erdős-Rényi, not much is known for higher degree Sum-of-Squares in the regular graph setting (beyond degree- $4$ ). In fact, it was far from clear prior to this work how existing techniques from the i.i.d. setting may translate for the regular graph distribution, and what kind of new technical obstacles may arise. For example, it takes considerably technical efforts to improve the original result of [6] to satisfy the clique-size constraint exactly [37], and it is conceivable that similar challenges may appear for the regular graph setting.

From this perspective, our work completes the missing piece in the paradigm of Sum-of-Squares hardness by extending its coverage to random regular graphs, and develops tools to enable a smooth transfer within the known framework for applications in contexts beyond max independent set. In particular, we believe our norm bound result would also enable a smooth transfer for applications outside Sum-of-Squares lower bounds by considering spectral algorithms for average-case problems, and we leave this direction for future work.

Works for Low-Degree Polynomial Hardness and Level- $2$ Local Statistics

Closely related to works in Sum-of-Squares lower bounds, low-degree polynomial framework is also another active platform for examining average-case hardness [31, 48, 44, 15, 42, 28]. Random regular graphs have been investigated in this model [3], however, as far as we understand, a general theory for regular instances in the low-degree framework remains mostly at large due to the absence of an explicit orthogonal basis. That said, the recent work of [32] considers a close variant of our problem in the local statistics hierarchy of degree $LoSt(2,D)$ , and asks explicitly for results of hierarchy of higher degree $L o S t$ in regular graphs. On a high level, the local-statistics hierarchy may be viewed as an adaptation of Sum-of-Squares hierarchy to distinguishing problems, and $LoSt(2,D)$ may be seen as a hybrid of hardness against degree- $D$ polynomials and the basic SDP (which is itself captured by degree- $2$ SoS). Our result addresses their question in the context of independence number.

Previous Works for Graph Matrix Norm Bounds

The notion of graph matrix is first formally coined in [5] where its norm bounds are given in [5] and generalized in [1] for the dense setting for random variables with bounded Orlicz norm. In the sparse random graph setting, for random graphs of average degree at least $\operatorname{polylog}(n)$ , rough norm bounds are studied in [24] and [41, 47]. More recently, the previous work [29] optimizes the subpolynomial dependence of the norm bounds which are crucial for the sparse setting, and gives almost tight bounds in the setting of bounded average degree. Our work showcases the versatility of the framework in [29] by adapting it to the regular graph setting. We believe that following our analysis here, a careful combination of some analog of the main lemma from [43] in the sparse regime (implicit in [7]) and [29] would yield norm bounds for the sparse regime for $d=O(1)$ (albeit in a slightly different model for random regular graphs), and we leave this for future work.

Distribution of Random $𝒅$ -Regular Graphs $G_{d}(n)$

The spectrum and the spectral norm of random regular graph is an important topic in random matrix theory, and there have been a long line of works spanning over decades (eg. [18, 10, 13, 46, 9, 45, 8, 23, 11] and we refer reader to see references therein). Before we dive into technical analysis for Sum-of-Squares, let us first make clear the specific distribution of random regular graphs $G_{d}(n)$ that we are working with throughout this work. We start by considering the set of all graphs on $n$ vertices such that each vertex has degree $d$ . Since such set is non-empty whenever $n d$ is even and $0<d<n$ , we may then impose a uniform measure on this set, and define $G_{d}(n)$ the uniform distribution of graphs drawn from this set.

Our choice of distribution is slightly different from the usual choices of configuration/lifting model studied in the previous works for low-degree polynomial analysis. Interestingly, these two alternatives are usually used for the ease of moment calculation as it is possible to employ direct probabilistic calculations in these models. However, we believe such distinction is rather technical and should not be conceptually significant: both distributions are both contiguous to the uniform distribution of random $d$ -regular graphs. In fact, our specific choice is picked so that we may adopt the moment calculation from previous works in a blackbox manner, while we believe similar calculation on either model is true, and can be extracted so that our results for norm bounds may be plugged in mechanically again. That said, to keep the presentation of our work concise, and to maintain the focus on our switching analysis, we opt to restrict our attention to the distribution $G_{d}(n)$ .

1.1 Informal Statement of Our Results

We now give a quick overview and an informal statement of results. We give matrix norm bounds for random $d$ -regular graphs. The results are two-fold.

On the one hand, we identify the “crucial” combinatorial structure of the underlying shape that dictates whether the input distribution of Erdős-Rényi matters, i.e., when the same norm bound holds on both distributions. On the other hand, we identify the tight (up to lower order dependence) dependence of graph matrix norm bound for shapes that have different spectral norm upper bounds in these two distributions.

Theorem 1 (Informal of Theorem 15).

For shapes $\tau$ that do not have any edge “floating”, i.e., edge-component not connected to the left/right matrix boundary , the same graph matrix norm bound (in [24]) for Erdős-Rényi continues to hold with high probability for the random $d$ -regular graph distribution $G_{d}(n)$ .

For shapes $\tau$ that have some floating component that is additionally tree-like, the graph matrix norm bounds for Erdős-Rényi no longer hold in $G_{d}(n)$ , and our norm bound for $G_{d}(n)$ gives a $\sqrt{n}$ factor blow-up over the prior norm bound is for each such component .

For our application, we observe that it suffices for us to focus on shapes in the first category that enjoy similar norm bounds as in the i.i.d. setting (precisely those that do not have any floating component) for the analysis of higher-degree Sum-of-Squares, and therefore we can essentially plug in the new norm bound to the existing SoS analysis. To motivate our results, it is most helpful for us to recap the SoS formulation for the independent set problem and recap the previous result for Erdos-Renyi random graph.

Definition 2 (Pseudo-expectation of degree $\mathsf{dsos}$ ).

For any $\mathsf{dsos}\in\mathbb{N}$ , a degree- $\mathsf{dsos}$ pseudoexpectation in variables $x=(x_{1},x_{2},\dots,x_{n})$ (denoted by $\widetilde{\mathbb{E}}$ ) is a linear map that that assigns a real number to every polynomial $f$ of degree $<d$ in x and satisfies: 1) normalization: $\widetilde{\mathbb{E}}[1]=1$ , and, 2) positivity: $\widetilde{\mathbb{E}}[f^{2}]=0$ for every polynomial $f$ with degree at most $\mathsf{dsos}$ . For any polynomial $g(x)$ , a pseudoexpectation satisfies a constraint $g=0$ if $\widetilde{\mathbb{E}}[f\cdot g]=0$ for all polynomials $f$ of degree at most $\mathsf{dsos}-deg(g)$ .

Definition 3 (Axioms for independent set).

Let $G$ be a n-vertex graph. The following axioms describe the $0-1$ indicators $x$ of independent sets in G:

	$\displaystyle\forall i\in[n],x_{i}^{2}=x_{i}\hskip 12.0pt\text{(Booleanity);}$
	$\displaystyle\forall(i,j)\in E(G),x_{i}x_{j}=0\hskip 12.0pt\text{(Independent % set) }\,.$

Working with the above set-up, the existing result reads as the following,

Theorem 4 ([24]).

With high probability over $G$ sampled from $G(n,\frac{d}{n})$ , there is an absolute constant $c_{0}\in\mathbb{N}$ such that for sufficiently large $n\in\mathbb{N}$ and $d\in[(\log n)^{2},n^{0.5}]$ , and parameters $k$ , $\mathsf{dsos}$ satisfying

k\leq\frac{n}{\sqrt{d}}\cdot\frac{1}{\mathsf{dsos}^{c_{0}}\cdot\log n}\,,

there is a pseudo-expectation of degree $\mathsf{dsos}$ for independent set with objective value

\widetilde{\mathbb{E}}[\sum_{i\in[n]}x_{i}]\geq(1-o(1))k\,.

We are now ready to introduce our main result of switching the input distributions, which states the main result of Theorem 4 holds with essentially the same parameter for inputs from $G_{d}(n)$ (up to lower order dependence of $\mathsf{dsos}$ ).

Theorem 5 (Switching to Lower bounds for $G_{d}(n)$ ).

With high probability over $G$ sampled from the regular graph distribution $G_{d}(n)$ , there is an absolute constant $c_{1}\in\mathbb{N}$ such that for sufficiently large $n\in\mathbb{N}$ and $d\in[(\log n)^{2},n^{0.5}]$ , there is a pseudo-expectation of degree $\mathsf{dsos}<d^{1/10}$ for independent set with objective value

\widetilde{\mathbb{E}}[\sum_{i\in[n]}x_{i}]\geq(1-o(1))k\,.

for

k\leq\frac{n}{\sqrt{d}}\cdot\frac{1}{\mathsf{dsos}^{c_{1}}\log n}\,.

Verbatim, our result for the regular graph distribution may seem to require an extra assumption of $\mathsf{dsos}<d^{1/10}$ , however, we point out that produces makes minimal effect to the strength of our lower bounds in comparison the i.i.d. one as it is offset by the implicit $\operatorname{poly}(\mathsf{dsos})$ dependence of the objective value. In other words, the extra assumption can be dropped taking a slightly larger constant $c_{1}>c_{0}$ for $c_{0}$ promised in the i.i.d. bound and set the objective value to be marginally smaller by $\operatorname{poly}\mathsf{dsos}$ factor.

2 Graph Matrix Norm Bounds for Random Regular Graphs

In this section, we describe our key technical ingredient, graph matrix norm bounds for random regular graphs. Even in the i.i.d. setting, the usual challenge of analyzing spectral norm bounds for graph matrix is the dependence of entries as a graph matrix of dimension $N\times N$ typically has entries given by polynomial functions of $N^{o(1)}$ bits of independent underlying randomness. In the regular graph setting, the $N^{o(1)}$ bits of underlying randomness are further correlated with each other. The further correlation poses challenge to the previous methods of analyzing graph matrix norm bounds via trace moment method, and our main contribution is to build upon previous known techniques for the i.i.d. setting, and to handle the correlation posed by regularity.

2.1 Preliminaries of Graph Matrix

Let us now start with the formal definition of graph matrix. Usually in the case of i.i.d. input, graph matrix is defined using the corresponding orthogonal basis for the null distribution, which is the $p$ -biased basis for the Erdos-Renyi distribution $G(n,\frac{d}{n})$ . The specific basis is defined using the following Fourier characters,

Definition 6 (Fourier character for $G(n,\frac{d}{n})$ ).

Let $\chi$ denote the $p$ -biased Fourier character, we have

\chi(1)=\sqrt{\frac{1-p}{p}}\approx\sqrt{\frac{n}{d}}\,,

and

\chi(0)=-\sqrt{\frac{p}{1-p}}\approx-\sqrt{\frac{d}{n}}\,.

For a subset of edges $S\subseteq\binom{n}{2}$ , we denote its corresponding basis element as $\chi_{S}(G)=\prod_{e\in S}\chi_{e}(G)$ . Throughout this work, we use $p$ and $\frac{d}{n}$ interchangeably unless otherwise specified.

To see that this forms the an orthogonal basis for Erdős-Rényi $G(n,\frac{d}{n})$ , it is straightforward to verify that each edge is independent of each other, and each edge character has mean $0$ and variance $1$ . In this work, even though we are working with input coming random $d$ -regular graph, we define the underlying edge-character as the above Fourier character for Erdős-Rényi graph of $G(n,\frac{d}{n})$ . Crucially, we want to point out that that the edge characters are no longer, even though close to being, orthogonal. From this point on, we will use $G$ to refer to the graph input in general, and as we use the same edge character, we shall not make the distinction of the distribution from which $G$ is sampled.

Next, we are ready to introduce shape, a representation of structured matrices whose entires are polynomial functions of the underlying graph input $G$ .

Definition 7 (Shape).

A shape $\tau$ is a graph on vertices $V(\tau)$ with (possibly multi-)edges $E(\tau)$ and two ordered tuples of vertices $U_{\tau}$ (left boundary) and $V_{\tau}$ (right-boundary). We denote a shape $\tau$ by $(V(\tau),E(\tau),U_{\tau},V_{\tau})$ .

We remind the reader that $V_{\tau}$ should be distinguished from $V(\tau)$ , where $V_{\tau}$ is the right boundary set, while $V(\tau)$ is the set of all vertices in the graph.

Definition 8 (Shape transpose).

For each shape $\tau$ , we use $\tau^{T}$ to denote the shape obtained by flipping the boundary $U_{\tau}$ and $V_{\tau}$ labels. In other words, $\tau^{T}=(V(\tau),E(\tau),U_{\tau^{T}}=V_{\tau},V_{\tau^{T}}=U_{\tau})$ .

Definition 9 (Embedding).

Given an underlying random graph sample $G$ , a shape $\alpha$ and an injective function $\psi(\alpha):V(\alpha)\to[n],$ we define $M_{\psi(\alpha)}$ to be the matrix of size $\frac{n!}{(n-|U_{\alpha}|)!}\times\frac{n!}{(n-|V_{\alpha}|)!}$ with rows and columns indexed by ordered tuples of $[n]$ of size $|U_{\alpha}|$ and $|V_{\alpha}|$ with a single nonzero entry

M_{\psi(\alpha)}[\psi(U_{\alpha}),\psi(V_{\alpha})]=\prod_{(i,j)\in E(\alpha)}% \chi_{G}\left(\psi(i),\psi(j)\right).

and $0$ everywhere else.

Definition 10 (Graph matrix of a shape).

For a shape $\alpha$ , the graph matrix $M_{\alpha}$ is

M_{\alpha}=\displaystyle\sum_{\text{injective }\psi:V(\alpha)\to[n]}M_{\psi(% \alpha)}.

When analyzing the Sum of Squares hierarchy, we extend $M_{\alpha}$ to have rows and columns indexed by all tuples of vertices of size at most $\frac{\mathsf{dsos}}{2}$ by filling in the remaining entries with $0$ .

In words, for a graph matrix of shape $\tau$ , its entry of $M_{\tau}[S,T]$ for set $S, T$ agreeing with the boundary condition of $\tau$ is given by the summation over the injective labeling of middle vertices in $V(\tau)\setminus U_{\tau}\cup V_{\tau}$ .

(a) Line Graph.

(b) Z-shape.

Take the following two diagrams for example. The first diagram is the usual adjacency matrix in the $p$ -biased basis (with diagonal removed), and has entries $M_{\text{line}}[i,j]=\chi_{G}(\{i,j\})$ where we remind the reader for $\chi_{G}(\{i,j\})$ is the $p=\frac{d}{n}$ -biased character. The second diagram is a more interesting example of graph matrix with non-trivial correlations across the entries: it corresponds to a matrix of dimension $n(n-1)\times n(n-1)$ and has entries $M_{Z}[(a,b),(c,d)]=\sum_{t\notin\{a,b,c,d\}}\chi_{G}(\{a,b\})\cdot\chi_{G}(\{b% ,t\})\cdot\chi_{G}(\{c,t\})\cdot\chi_{G}(\{c,d\})$ . Both matrices have $0$ at the undefined entries.

Before we state our main result for graph matrix norm bounds, we make one further definition for graph matrix that will crucially reflect the difference of norm bounds for the i.i.d. distribution and for the regular graphs.

Definition 11 (Isolated vertex).

For a shape $\tau$ and a vertex $v\in V(\tau)\setminus U_{\tau}\cup V_{\tau}$ , we call it isolated if it is not incident to any edge. However, vertices in $U_{\tau}\cup V_{\tau}$ are never considered isolated.

Definition 12 (Floating component).

For a shape $\tau$ , and an connected component $C$ induced by edges, we call $C$ floating if there is no path from $C$ to $U_{\tau}\cup V_{\alpha}$ .

See the following for example of floating component. This is an $n\times n$ graph matrix of entries $M[i,j]=\chi_{G}(\{i,j\})\cdot(\sum_{\{a,b\}\cap\{i,j\}=\emptyset,a\neq b}\chi_% {G}(\{a,b\})$ . We call the edge $\{a,b\}$ floating in this shape as it is not connected to neither left nor right boundary.

Figure 2: Floating Component.

Importantly, observe that an isolated vertex of degree $0$ in $V(\alpha)\setminus U_{\alpha}\cup V_{\alpha}$ is not floating as we consider edge-induced component in the above definition. Finally, we make clear of the definition of a component being tree-like even though it may already be clear as its name suggests,

Definition 13 (Tree-like component).

We call a connected component $C$ with vertices $V(C)$ and edges $E(C)$ tree-like if $V(C)=E(C)+1$ . In other words, there is no cycle in the connected component.

2.2 Main Theorems of Graph Matrix Norm Bounds on Random $𝒅$ -Regular Graphs

For some $\delta>0$ and for any shape $\tau$ with $|V(\alpha)|\leq n^{\delta}$ , and $G_{d}(n)$ the distribution of random $d$ -regular graphs and $p=\frac{d}{n}$ , we obtain the following theorems,

Theorem 14 (User-friendly version for shapes without floating component).

For a shape $\tau$ without floating component, we define

B_{q}(\tau)\coloneqq\max_{S:\text{separator for }\tau}(\sqrt{n}\cdot q)^{|V(% \tau)\setminus S|}\cdot\left(\sqrt{\frac{1-p}{p}}\right)^{|E(S)|}\cdot\sqrt{n}% ^{|I(\tau)|}\cdot(c_{\mathsf{norm}})^{|E(\tau)|}

for some constant $c_{\mathsf{norm}},c>0$ and $I(\tau)$ the set of isolated vertices in $\tau$ . For any $\epsilon>0$ , there exists some large enough constant $c>0$ such that for any $q=\Omega(|U_{\tau}||\log^{c}n)$ and $q<\min(d^{1/10},n^{O(\delta)})$ ,

\mathbb{E}_{G\sim G_{d}(n)}\left[\Tr((M_{\tau}M_{\tau}^{\top})^{q})\right]\leq% \left((1+\epsilon)\cdot B_{q}(\tau)\right)^{2q}

Theorem 15 (Full version for shapes containing floating component).

For a shape $\tau$ possibly containing floating components, we define

\mathsf{float}(\tau\setminus S)=\prod_{C_{i}:\text{ floating component not % connected to }S}\sqrt{n}\cdot 1[C_{i}\text{ is tree-like}]\,,

for any $S\subseteq V(\tau)$ where $1[C_{i}\text{ is tree-like}]$ is the indicator for whether edge-induced component $C_{i}$ is tree-like, and define

\displaystyle B_{q}(\tau)\coloneqq\max_{S:\text{separator for }\tau}(\sqrt{n}% \cdot q)^{|V(\tau)\setminus S|}\cdot\left(\sqrt{\frac{1-p}{p}}\right)^{|E(S)|}% \cdot\sqrt{n}^{|I(\tau)|}\cdot\mathsf{float}(\tau\setminus S)\cdot(c_{\mathsf{% norm}})^{|E(\tau)|}

for some constant $c_{\mathsf{norm}},c>0$ and $I(\tau)$ the set of isolated vertices in $\tau$ . For any $\epsilon>0$ and for any $q=\Omega(|U_{\tau}|\log^{c}n)$ and $q<\min(d^{1/10},n^{O(\delta)})$ ,

\mathbb{E}_{G\sim G_{d}(n)}\left[\Tr((M_{\tau}M_{\tau}^{\top})^{q})\right]\leq% \left((1+\epsilon)\cdot B_{q}(\tau)\right)^{2q}

Let us now unpack the above norm bounds for clarity. Towards the end, we recall the norm bound from [24] for the i.i.d. setting as

\tilde{O}(\max_{S:\text{separator}}\sqrt{n}^{|V(\tau)\setminus S|}\cdot\sqrt{n% }^{|I(\tau)|}\cdot\sqrt{\frac{1-p}{p}}^{|E(S)|})

The main difference between the norm bound for shape with and without floating component is the extra factor captured by $\mathsf{float}(\tau\setminus S)$ , that is each tree-like floating component disconnected from the separator $S$ requires an extra factor of $\sqrt{n}$ in the candidate upper bound. Despite the difference incurred by floating component, the candidate bound stated above are essentially identical as that for the i.i.d. setting in [24] up to subpolynomial dependence.

As a corollary, we obtain the following matrix norm bound that holds with probability at least $1-o_{n}(1)$ , $\|M_{\tau}\|\leq(1+o_{n}(1))\cdot B_{q}(\tau)$ .

2.3 Trace Moment Method and Block-Value Bound

Spectral Norm Bound from Trace Moment Method

Our proof proceeds by analyzing trace moments of matrices using that for any $A$ , the spectral norm $\|A\|_{spec}\leq\tr((AA^{\top})^{q})^{1/2q}$ . Taking $q$ to be logarithmic in the dimension of $A$ suffices to get a bound on $\|A\|$ sharp up to $1+\delta$ for an arbitrarily small $\delta>0$ . Throughout this work, unless otherwise specified, for a matrix $A$ , we denote its spectral norm by $\|A\|\coloneqq\|A\|_{\text{spec}}$ . Expanding the trace power for a graph matrix $M_{\tau}$ gives

\displaystyle\tr((M_{\tau}M_{\tau}^{\top})^{q})

\displaystyle=\sum_{\begin{subarray}{c}P:\text{a shape-walk of length }q\\ P=\{S_{1},T_{1},S_{2},\dots,S_{q-1},T_{q-1}\}\\ S_{i}:\text{labeling of left boundaries of $\tau$}\\ T_{i}:\text{labeling of right boundaries of $\tau$}\end{subarray}}M_{\tau}[S_{% 1},T_{1}]M_{\tau}^{\top}[T_{1},S_{2}]\dots M^{\top}[T_{q-1},S_{q}=S_{1}]\,.

We can now adopt a combinatorial perspective. The trace power is expanded as a sum of weighted walks of length $2q$ over the entries of $M_{\tau}$ , and each walk can be viewed as graph consisting of $q$ blocks of $\tau$ and $\tau^{T}$ . Each term in the expansion of $\tr((M_{\tau}M_{\tau}^{\top})^{q})$ corresponds to a labeling of the vertices in $q$ copies of $\tau$ and $\tau^{\top}$ with labels from $[n]$ (i.e, vertices of the graph $G$ ) satisfying some additional constraints that correspond to a valid walk. The following definition captures these constraints.

Definition 16 (Shape walk and its valid labelings).

Let $\tau$ be a shape and $q\in\mathbb{N}$ . For each walk $P$ , let $G_{P}(\alpha,2q)$ be the shape-walk graph of the shape-walk $P$ vertices on vertices $V_{P}(\tau,2q)$ formed by the following process,

1.

Take $q$ copies of $\tau_{1},\dots,\tau_{q}$ of $\tau$ , and $q$ copies of $\tau_{1}^{\top},\dots,\tau_{q}^{\top}$ of $\tau^{\top}$ ;
2.

For each copy of $\tau_{i}$ (and $\tau_{i}^{T}$ ), we associate it with a labeling, i.e., an injective map $\psi_{i}:V(\tau)\rightarrow[n]$ (and respectively $\psi_{i}^{\prime}$ for $\tau^{\top}$ );
3.

For each $i\in[q]$ , we require the boundary labels to be consistent as ordered tuples, i.e. $\psi_{i}(U_{\tau})=\psi^{\prime}_{i-1}(V_{\tau})$ and $\psi^{\prime}_{i}(U_{\tau^{\top}})=\psi_{i}(V_{\tau_{i}})$ ;
4.

Additionally, each such walk must be closed, i.e., $\psi^{\prime}_{q}(V_{\tau^{\top}})=\psi_{1}(U_{\tau})$ as a tuple-equality;
5.

We call each $\tau_{i}$ and $\tau^{\top}_{i}$ block a BlockStep in the walk.

For each walk-graph , we associate it with a natural decomposition $P=\psi_{1}\circ\psi_{1}^{\prime}\circ\psi_{2}\circ\dots\circ\psi_{q}\circ\psi_% {q}^{\prime}$ .

Moreover, we let $E(P)$ be the set of edges used in the labeled walk $P$ . Before we proceed further, we would like remind the reader not to confuse vertices/edges in the walk with vertices/edges in the shape. The vertices in a walk are “labeled” by elements in $[n]$ . Similarly, each edge $e\in E(P)$ in a walk is labeled by an element in $\binom{n}{2}$ . We will use the terms “labeled vertex” and “labeled edge” unless it is clear from context.

Throughout our work, we require spectral norm bounds on random matrix that holds with probability at least $1-o(1)$ , and this is further accomplished by bounding the expectation of the above trace quantity and a simple application of Markov’s inequality. Taking the expectation over the randomness of the underlying input $G$ , and reorganizing the terms on the righthand side by grouping steps by their underlying labeled-edge, we can write the expected trace as

	$\displaystyle\mathbb{E}_{G}\tr((M_{\tau}M_{\tau}^{\top})^{q})$	$\displaystyle=\mathbb{E}_{G}\sum_{\begin{subarray}{c}S_{1},T_{1},S_{2},\dots,S% _{q-1},T_{q-1}\\ S_{i}:\text{labeling of left boundaries of $\tau$}\\ T_{i}:\text{labeling of right boundaries of $\tau$}\end{subarray}}M_{\tau}[S_{% 1},T_{1}]M_{\tau}^{\top}[T_{1},S_{2}]\dots M_{\tau}^{\top}[T_{q-1},S_{1}]$
		$\displaystyle=\mathbb{E}_{G}\sum_{\begin{subarray}{c}P\\ \text{shape-walk of length }q\end{subarray}}\prod_{e\in E(P)}\chi_{G}(e)^{% \text{mul}_{P}(e)}$

where we use $\text{mul}_{P}(e)$ to denote the multiplicity of labeled-edge $e$ in the walk $P$ . In the i.i.d. setting, the above quantity further factorizes over edges as

\mathbb{E}_{G}\sum_{\begin{subarray}{c}P\\ \text{shape-walk of length }q\end{subarray}}\prod_{e\in E(P)}\chi_{G}(e)^{% \text{mul}_{P}(e)}=\sum_{\begin{subarray}{c}P\\ \text{shape-walk of length}q\end{subarray}}\prod_{e\in E(P)}\mathbb{E}_{G}[% \chi_{G}(e)^{\text{mul}_{P}(e)}]\,,

and a crucial observation at this point is that for each walk to give non-zero contribution, each labeled edge needs to appear in at least two steps, as otherwise the expectation of the walk factorizes over the edges and edges appearing a single time gives mean $0$ .

Noting that such immediate factorization is not true in our setting of random regular graphs, however, we will proceed with the i.i.d. setting to describe the machinery of obtaining matrix norm bound from block-value bound from [1, 24, 22, 29] , and then outline challenges and solution posed by regularity in the subsequent section.

In particular, our norm bound techniques may be viewed as a showcase for the versatility of the machinery developed in [29] with simplification as we do not optimize over polylog dependence which is the main target of their work, and with adaptation to random regular graphs.

Spectral Norm Bound from Block Value Bound

Noting that the expected trace is a weighted count of walks, trace moment methods for random matrix, in particular adjacency matrix and its variants, usually proceed in a global fashion by analyzing the global constraints of the walks (eg. each edge needs to appear twice) via an encoding argument and then carefully analyzing the combinatorial factors therein. However, as noted in previous works, such analysis may easily become overwhelming if applied for non-trivial graph matrices.

To handle the potential complication from a global analysis, the machinery of block value bound proposes to find a local bound that holds for each step of the walk, or more concretely when applied for graph matrix, for each BlockStep of a shape walk. For starters, one may first unpack the expected trace, and observe that there are two kind of factors contributing to the final expected trace,

1.

Vertex Factor: the combinatorial “counting” factor that specifies each step of the walk;
2.

Edge Value: the analytical factor from edges (the underlying randomness) which corresponds to the term $\mathbb{E}\prod_{e\in E(P)}\chi_{G}(e)^{\text{mul}_{P}(e)}$ .

To be concrete, one may think of the vertex factor as the factor needed for the decoder to identify the walk in the usual encoder-decoder setting. For example, a typical vertex requires a cost of $[n]$ if it is the first time it appears in the walk as there are $n$ possible choices for the vertex label. Within this scheme, the vertex-factors altogether should be sufficient for the decoder to decode the walk, and when combined with the analytic factor from the underlying randomness, gives an upper bound for the desired expected trace.

With these two types of factors in hand, the core message of the machinery is that one can split the factors in an essentially “even” manner so that the global bound reduces to finding a local bound of the BlockStep. In words, for each BlocStep, the machinery demands a factor assignment scheme such that for the candidate upper bound $B(\tau)$ , one can bound the contribution of a given $\text{BlockStep}_{i}$ to the global trace by

\mathsf{vtxcost}(\text{BlockStep}_{i})\cdot\mathsf{edgeval}(\text{BlockStep}_{% i})\leq B(\tau)

on a high level.

The target of the block value machinery is then formally defined as

Definition 17 (Block value bound).

Fix $q\in\mathbb{N}$ and a shape $\tau$ . For any vertex/edge factor assignment scheme, we call $B_{q}(\tau)$ a valid block-value function for $\tau$ of the given factor-assignment scheme if

\mathbb{E}\left[\tr(M_{\tau}M_{\tau}^{\top})^{q}\right]\leq f(\tau)\cdot B_{q}% (\tau)^{2q}

for some auxiliary function $f(\tau)$ s.t. $f(\tau)^{1/2q}=1+o_{n}(1)$ , and for each $\mathsf{BlockStep}_{i}$ throughout the shape walk, the following holds,

\mathsf{vtxcost}(\mathsf{BlockStep}_{i})\cdot\mathsf{edgeval}(\mathsf{% BlockStep}_{i})\leq B_{q}(\tau)

where $\text{vtxcost}(\mathsf{BlockStep}_{i}),\mathsf{edgeval}(\mathsf{BlockStep}_{i})$ are the corresponding vertex-cost and edge-value assigned to $\mathsf{BlockStep}_{i}$ by the given factor-assignment scheme.

$\blacktriangleright$ Remark 18.

To break the assymetry between the first block-step and any subsequent block-step, we take $f(\tau)=O(n^{|U_{\tau}|})$ to capture of identifying the start of the walk, and then walk-value may then be bounded by treating the first block as any subsequent block.

The intended upper bound $B_{q}(\tau)$ in the application may have extra dependence on $q$ on the length of the walk, while this effect only culminates to subpolynomial $\tilde{O}(1)$ factors of our norm and can be ignored for the purpose of our work as we work in the regime of $d>\log^{c}n$ for some absolute constant $c>0$ . We ignore the subscript $q$ in the block-value bound from this point on.

To further enable a local analysis and break correlations across the BlockSteps, we design our factor assignment (for both vertex-cost and edge-value) that only depends on the step-labels of the block. We formally define step-label as the following,

Definition 19 (Step-label and BlockStep-Label).

We label each step (i.e. edge’s multiplicity) as the following,

1.

Singleton Step: For any edge that appears only once throughout the walk, we call this edge/step a singleton step/edge;
2.

F/S Step: For steps along a non-singleton edge (i.e. an edge that appears more than once), and the edge is appearing for the first time in the walk, we call it an $F$ (fresh) step if it leads to a new, unexplored vertex in $[n]$ ;
3.

H Step: For a step along a non-singleton edge that appears for neither the first nor the last time in the walk, we call it an $H$ (high-mul) step;
4.

R Step: For a step along a non-singleton edge that appears for the last time in the walk, we call it an $R$ (Return) step.

A step-labeling for a block-step assigns step-labels for each edge in the block, and can be represented as a function $L:E(\tau)\rightarrow\{F,S,R,H,\text{Singleton}\}$ .

The following proposition shows that we can easily obtain a valid $B_{q}(\tau)$ once we have an appropriate factor assignment scheme.

Proposition 20.

For any graph matrix $M_{\tau}$ and any valid factor assignment scheme, for any step-labeling $L$ of $\tau$ , define

B(L)\coloneqq\mathsf{vtxcost}(L)\cdot\mathsf{edgeval}(L)\,,

then

\displaystyle B_{q}(\tau)\coloneqq\sum_{L:\text{ step-labelings for }E(\tau)}B% (L)=\sum_{L:\text{ step-labelings for }E(\tau)}\mathsf{vtxcost}(L)\cdot\mathsf% {edgeval}(L)

is a valid block-value function for $\tau$ .

Proof.

It is immediate to observe that $B_{q}(\tau)$ defined above is a local bound for each block-step. To see the global upper bound, observe that the trace can be bounded by the matrix dimension (specifying the start of the walk captured by the auxiliary function $f(\tau)$ ) times

	$\displaystyle\sum_{\begin{subarray}{c}L_{1},\dots,L_{2q}:\\ \text{step-labelings for $E(\tau)$}\end{subarray}}\prod_{i=1}^{2q}\mathsf{% vtxcost}(L_{i})\cdot\mathsf{edgeval}(L_{i})$
	$\displaystyle\leq\left(\sum_{L:\text{step-labelings for }E(\tau)}\mathsf{% vtxcost}(L)\cdot\mathsf{edgeval}(L)\right)^{2q}$

$\hfill\blacktriangleleft$

The next step of the Block-Value bound machinery is then to identify a factor-assignment scheme (for both vertex-cost and edge-value) that produces a minimal upper bound of $B(\tau)$ . It should be pointed out the most technical component of the machinery is usually to design the assignment scheme for vertex-costs and carefully analyze the interplay between vertex-cost bound and edge-value bound, while the edge-value scheme is rather immediate in the i.i.d. setting.

However, in our setting of regular graphs, the edge-value component is a major focus of our work as this is where the distinction of the underlying graph distribution kicks in.

2.4 Bounding Walk Value: putting in the regularity

Before we consider how the edge-value may be factorized into each BlockStep, a crucial starting point is to understand what the edge-value bound globally for a whole walk. In particular, we want to find an upper bound of edge-value for $\mathbb{E}_{G\sim G_{d}(n)}\underbrace{\prod_{e\in P}\chi_{G}(e)^{\text{mul}_{% P}(e)}}_{\coloneqq\mathsf{edgeval}_{\text{scaled}}(P)}$ for a “not-too-large” subset of edges $P\subseteq\binom{n}{2}$ with various multiplicities in a random regular graph.

Fortunately, such question is well-understood in the context of random regular graphs, and we use result from the previous work of [43] in the context of the spectral gap for random $d$ -regular graph. Before we state the known result, we first make the following additional definitions,

Definition 21 (Surprise step/visit).

In a shape walk, we call a step a surprise visit if it leads to a vertex that has already been visited/explored in the walk.

Definition 22 (Singleton step/edge).

In a shape walk $P$ , we call a step along labeled edge $e$ (of the underlying randomness) a singleton-edge/step if $e$ appears only once throughout the whole walk.
On the other hand, we call a step using along a labeled edge $e$ that appears more than once a non-singleton step and the underlying edge a non-singleton edge.

We are now ready to recall the previous known bound, which bounds the unscaled value of a walk $P$ of length- $2q$ in a random $d$ -regular as the following.

Lemma 23 (Restated edge-value bound from Corollary 3.6 in [43]).

Let $\log n\ll q\ll d^{1/10}$ , and $d<cn$ for some constant $c>0$ , define

\mathsf{edgeval}_{\text{unscaled}}(P)\coloneqq\prod_{e\in P}\underbrace{(G(e)-% \frac{d}{n})^{\text{mul}_{P}(e)}}_{\text{unscaled character}}\,,

where $G(e)$ is the $0/1$ indicator variable for edge in graph sample $G$ , the following bound holds

	$\displaystyle\|\mathbb{E}_{G\sim G_{d}(n)}\mathsf{edgeval}_{\text{unscaled}}(P)\|$
	$\displaystyle\leq(2+o(1))\cdot(2q)^{2\cdot\|\text{surprise(P)}\|}\cdot(p(1-p)/n)% ^{\|\text{singleton(P)}\|/2}(p(1-p))^{\|\text{NonSingleton}(P)\|}$

where $\text{surprise}(P)$ is the set of surprise visits in the walk $P$ , and $\text{Singleton}(P)$ is the set of singleton edges (i.e., edges that appear only once in the walk), $\text{NonSingleton}(P)$ is the set of edges that appear at least twice, and importantly, $|\text{NonSingleton}(P)|$ denotes the number of such edges (not counting multiplicities).

At this point, we shall emphasize that the most important aspect of the above bound is the factor of $(p(1-p)/n)^{|\text{singleton(P)}|/2}$ which accounts for the change that we are working in a non i.i.d. setting, and each edge appearing only once no longer has zero expected value as in the i.i.d. setting. This lemma does not follow from an immediate magnitude bound, and requires a careful analysis using cancellation of the terms that appear in the moment expansion which is arguably the main technical component of [43]: compared with magnitude bound, it comes with an extra $\frac{1}{\sqrt{n}}$ decay for each singleton edge without which our spectral norm bounds would degrade into a trivial Frobenius norm bound for various shapes.

Before we combine this edge factor with combinatorial counting, let us switch back to the Fourier basis in which edge has their character given, and note that the scaling is picked such that

\mathsf{edgeval}_{\text{scaled}}(P)=\mathsf{edgeval}_{\text{unscaled}}(P)\cdot% \sqrt{\frac{1}{p(1-p)}}^{\text{mul}(P)}

where $\text{mul}(P)\coloneqq\sum_{e\in P}\text{mul}_{P}(e)$ is the total edge multiplicity of walk $P$ , and $\text{mul}_{P}(e)$ is the multiplicity of edge $e$ in $P$ . Combining with the magnitude bound for the unscaled value, we have

	$\displaystyle\left\|\mathbb{E}_{G\sim G_{d}(n)}\mathsf{edgeval}_{\text{scaled}}% (P)\right\|\leq$	$\displaystyle(2+o(1))\cdot(2q)^{2\cdot\|\text{surprise(P)}\|}\cdot(p(1-p)/n)^{\|% \text{singleton(P)}\|/2}$
		$\displaystyle\cdot(p(1-p))^{\|\text{NonSingleton}(P)\|}\cdot\sqrt{\frac{1}{p(1-p% )}}^{\text{mul}(P)}$

With the above bound for the walk value, we arrive at our edge-value assignment scheme that assigns factors from the above upper bound to each edge’s multiplicity in the walk. We follow the notation in previous works and label each edge’s multiplicity (i.e. step) as the following,

At this point, it is crucial for the reader to distinguish a Singleton step and an $S$ step of surprise visit. In fact, we advise for the readers to skip upon $S$ step of surprise visit as they only concern for subpolynomial dependence of the final norm bound which we do not optimize in this work.

Proposition 24.

The following step-value assignment scheme gives an upper bound for the edge-value up to a factor of $O(1)$ :

1.

For singleton step/edge, assign a value of $\sqrt{\frac{p(1-p)}{n}}\cdot\sqrt{\frac{1}{p(1-p)}}=\sqrt{\frac{1}{n}}$ ;
2.

For an $F/S/R$ step of an edge that appears more than once, assign a value of $\sqrt{p(1-p)}\cdot\sqrt{\frac{1}{p(1-p)}}=1$ ;
3.

For an $S$ step, i.e., the underlying edge is non-singleton and appearing for the first time wile the step leads to a visited vertex in the walk, we additionally assign a value of $(2q)^{2}$ . That said, an $S$ step of a surprise visit gets assigned a value of $(2q)^{2}$ in total;
4.

For an $H$ step of an edge that appears more than twice, assign a value of $\sqrt{\frac{1-p}{p}}$ .

Let $f(s)$ be the assigned value of step $s$ in according to the above scheme,

(2+o(1))\prod_{s\in P:\text{step}}|f(s)|\geq|\mathsf{edgeval}_{\text{scaled}}(% P)|

In words, up to the factor of $(2+o(1))$ , the above step-value assignment scheme assigns the upper bound factor of the walk to each step.

Proof.

We first observe that the factor $\sqrt{\frac{1}{p(1-p)}}$ gets assigned to each step regardless of label, which is consistent to the fact that we have $\sqrt{\frac{1}{p(1-p)}}^{\text{mul}(P)}$ in the original upper bound. Additionally, for each edge that appears more than once, we pick up a factor of $p(1-p)$ and this is distributed among the $F//R$ steps of the edge. For edges that appear only once, the whole factor is assigned to the singleton edge. For the factor of $(2q)^{|surprsie(P|)}$ , we assign them to the $S$ -step in which the edge is making the first appearance. $\hfill\blacktriangleleft$

2.5 Bounding Vertex-Factor: as if edges are i.i.d.

For people familiar with the trace-moment method calculation, this is usually the most technical and cumbersome step of most random matrix norm bounds. For this component of our work, we largely draw from prior works [24, 22, 29] for applying the module of assigning vertex-factors while the effect of having singleton edges comes into play later when combined with the edge-value assignment scheme.

Vertex-factor Assignment Scheme

In the case of each edge appearing at least twice for the trace to be non-vanishing, we consider the following vertex-factor assignment scheme.

1.

We assign a factor of $n$ for a vertex making both of its first and last appearance at the same block;
2.

otherwise, we assign a factor of $\sqrt{n\cdot q_{\tau}}\leq\sqrt{n}\cdot q_{\tau}$ for the first and last appearance (where we use a loose bound here for simplicity as we do not optimize the dependence on $q$ );
3.

we assign a factor of $q_{\tau}$ for any of its middle appearance.

Proposition 25 (Vertex-factor assignment scheme).

The above is a sound factor assignment scheme. In other words, let $\mathsf{vtxcost}(P)$ be an upper bound for the vertex-factor of all vertices throughout the walk $P$ ,

\mathsf{vtxcost}(P)\leq\prod_{\begin{subarray}{c}v:\text{vertex }v\\ \text{appearance }i\end{subarray}}|\text{vtxcost}(v,i)|

where $\text{vtxcost}(v,i)$ is the factor assigned by the vertex-factor assignment scheme for vertex $v$ at its $i$ -th appearance.

Proof.

In the case where there is no singleton edge, each vertex needs to appear at least twice. Further, for each vertex that appears more than once in a length- $q_{\tau}\coloneqq 2q|V(\tau)|$ walk, its first appearance requires a cost of $[n]$ and any of its subsequent appearance can be specified at a cost of $q_{\tau}$ . The crux of this scheme is to split the factor of $n\cdot q_{\tau}$ evenly to its first and last appearance, and this proves the factor assignment schemes is a sound upper bound for vertices that do no make first and last appearance in the same block (i.e., a single appearance throughout the walk).

In the case of singleton edges, we note that for vertices arrived by a singleton edge on the $V_{\tau}$ boundary, such vertex continues to make appearance in two blocks and that is still a factor of $\sqrt{n\cdot q_{\tau}}\leq\sqrt{n}\cdot q_{\tau}$ per appearance. For vertices arrived by a singleton edge but in the interior, i.e., $V(\tau)\setminus V_{\tau}$ , we follow the notation that a vertex is allowed to make more a single first/last appearance in the same block. That said, such a vertex may be making its first and last appearance in the same block, and gets assigned a factor of $n\cdot q_{\tau}$ by the previous reasoning. However, notice that for such vertices, a cost of $[n]$ at the first appearance suffices, therefore we can spare a factor of $q_{\tau}$ that is originally intended for its subsequent appearance, and assign a cost of $n$ in total. $\hfill\blacktriangleleft$

2.6 Explicit Application of BlockValue Machinery

In this section, we apply the above machinery to the explicit graph matrices of line graph (see following for diagrams) to familiarize readers with our described scheme, and show one can easily recover the $\tilde{O}(\sqrt{n})$ bound for centered adjacency matrix, which is equivalent to a $\tilde{O}(\sqrt{d})$ bound for the spectral gap of a random graph.

Lemma 26.

For the line-graph $\tau_{line}$ , we have

B(\tau_{line})\leq\tilde{O}(\sqrt{n})\,,

as a corollary, we have $\|M_{line}\|\leq O(\sqrt{n}\operatorname{poly}\log(n))$ w.h.p.

Proof.

We first take $q=\operatorname{polylog}n$ . To apply block-value bound, fix a traversal direction from $U_{\tau}$ to $V_{\tau}$ , and given current boundary at $U_{\tau}$ , we start by casing the step-label. If this is an $F$ -step

1.

$V_{\tau}$ is making a first appearance and a factor of $\sqrt{n}\cdot q$ is assigned;
2.

$U_{\tau}$ is making a middle appearance and at most a cost of $q$ is assigned to the vertex;
3.

The edge is non-singleton and making the first appearance, which gets value $1$ ;
4.

This combines to a value of $\sqrt{n}\cdot q$ in total.

Similarly if this is an $R$ -step,

1.

$V_{\tau}$ is potentially making a last appearance and at most a factor of $\sqrt{n}\cdot q$ is assigned (a factor of $q$ for middle appearance);
2.

$U_{\tau}$ is making a middle appearance and at most a cost of $q$ is assigned to the vertex;
3.

The edge is non-singleton and making the first appearance, which gets value $1$ ;
4.

This combines to a value of $\sqrt{n}\cdot q$ in total.

If this is an $S/H$ -step, we have at most a vertex factor of $q^{2}$ in total, and an edge-value of $1$ or in the case of $H$ -step, a value of $\sqrt{\frac{1-p}{p}}\approx\sqrt{\frac{n}{d}}$ . This gives a total factor of $q^{2}$ and $\sqrt{\frac{1-p}{p}}\cdot q^{2}$ .

Lastly, if this is a singleton-step, we have vertex factor of at most $n$ in total when the left vertex is making a last appearance and the right vertex a first appearance. Crucially, the singleton-step gives a decay of $\frac{1}{\sqrt{n}}$ , and therefore we have a combined bound of $\sqrt{n}$ .

Summing over the above step-labels, we have

B(\tau)\leq 2\cdot\sqrt{n}\cdot q^{2}+q^{2}+\sqrt{\frac{1-p}{p}}\cdot q^{2}+% \sqrt{n}\leq\tilde{O}(\sqrt{n})

as we take $q=\operatorname{poly}\log n$ . $\hfill\blacktriangleleft$

2.7 Connecting back to Vertex Separator

The crucial quantity governing graph matrix norm bounds is the notion of vertex separator, defined as the following,

Definition 27 (Vertex separator).

For a shape $\tau$ , we say $S\subseteq V(\tau)$ is a vertex separator for $\tau$ if any path from $U_{\tau}$ to $V_{\tau}$ passes through some vertex in $S$ .

In the previous analysis, the notion of vertex separator pops up as each edge needs to appear twice in the walk, and therefore, there is always some vertex in a given BlockStep that is making a middle appearance. However, this is no longer true for us as we may non-zero value walk that contain singleton edge and a priori, it is not at all clear whether vertex separator continues to control matrix norm bound in the regular setting.

To relate the block value to vertex separator, we start with a step-labeling of edges in the given block $\tau$ . In fact, we restrict to step-labeling that does not involve singleton-step first. This would enable us to recover the usual graph matrix norm bounds. For concreteness, assume this is an $\tau$ block (as opposed to $\tau^{\top}$ ) and we are traversing from $U_{\tau}$ (left boundary) to $V_{\tau}$ (right boundary). Importantly the vertices in $U_{\tau}$ are already specified for us.

Building the Separator from BlockStep-Labels

For a block of $\tau$ traversing from $U_{\tau}$ and $V_{\tau}$ , and let $L:E(\tau)\rightarrow\{F,R,H,\text{singleton}\}$ be a step-labeling of the given block, we build $S_{B}$ the separator for the given block as the following,

1.

Include any vertex in $U_{\tau}\cap V_{\tau}$ into $S_{B}$ ;
2.

Include any vertex incident to $H$ -step into $S_{B}$ ;
3.

Include any vertex incident to both $F, R$ edges into $S_{B}$ ;
4.

Include any vertex in $U_{\tau}$ incident to some $F/S$ -step (note that $S$ is a surprise step as opposed to a singleton-step) into $S_{B}$ ;
5.

Include any vertex in $V_{\tau}$ incident to some $R$ -step into $S_{B}$ ;
6.

Additionally include any other vertex making middle appearance into $S_{B}$ in the given block.

At this point, it is not clear whether $S_{B}$ built from the above process is a vertex separator for any block-labeling, not to mention whether it governs the matrix norm. In fact, it is possible in our case that $S_{B}$ is not a vertex separator for $\tau$ at all. That said, we first consider the case where there are no singleton-steps, and in this case, one can see the set $S_{B}$ built from above is indeed a vertex separator. This in part explains why matrix norm bounds are connected to vertex separator in the previous works for i.i.d. setting.

Claim 28.

In the absence of singleton-steps, $S_{B}$ is a vertex separator, i.e., any path from $U_{\tau}$ to $V_{\tau}$ passes through some vertex in $S_{B}$ .

Proof.

To show $S_{B}$ is a vertex separator, it suffices for us to show any path from $U_{\tau}$ to $V_{\tau}$ passes through some vertex in $S_{B}$ . Consider any such path, we first observe that if the path is trivial (i.e., no step is involved), such path is blocked by $U_{\tau}\cap V_{\tau}\subseteq S_{B}$ . For the non-trivial path, such path cannot contain any $H$ -step, as any $H$ -step has both its endpoints included in $S_{B}$ , and therefore blocked by the separator. Similarly, since each vertex incident to both $F$ and $R$ -steps are included into the separator, any path from $U_{\tau}$ to $V_{\tau}$ must be of either all $F$ or all $R$ -steps.

In the case of a path being of all $F$ -steps, let $u$ be a vertex in which path intersects $U_{\alpha}$ , this is a $U_{\tau}$ vertex incident to $F$ -step and therefore included into the set $S_{B}$ . Analogously, an all $R$ -step patg passes through some vertex in $V_{\tau}$ incident to an $R$ -step and included into $S_{B}$ . Therefore, any path from $U_{\tau}$ to $V_{\tau}$ passes through the set $S_{B}$ , and $S_{B}$ is indeed a vertex separator. $\hfill\vartriangleleft$ From the above proof, we can also arrive at the following corollary immediately,

Corollary 29.

In the presence of singleton-steps, $S_{B}$ is not necessarily a vertex separator, however, any path not blocked by $S_{B}$ is all-singleton.

Observation 30.

Any vertex included into $S_{B}$ in the above process is a vertex making a middle appearance in the given block.

With the connection between vertex separator and step-labeling established, we are now ready to bound the block-value of a given step-labeling, and see why it is indeed the norm bound given by vertex separator in the previous works.

2.8 Deducing Block-Value from Step-Labeling

In this section, we combine the edge-value assignment scheme and our vertex-factor assignment scheme introduced earlier to bound the block-value of a given step-labeling . On a high-level, we first consider the case where there is no singleton-edge, and show in this case we recover the usual graph matrix norm bounds.

However, as we show in the last section, a step-labeling in the presence of singleton-edges is not necessarily a vertex separator, therefore it is not quite sufficient to consider step-labeling free of singleton-step. To handle such discrepancy, we show that any step-labeling $L$ with singleton-step, we can construct an alternative BlockStep-labeling $L^{\prime}$ that is singleton-step free, and furthermore we have the BlockValue bound $B(L)\leq B(L^{\prime})$ . Therefore, we show that for the sake of maximizer of the block-value (and thereby of the matrix norm bound), it suffices for us to consider $L$ that is free of singleton-step, and for these step-labelings, we have a “genuine” vertex-separator as usual.

Lemma 31.

For a shape $\tau$ , for any step-labeling $L$ of $\tau$ that does not contain singleton-step, let $S$ be its associated vertex separator built from the prescribed process, we can bound its block-value by

	$\displaystyle B(L)$	$\displaystyle\coloneqq\mathsf{vtxcost}(L)\cdot\mathsf{edgeval}(L)$
		$\displaystyle\leq(\sqrt{n}\cdot q_{\tau})^{\|V(\tau))\setminus S\|}\cdot\sqrt{% \frac{1-p}{p}}^{\|E(S)\|}\cdot\sqrt{n}^{\|I(\tau)\|}\cdot q_{\tau}^{\|V(S)\setminus U% _{\tau}\cap V_{\tau}\|}\cdot\max(1,q_{\tau}^{\|E(\tau)\setminus E(S)\|-\|V(\tau)% \setminus V(S)\|})$

With some abuse of notation, we also write $B(S)\coloneqq B(L)$ defined as above as we observe the RHS quantity only has dependence on $L$ through $S$ .

Proof.

The bound follows from observing the following,

1.

By our vertex factor assignment scheme, any vertex outside the separator is making a first or last appearance in this block but not both since $L$ is free of singleton-step, and gets assigned a vertex cost of $\sqrt{nq_{\tau}}\leq\sqrt{n}\cdot q_{\tau}$ ;
2.

Any $H$ edge gets assigned an edge-value of $\sqrt{\frac{1}{p(1-p)}}\approx\sqrt{\frac{n}{d}}$ , and any such edge is inside the separator, therefore, we have at most a factor of $\sqrt{\frac{n}{d}}^{|E(S)|}$ in total;
3.

Any excess edge gets assigned a factor of $q_{\tau}$ in its $F/R$ -step, therefore we have a factor of $q_{\tau}^{|E(\tau)\setminus E(S)|-|V(\tau)\setminus S|}$ in total;
4.

Any vertex inside the separator other than $|U_{\tau}\cap V_{\tau}|$ is making a middle appearance and gives a factor of $q_{\tau}$ , where we notice that a factor is spared for $|U_{\tau}\cap V_{\tau}|$ as no encoding is needed for such vertices.

$\hfill\blacktriangleleft$

Lemma 32.

For a shape $\tau$ , for any of its step-labeling $L$ that contains singleton-step, if $\tau$ does not contain any floating component, there exists a separator $S$ whose corresponding block-value bound that at least matches the block-value bound of $L$ . In other words, there exists vertex separator $S$ such that

B(L)\leq B(S)=(\sqrt{n}\cdot q_{\tau})^{|V(L)\setminus S|}\cdot\sqrt{\frac{1-p% }{p}}^{|E(S)|}\cdot q_{\tau}^{|V(S)\setminus U_{\tau}\cap V_{\tau}|}\cdot\max(% 1,q_{\tau}^{|E(\tau)\setminus E(S)|-|V(\tau)\setminus V(S)|})

Proof.

For starters, notice that our block-value bound factorizes over connected component, and it suffices for us to consider a single connected component. We first observe given a step-labeling, we can decompose $\tau$ into singleton-components by only considering singleton-step edges in $\tau$ .

We now case on whether $S(L)$ , the candidate vertex separator built from $L$ containing singleton-step, is a vertex-separator for $L$ . If so, it suffices for us to verify our previous bound of

B(L)\leq(\sqrt{n}\cdot q_{\tau})^{|V(L)\setminus S|}\cdot\sqrt{\frac{1-p}{p}}^% {|E(S)|}\cdot q_{\tau}^{|V(S)\setminus U_{\tau}\cap V_{\tau}|}\cdot\max(1,q_{% \tau}^{|E(\tau)\setminus E(S)|-|V(\tau)\setminus V(S)|})

continues to hold for the given block when we take $S=S(L)$ even in the presence of singleton-step. To see this, notice the previous argument bounding vertex factors in identical way for vertices outside the separator that are not making both first and last appearances, and therefore, it suffices for us to focus on the “new” vertices making both first and last appearance due to the non-repetitiveness of singleton-edges. Any such vertex is a non-isolated vertex (otherwise if isolated, its double factor has already been accounted for in the previous proof by the factor of $\sqrt{n}^{|I(\tau))|}$ ), and each such vertex gives an extra factor of $\sqrt{n}$ . Call such vertex a flip vertex, and unflipped otherwise. That said, we can restrict our attention to these vertices and note that are all incident to some singleton edge that comes with an extra $\frac{1}{\sqrt{n}}$ decay. Therefore, the task is to assign a singleton edge for each such vertex that is making both first and last appearance in the block.

Consider the graph induced by singleton edges, we observe that any flipped vertex has a path of singleton edges to an unflipped vertex in the case there is no floating component since it has a path to $U_{\alpha}\cup V_{\alpha}$ . Therefore we may consider a BFS to traverse flipped vertex from some unflipped vertex via singleton edges, and assign the singleton edge to the vertex it leads to, and observe that

1.

Each singleton edge, if non-excess, comes with a value $\frac{1}{\sqrt{n}}$ and gets assigned to the destination vertex, which is indeed the target we start off with;
2.

Otherwise, if an excess edge (i.e. a singleton edge that is also a surprise step leading to visited vertex), we incur $q^{O(1)}$ factor but it has an unassigned $\frac{1}{\sqrt{n}}$ factor as there must be at least another edge that is assigned to the destination vertex: if the vertex makes first appearance in the block, either it is not flipped and an extra $\sqrt{n}$ factor is not needed , or it is a flipped vertex but the extra $\sqrt{n}$ factor has been offset by the first singleton step that explores it ,

and this completes the proof for the case $S(L)$ remains as a separator for $\tau$ .

On the other hand, if $S(L)$ is not a separator for $\tau$ , it suffices for us to construct a separator $S$ and go through the above argument to show the desired block value bound of $B(L)\leq B(S)$ . Towards this end, observe that there must be a path from $U_{\tau}$ to $V_{\tau}$ that does not intersect $S(L)$ . By our construction of $S(L)$ , any such path must be all singleton-step. Consider all such singleton-paths from $U_{\tau}$ to $V_{\tau}$ and let the union of all such paths be $T$ . Let $X$ be the MVS for $T$ and now we consider $S\coloneqq S(L)\cup X$ as the new candidate vertex separator.

Observe that $S=S(L)\cup X$ is indeed a vertex separator now as any path not blocked by $S(L)$ is in $T$ while any such path in $T$ from $U_{\tau}$ to $V_{\tau}$ is blocked by $X$ . It now remains to verify the block S value of $S$ upper bounds the BlockValue of $L$ .

Note that as the block-value bound factorizes over connected components, the factors of vertices/edges connected to $S(L)$ can be bounded by the previous argument, it suffices for us to focus on factors on the singleton path from $U_{\tau}$ to $V_{\tau}$ . Towards this end, we first consider a BFS from $X$ using the singleton-step in $L$ to keep track of the change of factors in the BlockValue due to the addition of $X$ .

1.

We start by observing for any vertex in $X$ , it may either come from $U_{\tau}\Delta V_{\tau}$ , or it is outside $U_{\tau}\cup V_{\tau}$ . Any such vertex cannot be in $U_{\tau}\cap V_{\tau}$ since such vertices are automatically included into $S(L)$ already;
2.

Any vertex in $X\setminus(U_{\tau}\cup V_{\tau})$ is making a first and last appearance in $L$ , which gives a factor of $n$ . However, it now gives a factor of $\sqrt{n}$ in the bound on the RHS by being a vertex outside the separator, and this is a deficit of $\frac{1}{\sqrt{n}}$ ;
3.

Any vertex in $X\cap(U_{\tau}\Delta V_{\tau})$ is making either a first or last appearance in $L$ (but not both) which gives a factor of $\sqrt{n}$ . Similarly to the above, it gives a factor of $1$ in the block-value bound of $B(S)$ , which gives a deficit of $\frac{1}{\sqrt{n}}$ ;
4.

As we consider the BFS from $X$ using singleton-step, any such singleton-step corresponds to a gain of $\sqrt{n}$ as it gives value $1$ for block-value bound of $B(S)$ while a factor of $\frac{1}{\sqrt{n}}$ to $B(L)$ ;
5.

Any vertex outside $U_{\tau}\cup V_{\tau}$ reached by a singleton-step gives a factor of $n$ in $B(L)$ , while a factor of $\sqrt{n}$ to $B(S)$ Combining the change of vertex factor with the edge assigned to it, this is a change of

$\frac{\sqrt{n}}{n}\cdot\sqrt{n}=1\,;$
6.

Any vertex in $U_{\tau}\Delta V_{\tau}$ reached by a singleton-step gives a change of $\sqrt{n}$ to both bounds, therefore there is no change in the vertex factor restricted to these vertices. Importantly, since it is still reached by a singleton-step, we pick up a change of $\sqrt{n}$ on these vertices;
7.

Combining the above, notice for any vertex i $v\in X\setminus U_{\tau}\cup V_{\tau}$ , we can assign at least one vertex in $U_{\tau}\setminus V_{\tau}$ and $V_{\tau}\setminus U_{\tau}$ reached by a BFS from $v$ without passing through any other vertex in $X$ . As otherwise, $X\setminus\{v\}$ continues being a separator of $T$ while this contradicts with the minimality assumption of $X$ to start with. With at least two vertices in $U_{\tau}\cup V_{\tau}$ assigned to each vertex $v$ , we have a total change of

$\frac{1}{n}\cdot(\sqrt{n})^{2}=1;$
8.

Similarly, for any vertex $v\in X\cap(U_{\tau}\Delta V_{\tau})$ (W.L.O.G. consider $v\in X\cap U_{\tau}$ ) ,we can assign at least one vertex in $V_{\tau}$ reached by the BFS via a singleton-step from $v$ without passing through other vertex in $X$ , as again otherwise removing $v$ from $X$ preserves a separator for $T$ while contradicting with the minimality. This is a change of

$\frac{1}{\sqrt{n}}\cdot\sqrt{n}=1\,.$

This proves that the block-value bound $B(S)\geq B(L)$ for $S=X\cup S(L)$ for step-labeling $L$ . $\hfill\blacktriangleleft$

To wrap up, we have shown that any step-labeling has its block-value bounded by some separator, therefore, using a loose bound to crudely bound the number of step-labeling, the final bound follows as

	$\displaystyle B_{q}(\tau)\coloneqq\sum_{L:\text{ step-labelings for }E(\tau)}B% (L)=$	$\displaystyle\sum_{L:\text{ step-labelings for }E(\tau)}\mathsf{vtxcost}(L)% \cdot\mathsf{edgeval}(L)$
		$\displaystyle\leq c^{\|E(\tau)\|}\cdot\max_{S:\text{separator}}B_{\tau,q}(S)$

for some constant $c>0$ , and we introduce the short-hand $B_{\tau,q}(S)$ to refer to $B(S)$ for shape $\tau$ when the dependence on shape $\tau$ may be unclear from the context.

One may then observe that $c^{|E(\tau)|}\cdot B_{\tau,q}(S)$ are indeed the norm bound given for graph matrix in the i.i.d. setting by [24], and in particular, the polynomial factors in $B_{\tau,q}(S)$ match exactly with the polynomial factors in the SMVS bound therein. Since the $c^{|E(\tau)|}$ factor is dominated by the factors of $q$ (i.e. polylog factors in the $B_{q}$ bound) in the $B(S)$ bound, we have shown that these two bounds match up to lower-order dependence.

However, as introduced in our technical overview, such comparison no longer holds for the scalar example and potentially more. We next show that these are the only examples that a blow-up is incurred in the norm bounds. Formally, we show that a $\sqrt{n}$ blow-up is incurred for each tree-like floating component, i.e. edge-component not connected to neither of the left/right boundary.

Before we get started, we first point out how floating component captures the scalar illustrated by the scalar random variable $p(x)=\sum_{i<j\in[n]}\chi_{G}(\{i,j\})$ . This can be viewed as a shape with $U_{\tau}=V_{\tau}=\emptyset$ and $E(\tau)=p(x)$ . Thus, with the boundary condition being empty, we indeed have a floating component and it is easy to see that is additionally tree-like.

We are now ready to augment the previous lemma to take into account of floating components.

Lemma 33.

For any shape $\tau$ , for any step-labeling $L$ , there exits a separator $S$ whose corresponding block-value bound upper bounds that of $L$ . In other words, there exists vertex separator $S$ such that for some constant $c>0$ ,

	$\displaystyle B(L)$	$\displaystyle\leq(\sqrt{n}\cdot q_{\tau})^{\|V(\tau)\setminus S\|}\cdot\sqrt{% \frac{1-p}{p}}^{\|E(S)\|}\cdot\sqrt{n}^{\|I(\tau)\|}\cdot\sqrt{n}^{\|float_{tree}(V% (\tau)\setminus S)\|}$
		$\displaystyle\cdot\max(1,q_{\tau}^{\|E(\tau)\setminus E(S)\|-\|V(\tau)\setminus V% (S)\|})\cdot q_{\tau}^{\|V(S)\setminus U_{\tau}\cap V_{\tau}\|}\cdot c^{\|E(\tau)\|}$

where $|float_{tree}(V(\tau)\setminus S)|$ is the number of tree-like floating components not connected to $S$ .

Proof.

The key of this lemma is that each floating component gives at most a $\sqrt{n}$ blow-up. Again, we start with the observation that our block-value bound factorizes over connected components, and it suffices for us consider $C$ a floating component. In particular, it suffices for us focus on the components not connected to $S$ and those that are of all singleton-steps, as otherwise the previous proof applies: the component of vertices that make both first and last appearances are connected via singleton-step to vertices that are not making both appearances.

It now suffices to bound the block-value restricted to all-singleton floating components, and its value is given by $n^{|V(C)|}\cdot\frac{1}{\sqrt{n}}^{|E(C)|}$ by our vertex-factor and edge-value assignment scheme. Notice in the case of tree-like floating components, we can bound it by

n^{|V(C)|}\cdot\frac{1}{\sqrt{n}}^{|E(C)|}\leq\sqrt{n}^{|V(C)|}\cdot\sqrt{n}% \leq(\sqrt{n}\cdot q_{\tau})^{|V(C)|}\cdot\sqrt{n}\

and in the case of $|E(C)|\geq|V(C)|$ , we can simply bound it by $(\sqrt{n}q_{\tau})^{|V(C)|}$ . Note that each bound on the RHS is the block-value factors in $B(S)$ associated with such floating component $C$ , and this proves our desired lemma. $\hfill\blacktriangleleft$

2.9 Wrapping Up

We are now ready to conclude by completing the proof to our main theorem.

Proof.

Bby Lemma 33 and Proposition 20, we have

\displaystyle B(\tau)\leq\sum_{L}B(L)\leq c^{|E(\tau)|}\max_{S}B_{\tau}(S)

By design of our block-value function (and grouping the extra factor of $2$ from edge-value to the cost of identifying start of the walk), we have

\mathbb{E}_{G\sim G_{d}(n)}\tr(M_{\tau}M_{\tau}^{\top})^{q}\leq O(n^{|U_{% \alpha}|})\cdot B_{q}(\tau)^{2q}\leq O(n^{|U_{\alpha}|})B(\tau)^{2q}

To obtain concentration of the matrix norm bound, we then appeal to the following proposition and this completes our result of matrix norm bounds for random regular graphs. $\hfill\blacktriangleleft$

Proposition 34.

For a given shape $\tau$ , and a valid block-value bound $B_{q}(\tau)$ , with probability at least $1-c^{-q/\log n}$ ,

\|M_{\tau}\|\leq(1+o_{d}(1))B_{q}(\tau)

Proof.

This follows from Markov’s inequality, for any $\epsilon>0$ ,

	$\displaystyle\Pr[\\|M_{\tau}\\|\geq(1+\epsilon)B_{q}(\tau)]$	$\displaystyle\leq\Pr[\Tr((M_{\tau}M_{\tau}^{\top})^{q})>(1+\epsilon)^{2q}B_{q}% (\tau)^{2q})]$
		$\displaystyle\leq\frac{\mathbb{E}[\Tr((M_{\tau}M_{\tau}^{\top})^{q})]}{(1+% \epsilon)^{2q}B_{q}(\tau)^{2q}}$
		$\displaystyle\leq O(n^{\|U_{\tau}\|/2q})\cdot(\frac{1}{1+\epsilon})^{2q}$
		$\displaystyle\leq c^{-q/\log n}$

for any small enough constant $c>0$ and $q=\Omega(|U_{\tau}|\log n)$ . $\hfill\blacktriangleleft$

References

[1] Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin. Graph matrices: Norm bounds and applications. CoRR, abs/1604.03423, 2020. arXiv:1604.03423.
[2] Ainesh Bakshi and Pravesh K. Kothari. List-decodable subspace recovery: Dimension independent error in polynomial time. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, pages 1279–1297, USA, 2021. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611976465.78.
[3] Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, and Alexander S. Wein. Spectral planting and hardness of refuting cuts, colorability, and communities in random graphs. arXiv preprint, 2020. arXiv:2008.12237.
[4] Jess Banks, Robert Kleinberg, and Cristopher Moore. The lovász theta function for random regular graphs and community detection in the hard regime. SIAM Journal on Computing, 48(3):1098–1119, 2019. doi:10.1137/18M1180396.
[5] Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. SIAM Journal on Computing, 48(2):687–735, 2019. doi:10.1137/17M1138236.
[6] Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. CoRR, abs/1604.03084, 2016. arXiv:1604.03084.
[7] Charles Bordenave. A new proof of friedman’s second eigenvalue theorem and its extension to random lifts. Annales scientifiques de l’École normale supérieure, 2015. URL: https://api.semanticscholar.org/CorpusID:55584276.
[8] Charles Bordenave. A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts. Technical report, arXiv, 2019. To appear in Annales scientifiques de l’École normale supérieure. arXiv:1502.04482v4.
[9] Charles Bordenave, Marc Lelarge, and Laurent Massoulié. Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 1347–1357. IEEE, 2015. doi:10.1109/FOCS.2015.86.
[10] Andrei Broder and Eli Shamir. On the second eigenvalue of random regular graphs. In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pages 286–294, 1987. doi:10.1109/SFCS.1987.45.
[11] Chi-Fang Chen, Jorge Garza-Vargas, Joel A. Tropp, and Ramon van Handel. A new approach to strong convergence, 2024. arXiv:2405.16026.
[12] Yash Deshpande, Andrea Montanari, Ryan O’Donnell, Tselil Schramm, and Subhabrata Sen. The threshold for sdp-refutation of random regular nae-3sat. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2305–2321. SIAM, 2019. doi:10.1137/1.9781611975482.140.
[13] Joel Friedman. A proof of alon’s second eigenvalue conjecture. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 720–724. ACM, 2003. doi:10.1145/780542.780646.
[14] Alan Frieze and Michał Karoński. Introduction to Random Graphs. Cambridge University Press, 2015.
[15] David Gamarnik, Aukosh Jagannath, and Alexander S. Wein. Hardness of random optimization problems for boolean circuits, low-degree polynomials, and langevin dynamics, 2022. arXiv:2004.12063.
[16] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, November 1995. doi:10.1145/227683.227684.
[17] Venkatesan Guruswami and Ali Kemal Sinop. Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives. In FOCS, pages 482–491, 2011. doi:10.1109/FOCS.2011.36.
[18] A. J. Hoffman and Leonard Howes. On eigenvalues and colorings of graphs, ii. Annals of the New York Academy of Sciences, 175, 1970. URL: https://api.semanticscholar.org/CorpusID:85243045.
[19] Samuel B. Hopkins. Mean estimation with sub-gaussian rates in polynomial time, 2019. arXiv:1809.07425.
[20] Samuel B. Hopkins and Jerry Li. Mixture Models, Robustness, and Sum of Squares Proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1021–1034, New York, NY, USA, 2018. ACM. doi:10.1145/3188745.3188748.
[21] Samuel B Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-squares proofs. In Conference on Learning Theory, pages 956–1006, 2015. URL: http://proceedings.mlr.press/v40/Hopkins15.html.
[22] Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, and Jeff Xu. Ellipsoid Fitting up to a Constant. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 78:1–78:20, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2023.78.
[23] Jiaoyang Huang and Horng-Tzer Yau. Spectrum of random $d$ -regular graphs up to the edge, 2021. arXiv:2102.00963.
[24] C. Jones, A. Potechin, G. Rajendran, M. Tulsiani, and J. Xu. Sum-of-squares lower bounds for sparse independent set. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 406–416, Los Alamitos, CA, USA, February 2022. IEEE Computer Society. doi:10.1109/FOCS52979.2021.00048.
[25] Chris Jones and Lucas Pesenti. Diagram analysis of iterative algorithms, 2024. doi:10.48550/arXiv.2404.07881.
[26] Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu. Sum-of-squares lower bounds for densest k-subgraph. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 84–95, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585221.
[27] Adam Klivans, Pravesh K. Kothari, and Raghu Meka. Efficient algorithms for outlier-robust regression, 2020. arXiv:1803.03241.
[28] Pravesh Kothari, Santosh S. Vempala, Alexander S. Wein, and Jeff Xu. Is planted coloring easier than planted clique? In Annual Conference Computational Learning Theory, 2023. URL: https://api.semanticscholar.org/CorpusID:257255498.
[29] Pravesh K. Kothari, Aaron Potechin, and Jeff Xu. Sum-of-squares lower bounds for independent set on ultra-sparse random graphs. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1923–1934, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649703.
[30] Pravesh K. Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1035–1046, New York, NY, USA, 2018. Association for Computing Machinery. doi:10.1145/3188745.3188970.
[31] Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio, 2019. arXiv:1907.11636.
[32] Dmitriy Kunisky and Xifan Yu. Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs, 2024. doi:10.48550/arXiv.2404.17012.
[33] Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. on Optimization, 11(3):796–817, March 2000. doi:10.1137/S1052623400366802.
[34] Tengyu Ma, Jonathan Shi, and David Steurer. Polynomial-time tensor decompositions with sum-of-squares. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 438–446, 2016. doi:10.1109/FOCS.2016.54.
[35] Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu. Lifting sum-of-squares lower bounds: Degree-2 to degree-4. CoRR, abs/1911.01411, 2019. arXiv:1911.01411.
[36] Ankur Moitra and Alexander S. Wein. Spectral methods from tensor networks. SIAM Journal on Computing, 52(2):STOC19–354–STOC19–384, 2019. doi:10.1137/20M1311661.
[37] Shuo Pang. SOS lower bound for exact planted clique. In 36th Computational Complexity Conference, volume 200 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. 26, 63. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.
[38] Pablo A Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, 2000.
[39] Aaron Potechin and Goutham Rajendran. Machinery for proving sum-of-squares lower bounds on certification problems. CoRR, abs/2011.04253, 2020. arXiv:2011.04253.
[40] Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly Refuting Random CSPs Below the Spectral Threshold. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 121–131, New York, NY, USA, 2017. ACM. doi:10.1145/3055399.3055417.
[41] Goutham Rajendran and Madhur Tulsiani. Concentration of polynomial random matrices via efron-stein inequalities, 2022. doi:10.48550/arXiv.2209.02655.
[42] Cynthia Rush, Fiona Skerman, Alexander S. Wein, and Dana Yang. Is it easier to count communities than find them?, 2022. doi:10.48550/arXiv.2212.10872.
[43] Amir Sarid. The spectral gap of random regular graphs. Random Structures & Algorithms, 63(2):557–587, 2023. doi:10.1002/rsa.21150.
[44] Tselil Schramm and Alexander S. Wein. Computational barriers to estimation from low-degree polynomials. The Annals of Statistics, 50(3), June 2022. doi:10.1214/22-aos2179.
[45] Konstantin Tikhomirov and Pierre Youssef. The spectral gap of dense random regular graphs. arXiv e-prints, page arXiv:1610.01765, October 2016. doi:10.48550/arXiv.1610.01765.
[46] Linh V. Tran, Van H. Vu, and Ke Wang. Sparse random graphs: Eigenvalues and eigenvectors. Random Structures & Algorithms, 42(1):110–134, 2013. doi:10.1002/rsa.20406.
[47] Madhur Tulsiani and June Wu. Simple norm bounds for polynomial random matrices via decoupling, 2024. doi:10.48550/arXiv.2412.07936.
[48] Alexander S Wein. Optimal low-degree hardness of maximum independent set. arXiv preprint, 2020. arXiv:2010.06563.

[bib.bib1] [1] Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin. Graph matrices: Norm bounds and applications. CoRR, abs/1604.03423, 2020. arXiv:1604.03423.

[bib.bib2] [2] Ainesh Bakshi and Pravesh K. Kothari. List-decodable subspace recovery: Dimension independent error in polynomial time. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, pages 1279–1297, USA, 2021. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611976465.78.

[bib.bib3] [3] Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, and Alexander S. Wein. Spectral planting and hardness of refuting cuts, colorability, and communities in random graphs. arXiv preprint, 2020. arXiv:2008.12237.

[bib.bib4] [4] Jess Banks, Robert Kleinberg, and Cristopher Moore. The lovász theta function for random regular graphs and community detection in the hard regime. SIAM Journal on Computing, 48(3):1098–1119, 2019. doi:10.1137/18M1180396.

[bib.bib5] [5] Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. SIAM Journal on Computing, 48(2):687–735, 2019. doi:10.1137/17M1138236.

[bib.bib6] [6] Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. CoRR, abs/1604.03084, 2016. arXiv:1604.03084.

[bib.bib7] [7] Charles Bordenave. A new proof of friedman’s second eigenvalue theorem and its extension to random lifts. Annales scientifiques de l’École normale supérieure, 2015. URL: https://api.semanticscholar.org/CorpusID:55584276.

[bib.bib8] [8] Charles Bordenave. A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts. Technical report, arXiv, 2019. To appear in Annales scientifiques de l’École normale supérieure. arXiv:1502.04482v4.

[bib.bib9] [9] Charles Bordenave, Marc Lelarge, and Laurent Massoulié. Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 1347–1357. IEEE, 2015. doi:10.1109/FOCS.2015.86.

[bib.bib10] [10] Andrei Broder and Eli Shamir. On the second eigenvalue of random regular graphs. In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pages 286–294, 1987. doi:10.1109/SFCS.1987.45.

[bib.bib11] [11] Chi-Fang Chen, Jorge Garza-Vargas, Joel A. Tropp, and Ramon van Handel. A new approach to strong convergence, 2024. arXiv:2405.16026.

[bib.bib12] [12] Yash Deshpande, Andrea Montanari, Ryan O’Donnell, Tselil Schramm, and Subhabrata Sen. The threshold for sdp-refutation of random regular nae-3sat. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2305–2321. SIAM, 2019. doi:10.1137/1.9781611975482.140.

[bib.bib13] [13] Joel Friedman. A proof of alon’s second eigenvalue conjecture. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 720–724. ACM, 2003. doi:10.1145/780542.780646.

[bib.bib14] [14] Alan Frieze and Michał Karoński. Introduction to Random Graphs. Cambridge University Press, 2015.

[bib.bib15] [15] David Gamarnik, Aukosh Jagannath, and Alexander S. Wein. Hardness of random optimization problems for boolean circuits, low-degree polynomials, and langevin dynamics, 2022. arXiv:2004.12063.

[bib.bib16] [16] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, November 1995. doi:10.1145/227683.227684.

[bib.bib17] [17] Venkatesan Guruswami and Ali Kemal Sinop. Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives. In FOCS, pages 482–491, 2011. doi:10.1109/FOCS.2011.36.

[bib.bib18] [18] A. J. Hoffman and Leonard Howes. On eigenvalues and colorings of graphs, ii. Annals of the New York Academy of Sciences, 175, 1970. URL: https://api.semanticscholar.org/CorpusID:85243045.

[bib.bib19] [19] Samuel B. Hopkins. Mean estimation with sub-gaussian rates in polynomial time, 2019. arXiv:1809.07425.

[bib.bib20] [20] Samuel B. Hopkins and Jerry Li. Mixture Models, Robustness, and Sum of Squares Proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1021–1034, New York, NY, USA, 2018. ACM. doi:10.1145/3188745.3188748.

[bib.bib21] [21] Samuel B Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-squares proofs. In Conference on Learning Theory, pages 956–1006, 2015. URL: http://proceedings.mlr.press/v40/Hopkins15.html.

[bib.bib22] [22] Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, and Jeff Xu. Ellipsoid Fitting up to a Constant. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 78:1–78:20, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2023.78.

[bib.bib23] [23] Jiaoyang Huang and Horng-Tzer Yau. Spectrum of random $d$ -regular graphs up to the edge, 2021. arXiv:2102.00963.

[bib.bib24] [24] C. Jones, A. Potechin, G. Rajendran, M. Tulsiani, and J. Xu. Sum-of-squares lower bounds for sparse independent set. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 406–416, Los Alamitos, CA, USA, February 2022. IEEE Computer Society. doi:10.1109/FOCS52979.2021.00048.

[bib.bib25] [25] Chris Jones and Lucas Pesenti. Diagram analysis of iterative algorithms, 2024. doi:10.48550/arXiv.2404.07881.

[bib.bib26] [26] Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu. Sum-of-squares lower bounds for densest k-subgraph. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 84–95, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585221.

[bib.bib27] [27] Adam Klivans, Pravesh K. Kothari, and Raghu Meka. Efficient algorithms for outlier-robust regression, 2020. arXiv:1803.03241.

[bib.bib28] [28] Pravesh Kothari, Santosh S. Vempala, Alexander S. Wein, and Jeff Xu. Is planted coloring easier than planted clique? In Annual Conference Computational Learning Theory, 2023. URL: https://api.semanticscholar.org/CorpusID:257255498.

[bib.bib29] [29] Pravesh K. Kothari, Aaron Potechin, and Jeff Xu. Sum-of-squares lower bounds for independent set on ultra-sparse random graphs. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1923–1934, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649703.

[bib.bib30] [30] Pravesh K. Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1035–1046, New York, NY, USA, 2018. Association for Computing Machinery. doi:10.1145/3188745.3188970.

[bib.bib31] [31] Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio, 2019. arXiv:1907.11636.

[bib.bib32] [32] Dmitriy Kunisky and Xifan Yu. Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs, 2024. doi:10.48550/arXiv.2404.17012.

[bib.bib33] [33] Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. on Optimization, 11(3):796–817, March 2000. doi:10.1137/S1052623400366802.

[bib.bib34] [34] Tengyu Ma, Jonathan Shi, and David Steurer. Polynomial-time tensor decompositions with sum-of-squares. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 438–446, 2016. doi:10.1109/FOCS.2016.54.

[bib.bib35] [35] Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu. Lifting sum-of-squares lower bounds: Degree-2 to degree-4. CoRR, abs/1911.01411, 2019. arXiv:1911.01411.

[bib.bib36] [36] Ankur Moitra and Alexander S. Wein. Spectral methods from tensor networks. SIAM Journal on Computing, 52(2):STOC19–354–STOC19–384, 2019. doi:10.1137/20M1311661.

[bib.bib37] [37] Shuo Pang. SOS lower bound for exact planted clique. In 36th Computational Complexity Conference, volume 200 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. 26, 63. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.

[bib.bib38] [38] Pablo A Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, 2000.

[bib.bib39] [39] Aaron Potechin and Goutham Rajendran. Machinery for proving sum-of-squares lower bounds on certification problems. CoRR, abs/2011.04253, 2020. arXiv:2011.04253.

[bib.bib40] [40] Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly Refuting Random CSPs Below the Spectral Threshold. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 121–131, New York, NY, USA, 2017. ACM. doi:10.1145/3055399.3055417.

[bib.bib41] [41] Goutham Rajendran and Madhur Tulsiani. Concentration of polynomial random matrices via efron-stein inequalities, 2022. doi:10.48550/arXiv.2209.02655.

[bib.bib42] [42] Cynthia Rush, Fiona Skerman, Alexander S. Wein, and Dana Yang. Is it easier to count communities than find them?, 2022. doi:10.48550/arXiv.2212.10872.

[bib.bib43] [43] Amir Sarid. The spectral gap of random regular graphs. Random Structures & Algorithms, 63(2):557–587, 2023. doi:10.1002/rsa.21150.

[bib.bib44] [44] Tselil Schramm and Alexander S. Wein. Computational barriers to estimation from low-degree polynomials. The Annals of Statistics, 50(3), June 2022. doi:10.1214/22-aos2179.

[bib.bib45] [45] Konstantin Tikhomirov and Pierre Youssef. The spectral gap of dense random regular graphs. arXiv e-prints, page arXiv:1610.01765, October 2016. doi:10.48550/arXiv.1610.01765.

[bib.bib46] [46] Linh V. Tran, Van H. Vu, and Ke Wang. Sparse random graphs: Eigenvalues and eigenvectors. Random Structures & Algorithms, 42(1):110–134, 2013. doi:10.1002/rsa.20406.

[bib.bib47] [47] Madhur Tulsiani and June Wu. Simple norm bounds for polynomial random matrices via decoupling, 2024. doi:10.48550/arXiv.2412.07936.

[bib.bib48] [48] Alexander S Wein. Optimal low-degree hardness of maximum independent set. arXiv preprint, 2020. arXiv:2010.06563.

Switching Graph Matrix Norm Bounds: From i.i.d. to Random Regular Graphs

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Works for Low-Degree Polynomial Hardness and Level-𝟐 Local Statistics

Previous Works for Graph Matrix Norm Bounds

Distribution of Random 𝒅-Regular Graphs 𝑮𝒅⁢(𝒏)

1.1 Informal Statement of Our Results

Theorem 1 (Informal of Theorem 15).

Definition 2 (Pseudo-expectation of degree 𝖽𝗌𝗈𝗌 ).

Definition 3 (Axioms for independent set).

Theorem 4 ([24]).

Theorem 5 (Switching to Lower bounds for Gd⁢(n)).

2 Graph Matrix Norm Bounds for Random Regular Graphs

2.1 Preliminaries of Graph Matrix

Definition 6 (Fourier character for G⁢(n,dn)).

Definition 7 (Shape).

Definition 8 (Shape transpose).

Definition 9 (Embedding).

Definition 10 (Graph matrix of a shape).

Definition 11 (Isolated vertex).

Definition 12 (Floating component).

Definition 13 (Tree-like component).

2.2 Main Theorems of Graph Matrix Norm Bounds on Random 𝒅-Regular Graphs

Theorem 14 (User-friendly version for shapes without floating component).

Theorem 15 (Full version for shapes containing floating component).

2.3 Trace Moment Method and Block-Value Bound

Spectral Norm Bound from Trace Moment Method

Definition 16 (Shape walk and its valid labelings).

Spectral Norm Bound from Block Value Bound

Definition 17 (Block value bound).

▶ Remark 18.

Definition 19 (Step-label and BlockStep-Label).

Proposition 20.

Proof.

2.4 Bounding Walk Value: putting in the regularity

Definition 21 (Surprise step/visit).

Definition 22 (Singleton step/edge).

Lemma 23 (Restated edge-value bound from Corollary 3.6 in [43]).

Proposition 24.

Proof.

2.5 Bounding Vertex-Factor: as if edges are i.i.d.

Vertex-factor Assignment Scheme

Proposition 25 (Vertex-factor assignment scheme).

Proof.

2.6 Explicit Application of BlockValue Machinery

Lemma 26.

Proof.

2.7 Connecting back to Vertex Separator

Definition 27 (Vertex separator).

Building the Separator from BlockStep-Labels

Claim 28.

Proof.

Corollary 29.

Observation 30.

2.8 Deducing Block-Value from Step-Labeling

Lemma 31.

Proof.

Lemma 32.

Proof.

Lemma 33.

Proof.

2.9 Wrapping Up

Proof.

Proposition 34.

Proof.

References

Switching Graph Matrix Norm Bounds:
From i.i.d. to Random Regular Graphs

Works for Low-Degree Polynomial Hardness and Level- $2$ Local Statistics

Distribution of Random $𝒅$ -Regular Graphs $G_{d}(n)$

Definition 2 (Pseudo-expectation of degree $\mathsf{dsos}$ ).

Theorem 5 (Switching to Lower bounds for $G_{d}(n)$ ).

Definition 6 (Fourier character for $G(n,\frac{d}{n})$ ).

2.2 Main Theorems of Graph Matrix Norm Bounds on Random $𝒅$ -Regular Graphs

$\blacktriangleright$ Remark 18.