$\displaystyle\Delta^{c_{1}}\left(\frac{k}{d}\right)^{c_{2}}\mathop{\mathbb{E}}_{(u,l_{i})\sim\mu}[\prod_{i\in[m]}l_{i}^{e_{i}}\prod_{j\in[d]}u_{j}^{f_{j}}]\prod_{i,j}\sqrt{\lambda}^{a_{ij}}=\left(\frac{1}{\sqrt{k}}\right)^{|I|}\left(\frac{k}{d}\right)^{c_{2}}\Delta^{c_{1}}\prod_{i\in[m]}(e_{i}-1)!!\prod_{i,j}\frac{\sqrt{\lambda}^{a_{ij}}}{\sqrt{k}^{a_{ij}}}$

The last equality follows because, for each $j$ such that $u_{j}$ is nonzero,
we have $u_{j}^{t}=(\frac{1}{\sqrt{k}})^{t}$ and
$\mathop{\mathbb{E}}_{g\sim\mathcal{N}(0,1)}[g^{t}]=(t-1)!!$ if $t$ is even.

Define the degree of SoS to be $D_{sos}=d^{C_{sos}\varepsilon}$ for some
constant $C_{sos}>0$ that we choose later. Define the truncation parameters to
be $D_{V}=d^{C_{V}\varepsilon},D_{E}=d^{C_{E}\varepsilon}$ for some constants
$C_{V},C_{E}>0$. Regarding the choice of parameters, although we are working
with a different problem, 3.3 directly applies.

The underlying graphs for the graph matrices have the following structure:
There will be two types of vertices - $d$ type $1$ vertices corresponding to
the dimensions of the space and $m$ type $2$ vertices corresponding to the
different input vectors. The shapes will correspond to bipartite graphs with
edges going between across of different types. For the analysis of Sparse PCA,
we will use the following notation.

  * •

For a shape $\alpha$ and type $t\in\\{1,2\\}$, let $V_{t}(\alpha)$ denote the
vertices of $V(\alpha)$ that are of type $t$. Let
$|\alpha|_{t}=|V_{t}(\alpha)|$.

  * •

For an index shape $U$ and a vertex $i$, define $deg^{U}(i)$ as follows: If
$i\in V(U)$, then it is the power of the unique index shape piece $A\in U$
such that $i\in V(A)$. Otherwise, it is $0$.

  * •

For an index shape $U$, define $deg(U)=\sum_{i\in V(U)}deg^{U}(i)$. This is
also the degree of the monomial $p_{U}$.

  * •

For a shape $\alpha$ and vertex $i$ in $\alpha$, let
$deg^{\alpha}(i)=\sum_{i\in e\in E(\alpha)}l_{e}$.

  * •

For any shape $\alpha$, let $deg(\alpha)=deg(U_{\alpha})+deg(V_{\alpha})$.

  * •

For an index shape $U\in{\mathcal{I}}_{mid}$ and type $t\in\\{1,2\\}$, let
$U_{t}\in U$ denote the index shape piece of type $t$ in $U$ if it exists,
otherwise define $U_{t}$ to be $\emptyset$. Note that this is well defined
since for each type $t$, there is at most one index shape piece of type $t$ in
$U$ since $U\in{\mathcal{I}}_{mid}$. Also, denote by $|U|_{t}$ the length of
the tuple $U_{t}$.

We will now describe the decomposition of the moment matrix $\Lambda$.

######  Definition 4.3.

If a shape $\alpha$ satisfies the following properties:

  * •

Both $U_{\alpha}$ and $V_{\alpha}$ only contain index shape pieces of type
$1$,

  * •

$deg^{\alpha}(i)+deg^{U_{\alpha}}(i)+deg^{V_{\alpha}}(i)$ is even for all
$i\in V(\alpha)$,

  * •

$\alpha$ is proper,

  * •

$\alpha$ satisfies the truncation parameters $D_{sos},D_{V},D_{E}$.

then define

$\lambda_{\alpha}=\left(\frac{1}{\sqrt{k}}\right)^{deg(\alpha)}\left(\frac{k}{d}\right)^{|\alpha|_{1}}\Delta^{|\alpha|_{2}}\prod_{j\in
V_{2}(\alpha)}(deg^{\alpha}(j)-1)!!\prod_{e\in
E(\alpha)}\frac{\sqrt{\lambda}^{l_{e}}}{\sqrt{k}^{l_{e}}}$

Otherwise, define $\lambda_{\alpha}=0$.

######  Corollary 4.4.

$\Lambda=\sum\lambda_{\alpha}M_{\alpha}$.

####  2 Qualitative machinery bounds

In this section, we will prove the main PSD mass condition and obtain
qualitative bounds of the other two conditions, which we will reuse in the
full verification. As in prior sections, we will state the bounds first,
introduce notation and then prove them all in a unified manner.

######  Lemma 4.5 (PSD mass).

For all $U\in{\mathcal{I}}_{mid}$, $H_{Id_{U}}\succeq 0$

We define the following quantities to capture the contribution of the vertices
within $\tau,\gamma$ to the Fourier coefficients.

######  Definition 4.6.

For $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, if
$deg^{\tau}(i)$ is even for all vertices $i\in V(\tau)\setminus
U_{\tau}\setminus V_{\tau}$, define

$S(\tau)=\left(\frac{k}{d}\right)^{|\tau|_{1}-|U_{\tau}|_{1}}\Delta^{|\tau|_{2}-|U_{\tau}|_{2}}\prod_{j\in
V_{2}(\tau)\setminus U_{\tau}\setminus V_{\tau}}(deg^{\tau}(j)-1)!!\prod_{e\in
E(\tau)}\frac{\sqrt{\lambda}^{l_{e}}}{\sqrt{k}^{l_{e}}}$

Otherwise, define $S(\tau)=0$. For all $U,V\in{\mathcal{I}}_{mid}$ where
$w(U)>w(V)$ and $\gamma\in\Gamma_{U,V}$, if $deg^{\gamma}(i)$ is even for all
vertices $i$ in $V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$, define

$S(\gamma)=\left(\frac{k}{d}\right)^{|\gamma|_{1}-\frac{|U_{\gamma}|_{1}+|V_{\gamma}|_{1}}{2}}\Delta^{|\gamma|_{2}-\frac{|U_{\gamma}|_{2}+|V_{\gamma}|_{2}}{2}}\prod_{j\in
V_{2}(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}}(deg^{\gamma}(j)-1)!!\prod_{e\in
E(\gamma)}\frac{\sqrt{\lambda}^{l_{e}}}{\sqrt{k}^{l_{e}}}$

Otherwise, define $S(\gamma)=0$.

For getting the best bounds, it will be convenient to discretize the Normal
distribution. The following fact follows from standard results on Gaussian
quadrature, see for e.g. [diakonikolas2017statistical, Lemma 4.3].

######  Fact 4.7 (Discretizing the Normal distribution).

There is an absolute constant $C_{disc}$ such that, for any positive integer
$D$, there exists a distribution ${\mathcal{E}}$ over the real numbers
supported on $D$ points $p_{1},\ldots,p_{D}$, such that $|p_{i}|\leq
C_{disc}\sqrt{D}$ for all $i\leq D$ and
$\mathop{\mathbb{E}}_{g\sim{\mathcal{E}}}[g^{t}]=\mathop{\mathbb{E}}_{g\sim\mathcal{N}(0,1)}[g^{t}]$
for all $t=0,1,\ldots,2D-1$.

######  Definition 4.8.

For any shape $\tau$, suppose
$U^{\prime}=(U_{\tau})_{2},V^{\prime}=(V_{\tau})_{2}$ are the type $2$
vertices in $U_{\tau},V_{\tau}$ respectively. Define
$R(\tau)=(C_{disc}\sqrt{D_{E}})^{\sum_{j\in U^{\prime}\cup
V^{\prime}}deg^{\tau}(j)}$.

We can now state our qualitative bounds.

######  Lemma 4.9 (Qualitative middle shape bounds).

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,

$\begin{bmatrix}\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$

We again use the canonical definition of $H_{\gamma}^{\prime}$ from Section 4.

######  Lemma 4.10 (Qualitative intersection term bounds).

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}R(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}\preceq
H_{\gamma}^{\prime}$

##### Proof of the PSD mass condition

Most of the notation and analysis here are similar to the case of Tensor PCA,
we just need to appropriately modify them since there are two types of
vertices in the Sparse PCA application. When we compose shapes
$\sigma,\sigma^{\prime}$, from Definition 4.3, in order for
$\lambda_{\sigma\circ\sigma^{\prime}}$ to be nonzero, observe that all
vertices $i$ in $\lambda_{\sigma\circ\sigma^{\prime}}$ should have
$deg^{\sigma\circ\sigma^{\prime}}(i)+deg^{U_{\sigma\circ\sigma^{\prime}}}(i)+deg^{V_{\sigma\circ\sigma^{\prime}}}(i)$
to be even. To capture this notion conveniently, we again use the notion of
parity vectors.

######  Definition 4.11.

Define a parity vector $\rho$ to be a vector whose entries are in $\\{0,1\\}$.
For $U\in{\mathcal{I}}_{mid}$, define ${\mathcal{P}}_{U}$ to be the set of
parity vectors $\rho$ whose coordinates are indexed by $U_{1}$ followed by
$U_{2}$.

######  Definition 4.12.

For a left shape $\sigma$, define
$\rho_{\sigma}\in{\mathcal{P}}_{V_{\sigma}}$, called the parity vector of
$\sigma$, to be the parity vector such that for each vertex $i\in V_{\sigma}$,
the $i$-th entry of $\rho_{\sigma}$ is the parity of
$deg^{U_{\sigma}}(i)+deg^{\sigma}(i)$, that is, $(\rho_{\sigma})_{i}\equiv
deg^{U_{\sigma}}(i)+deg^{\sigma}(i)\pmod{2}$. For $U\in{\mathcal{I}}_{mid}$
and $\rho\in{\mathcal{P}}_{U}$, let ${\mathcal{L}}_{U,\rho}$ be the set of all
left shapes $\sigma\in{\mathcal{L}}_{U}$ such that $\rho_{\sigma}=\rho$, that
is, the set of all left shapes with parity vector $\rho$.

For a shape $\tau$, for a $\tau$ coefficient matrix $H_{\tau}$ and parity
vectors
$\rho\in{\mathcal{P}}_{U_{\tau}},\rho^{\prime}\in{\mathcal{P}}_{V_{\tau}}$,
define the $\tau$-coefficient matrix $H_{\tau,\rho,\rho^{\prime}}$ as
$H_{\tau,\rho,\rho^{\prime}}(\sigma,\sigma^{\prime})=H_{\tau}(\sigma,\sigma^{\prime})$
if
$\sigma\in{\mathcal{L}}_{U_{\tau},\rho},\sigma^{\prime}\in{\mathcal{L}}_{V_{\tau},\rho^{\prime}}$
and $0$ otherwise. This immediately implies the following proposition.

######  Proposition 4.13.

For any shape $\tau$ and $\tau$-coefficient matrix $H_{\tau}$, we have the
equality
$H_{\tau}=\sum_{\rho\in{\mathcal{P}}_{U_{\tau}},\rho^{\prime}\in{\mathcal{P}}_{V_{\tau}}}H_{\tau,\rho,\rho^{\prime}}$

######  Proposition 4.14.

For any $U\in{\mathcal{I}}_{mid}$,
$H_{Id_{U}}=\sum_{\rho\in{\mathcal{P}}_{U}}H_{Id_{U},\rho,\rho}$

###### Proof.

For any $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}$, using Definition 4.3,
note that in order for $H_{Id_{U}}(\sigma,\sigma^{\prime})$ to be nonzero, we
must have $\rho_{\sigma}=\rho_{\sigma^{\prime}}$.

We now discretize the normal distribution while matching the first $2D_{E}-1$
moments.

######  Definition 4.15.

Let ${\mathcal{D}}$ be a distribution over the real numbers obtained by
setting $D=D_{E}$ in 4.7. So, in particular, for any $x$ sampled from
${\mathcal{D}}$, we have $|x|\leq C_{disc}\sqrt{D_{E}}$ and for $t\leq
2D_{E}-1$, $\mathop{\mathbb{E}}_{x\sim{\mathcal{D}}}[x^{t}]=(t-1)!!$.

We define the following quantities to capture the contribution of the vertices
within $\sigma$ to the Fourier coefficients.

######  Definition 4.16.

For a shape $\sigma\in{\mathcal{L}}$, if $deg^{\sigma}(i)+deg^{U_{\sigma}}(i)$
is even for all vertices $i\in V(\sigma)\setminus V_{\sigma}$, define

$T(\sigma)=\left(\frac{1}{\sqrt{k}}\right)^{deg(U_{\sigma})}\left(\frac{k}{d}\right)^{|\sigma|_{1}-\frac{|V_{\sigma}|_{1}}{2}}\Delta^{|\sigma|_{2}-\frac{|V_{\sigma}|_{2}}{2}}\prod_{j\in
V_{2}(\sigma)\setminus V_{\sigma}}(deg^{\sigma}(j)-1)!!\prod_{e\in
E(\sigma)}\frac{\sqrt{\lambda}^{l_{e}}}{\sqrt{k}^{l_{e}}}$

Otherwise, define $T(\sigma)=0$.

######  Definition 4.17.

Let $U\in{\mathcal{I}}_{mid}$. Let $x_{i}$ for $i\in U_{2}$ be variables.
Denote them collectively as $x_{U_{2}}$. For $\rho\in{\mathcal{P}}_{U}$,
define $v_{\rho,x_{U_{2}}}$ to be the vector indexed by left shapes
$\sigma\in{\mathcal{L}}$ such that the $\sigma$th entry is
$T(\sigma)\prod_{i\in{U_{2}}}x_{i}^{deg^{\sigma}(i)}$ if
$\sigma\in{\mathcal{L}}_{U,\rho}$ and $0$ otherwise.

The following proposition is obvious and immediately implies the PSD mass
condition.

######  Proposition 4.18.

For any $U\in{\mathcal{I}}_{mid},\rho\in{\mathcal{P}}_{U}$, suppose $x_{i}$
for $i\in U_{2}$ are random variables sampled from ${\mathcal{D}}$. Then,
$H_{Id_{U},\rho,\rho}=\frac{1}{|Aut(U)|}\mathop{\mathbb{E}}_{x}[v_{\rho,x_{U_{2}}}v_{\rho,x_{U_{2}}}^{T}]$.

###### Proof.

Observe that for $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U,\rho}$ and
$t\in\\{1,2\\}$,
$(|\sigma|_{t}-\frac{|V_{\sigma}|_{t}}{2})+(|\sigma^{\prime}|_{t}-\frac{|V_{\sigma^{\prime}}|_{t}}{2})=|\sigma\circ\sigma^{\prime}|_{t}$.
The result follows by verifying the conditions of Definition 4.3 and using
Definition 4.15.

###### Proof of the PSD mass condition Lemma 4.5.

We have $H_{Id_{U}}=\sum_{\rho\in{\mathcal{P}}_{U}}H_{Id_{U},\rho,\rho}\succeq
0$ because of the above proposition.

##### Qualitative middle shape bounds

The next proposition captures the fact that when we compose shapes
$\sigma,\tau,\sigma^{\prime T}$, in order for
$\lambda_{\sigma\circ\tau\circ\sigma^{\prime T}}$ to be nonzero, the parities
of the degrees of the merged vertices should add up correspondingly.

######  Proposition 4.19.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, there exist
two sets of parity vectors $P_{\tau},Q_{\tau}\subseteq{\mathcal{P}}_{U}$ and a
bijection $\pi:P_{\tau}\rightarrow Q_{\tau}$ such that $H_{\tau}=\sum_{\rho\in
P_{\tau}}H_{\tau,\rho,\pi(\rho)}$.

###### Proof.

Using Definition 4.3, in order for $H_{\tau}(\sigma,\sigma^{\prime})$ to be
nonzero, we must have that, in $\sigma\circ\tau\circ\sigma^{\prime}$, for all
$i\in U_{\tau}\cup V_{\tau}$,
$deg^{U_{\sigma}}(i)+deg^{U_{\sigma^{\prime}}}(i)+deg^{\sigma\circ\tau\circ\sigma^{\prime
T}}(i)$ must be even. In other words, for any $\rho\in{\mathcal{P}}_{U}$,
there is at most one $\rho^{\prime}\in{\mathcal{P}}_{U}$ such that if we take
$\sigma\in{\mathcal{L}}_{U,\rho},\sigma^{\prime}\in{\mathcal{L}}_{U}$ with
$H_{\tau}(\sigma,\sigma^{\prime})$ nonzero, then the parity of
$\sigma^{\prime}$ is $\rho^{\prime}$. Also, observe that $\rho^{\prime}$
determines $\rho$. We then take $P_{\tau}$ to be the set of $\rho$ such that
$\rho^{\prime}$ exists, $Q_{\tau}$ to be the set of $\rho^{\prime}$ and in
this case, we define $\pi(\rho)=\rho^{\prime}$.

######  Proposition 4.20.

For any $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, suppose we
take $\rho\in P_{\tau}$. Let $\pi$ be the bijection from 4.19 so that
$\pi(\rho)\in Q_{\tau}$. Let
$U^{\prime}=(U_{\tau})_{2},V^{\prime}=(V_{\tau})_{2}$ be the type $2$ vertices
in $U_{\tau},V_{\tau}$ respectively. Let $x_{i}$ for $i\in U^{\prime}\cup
V^{\prime}$ be random variables independently sampled from ${\mathcal{D}}$.
Define $x_{U^{\prime}}$ (resp. $x_{V^{\prime}}$) to be the subset of variables
$x_{i}$ for $i\in U^{\prime}$ (resp. $i\in V^{\prime}$). Then,

$H_{\tau,\rho,\pi(\rho)}=\frac{1}{|Aut(U)|^{2}}S(\tau)\mathop{\mathbb{E}}_{x}\left[v_{\rho,x_{U^{\prime}}}\left(\prod_{i\in
U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}^{T}\right]$

###### Proof.

For $\sigma\in L_{U,\rho},\sigma^{\prime}\in{\mathcal{L}}_{U,\pi(\rho)}$ and
$t\in\\{1,2\\}$, we have
$(|\tau|_{t}-|U_{\tau}|_{t})+(|\sigma|_{t}-\frac{|V_{\sigma}|_{t}}{2})+(|\sigma^{\prime}|_{t}-\frac{|V_{\sigma^{\prime}}|_{t}}{2})=|\sigma\circ\tau\circ\sigma^{\prime}|_{t}$.
The result then follows by a straightforward verification of the conditions of
Definition 4.3 using Definition 4.15.

We are ready to show the qualitative middle shape bounds.

###### Proof of the qualitative middle shape bounds Lemma 4.9.

Let $P_{\tau},Q_{\tau},\pi$ be from 4.19. Let
$U^{\prime}=(U_{\tau})_{2},V^{\prime}=(V_{\tau})_{2}$ be the type $2$ vertices
in $U_{\tau},V_{\tau}$ respectively. Let $x_{i}$ for $i\in U^{\prime}\cup
V^{\prime}$ be random variables independently sampled from ${\mathcal{D}}$.
Define $x_{U^{\prime}}$ (resp. $x_{V^{\prime}}$) to be the subset of variables
$x_{i}$ for $i\in U^{\prime}$ (resp. $i\in V^{\prime}$).

For $\rho\in{\mathcal{P}}_{U}$, define
$W_{\rho,\rho}=\mathop{\mathbb{E}}_{y_{U_{2}}\sim{\mathcal{D}}^{U_{2}}}[v_{\rho,y_{U_{2}}}v_{\rho,y_{U_{2}}}^{T}]$
so that $H_{Id_{U},\rho,\rho}=\frac{1}{|Aut(U)|}W_{\rho,\rho}$. Observe that
$W_{\rho,\rho}=\mathop{\mathbb{E}}[v_{\rho,x_{U^{\prime}}}v_{\rho,x_{U^{\prime}}}^{T}]=\mathop{\mathbb{E}}[v_{\rho,x_{V^{\prime}}}v_{\rho,x_{V^{\prime}}}^{T}]$
because $x_{U^{\prime}}$ and $x_{V^{\prime}}$ are also sets of variables
sampled from ${\mathcal{D}}$ and, $U^{\prime}$, $V^{\prime}$ have the same
size as $U_{2}$ because $U_{\tau}=V_{\tau}=U$.

For $\rho,\rho^{\prime}\in{\mathcal{P}}_{U}$, define
$Y_{\rho,\rho^{\prime}}=\mathop{\mathbb{E}}\left[v_{\rho,x_{U^{\prime}}}\left(\prod_{i\in
U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}^{T}\right]$.
Then, $H_{\tau}=\sum_{\rho\in
P_{\tau}}H_{\tau,\rho,\pi(\rho)}=\frac{1}{|Aut(U)|^{2}}S(\tau)\sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}$. We have

$\displaystyle\begin{bmatrix}\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$
$\displaystyle=\frac{S(\tau)}{|Aut(U)|^{2}}\begin{bmatrix}R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}^{T}&R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}\end{bmatrix}$

Since $\frac{S(\tau)}{|Aut(U)|^{2}}\geq 0$, it suffices to prove that
$\begin{bmatrix}R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}^{T}&R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}\end{bmatrix}\succeq
0$. Consider

$\displaystyle\begin{bmatrix}R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}&\sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}\\\ \sum_{\rho\in
P_{\tau}}Y_{\rho,\pi(\rho)}^{T}&R(\tau)\sum_{\rho\in{\mathcal{P}}_{U}}W_{\rho,\rho}\end{bmatrix}=$
$\displaystyle R(\tau)\begin{bmatrix}\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}W_{\rho,\rho}&0\\\ 0&\sum_{\rho\in{\mathcal{P}}_{U}\setminus
Q_{\tau}}W_{\rho,\rho}\end{bmatrix}$
$\displaystyle+\begin{bmatrix}R(\tau)\sum_{\rho\in
P_{\tau}}W_{\rho,\rho}&\sum_{\rho\in P_{\tau}}Y_{\rho,\pi(\rho)}\\\
\sum_{\rho\in P_{\tau}}Y_{\rho,\pi(\rho)}^{T}&R(\tau)\sum_{\rho\in
P_{\tau}}W_{\pi(\rho),\pi(\rho)}\end{bmatrix}$

We have $\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}W_{\rho,\rho}=\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}\mathop{\mathbb{E}}[v_{\rho,x_{U^{\prime}}}v_{\rho,x_{U^{\prime}}}^{T}]\succeq
0$. Similarly, $\sum_{\rho\in{\mathcal{P}}_{U}\setminus
Q_{\tau}}W_{\rho,\rho}\succeq 0$. Also, $R(\tau)\geq 0$ and therefore, we have
that the first term in the above expression,
$R(\tau)\begin{bmatrix}\sum_{\rho\in{\mathcal{P}}_{U}\setminus
P_{\tau}}W_{\rho,\rho}&0\\\ 0&\sum_{\rho\in{\mathcal{P}}_{U}\setminus
Q_{\tau}}W_{\rho,\rho}\end{bmatrix}$, is positive semidefinite. For the second
term,

$\displaystyle\begin{bmatrix}R(\tau)\sum_{\rho\in
P_{\tau}}W_{\rho,\rho}&\sum_{\rho\in P_{\tau}}Y_{\rho,\pi(\rho)}\\\
\sum_{\rho\in P_{\tau}}Y_{\rho,\pi(\rho)}^{T}&R(\tau)\sum_{\rho\in
P_{\tau}}W_{\pi(\rho),\pi(\rho)}\end{bmatrix}$
$\displaystyle\qquad=\sum_{\rho\in
P_{\tau}}\begin{bmatrix}R(\tau)\mathop{\mathbb{E}}[v_{\rho,x_{U^{\prime}}}v_{\rho,x_{U^{\prime}}}^{T}]&\mathop{\mathbb{E}}\left[v_{\rho,x_{U^{\prime}}}\left(\prod_{i\in
U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}^{T}\right]\\\
\mathop{\mathbb{E}}\left[v_{\rho,x_{U^{\prime}}}^{T}\left(\prod_{i\in
U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}\right]&R(\tau)\mathop{\mathbb{E}}[v_{\pi(\rho),x_{V^{\prime}}}v_{\pi(\rho),x_{V^{\prime}}}^{T}]\end{bmatrix}$
$\displaystyle\qquad=\sum_{\rho\in
P_{\tau}}\mathop{\mathbb{E}}\begin{bmatrix}R(\tau)v_{\rho,x_{U^{\prime}}}v_{\rho,x_{U^{\prime}}}^{T}&v_{\rho,x_{U^{\prime}}}\left(\prod_{i\in
U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}^{T}\\\
v_{\rho,x_{U^{\prime}}}^{T}\left(\prod_{i\in U^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\tau}(i)}\right)v_{\pi(\rho),x_{V^{\prime}}}&R(\tau)v_{\pi(\rho),x_{V^{\prime}}}v_{\pi(\rho),x_{V^{\prime}}}^{T}\end{bmatrix}$

We will prove that the term inside the expectation is positive semidefinite
for each $\rho\in P_{\tau}$ and each sampling of the $x_{i}$ from
${\mathcal{D}}$, which will complete the proof. Fix $\rho\in P_{\tau}$ and any
sampling of the $x_{i}$ from ${\mathcal{D}}$. Let
$w_{1}=v_{\rho,X_{U^{\prime}}},w_{2}=v_{\pi(\rho),x_{V^{\prime}}}$. Let
$E=\prod_{i\in U^{\prime}\cup V^{\prime}}x_{i}^{deg^{\tau}(i)}$. We would like
to prove that $\begin{bmatrix}R(\tau)w_{1}w_{1}^{T}&Ew_{1}w_{2}^{T}\\\
Ew_{1}^{T}w_{2}&R(\tau)w_{2}w_{2}^{T}\end{bmatrix}\succeq 0$. For all $y$
sampled from ${\mathcal{D}}$, $|y|\leq C_{disc}\sqrt{D_{E}}$ and so,
$|E|\leq(C_{disc}\sqrt{D_{E}})^{\sum_{j\in U^{\prime}\cup
V^{\prime}}deg^{\tau}(j)}=R(\tau)$.

If $E\geq 0$, then

$\displaystyle\begin{bmatrix}R(\tau)w_{1}w_{1}^{T}&Ew_{1}w_{2}^{T}\\\
Ew_{1}^{T}w_{2}&R(\tau)w_{2}w_{2}^{T}\end{bmatrix}$
$\displaystyle=(R(\tau)-E)\begin{bmatrix}w_{1}w_{1}^{T}&0\\\
0&w_{2}w_{2}^{T}\end{bmatrix}+E\begin{bmatrix}w_{1}w_{1}^{T}&w_{1}w_{2}^{T}\\\
w_{1}^{T}w_{2}&w_{2}w_{2}^{T}\end{bmatrix}$
$\displaystyle=(R(\tau)-E)\left(\begin{bmatrix}w_{1}\\\
0\end{bmatrix}\begin{bmatrix}w_{1}&0\end{bmatrix}+\begin{bmatrix}0\\\
w_{2}\end{bmatrix}\begin{bmatrix}0&w_{2}\end{bmatrix}\right)+E\begin{bmatrix}w_{1}\\\
w_{2}\end{bmatrix}\begin{bmatrix}w_{1}&w_{2}\end{bmatrix}$
$\displaystyle\succeq 0$

since $R(\tau)-E\geq 0$ And if $E<0$,

$\displaystyle\begin{bmatrix}R(\tau)w_{1}w_{1}^{T}&Ew_{1}w_{2}^{T}\\\
Ew_{1}^{T}w_{2}&R(\tau)w_{2}w_{2}^{T}\end{bmatrix}$
$\displaystyle=(R(\tau)+E)\begin{bmatrix}w_{1}w_{1}^{T}&0\\\
0&w_{2}w_{2}^{T}\end{bmatrix}-E\begin{bmatrix}w_{1}w_{1}^{T}&-w_{1}w_{2}^{T}\\\
-w_{1}^{T}w_{2}&w_{2}w_{2}^{T}\end{bmatrix}$
$\displaystyle=(R(\tau)+E)\left(\begin{bmatrix}w_{1}\\\
0\end{bmatrix}\begin{bmatrix}w_{1}&0\end{bmatrix}+\begin{bmatrix}0\\\
w_{2}\end{bmatrix}\begin{bmatrix}0&w_{2}\end{bmatrix}\right)-E\begin{bmatrix}w_{1}\\\
-w_{2}\end{bmatrix}\begin{bmatrix}w_{1}&-w_{2}\end{bmatrix}$
$\displaystyle\succeq 0$

since $R(\tau)+E\geq 0$.

##### Qualitative intersection term bounds

Just as in 4.19, the next proposition captures the fact that when we compose
shapes $\sigma,\gamma,\gamma^{T},\sigma^{\prime T}$, in order for
$\lambda_{\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime T}}$ to be
nonzero, the parities of the degrees of the merged vertices should add up
correspondingly. Just as in the tensor PCA application, we similarly define
$H_{Id_{V},\rho,\rho^{\prime}}^{-\gamma,\gamma}$ and
$H^{\prime}_{\gamma,\rho,\rho}$. The following propositions are simple and
proved the same way.

######  Proposition 4.21.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for all
$\gamma\in\Gamma_{U,V}$, there exists a set of parity vectors
$P_{\gamma}\subseteq{\mathcal{P}}_{U}$ such that
$H_{Id_{V}}^{-\gamma,\gamma}=\sum_{\rho\in
P_{\gamma}}H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}$.

######  Proposition 4.22.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, for
$\gamma\in\Gamma_{U,V}$, $H_{\gamma}^{\prime}=\sum_{\rho\in
P_{\gamma}}H_{\gamma,\rho,\rho}^{\prime}$.

We will now define vectors which are truncations of $v_{\rho,x_{U_{2}}}$. This
definition and the following proposition are mostly a matter of technicality
and they are essentially similar to the PSD mass condition analysis.

######  Definition 4.23.

Let $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, and let
$\gamma\in\Gamma_{U,V}$. Let $x_{i}$ for $i\in U_{2}$ be variables. Denote
them collectively as $x_{U_{2}}$. For $\rho\in{\mathcal{P}}_{U}$, define
$v_{\rho,x_{U_{2}}}^{-\gamma}$ to be the vector indexed by left shapes
$\sigma\in{\mathcal{L}}$ such that the $\sigma$th entry is
$v_{\rho,x_{U_{2}}}(\sigma)$ if $|V(\sigma\circ\gamma)|\leq D_{V}$ and $0$
otherwise.

With this, we can decompose each slice
$H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}$.

######  Proposition 4.24.

For any $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, and for any
$\gamma\in\Gamma_{U,V}$, suppose we take $\rho\in P_{\gamma}$. When we compose
$\gamma$ with $\gamma^{T}$ to get $\gamma\circ\gamma^{T}$, let
$U^{\prime}=(U_{\gamma\circ\gamma^{T}})_{2},V^{\prime}=(V_{\gamma\circ\gamma^{T}})_{2}$
be the type $2$ vertices in
$U_{\gamma\circ\gamma^{T}},V_{\gamma\circ\gamma^{T}}$ respectively. And let
$W^{\prime}$ be the set of type $2$ vertices in $\gamma\circ\gamma^{T}$ that
were identified in the composition when we set $V_{\gamma}=U_{\gamma}^{T}$.
Let $x_{i}$ for $i\in U^{\prime}\cup W^{\prime}\cup V^{\prime}$ be random
variables independently sampled from ${\mathcal{D}}$. Define $x_{U^{\prime}}$
(resp. $x_{V^{\prime}},x_{W^{\prime}}$) to be the subset of variables $x_{i}$
for $i\in U^{\prime}$ (resp. $i\in V^{\prime},i\in W^{\prime}$). Then,

$H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}=\frac{1}{|Aut(V)|}S(\gamma)^{2}\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]$

###### Proof.

Fix $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U,\rho}$ such that
$|V(\sigma\circ\gamma)|,|V(\sigma^{\prime}\circ\gamma)|\leq D_{V}$. Note that
for $t\in\\{1,2\\}$,
$|\sigma|_{t}-\frac{|V_{\sigma}|_{t}}{2}+|\sigma^{\prime}|_{t}-\frac{|V_{\sigma^{\prime}}|_{t}}{2}+2(|\gamma|_{t}-\frac{|U_{\gamma}|_{t}+|V_{\gamma}|_{t}}{2})=|\sigma\circ\gamma\circ\gamma^{T}\circ\sigma^{\prime
T}|_{t}$. We can easily verify the equality using Definition 4.3 and
Definition 4.15.

######  Proposition 4.25.

For any $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$, and for any
$\gamma\in\Gamma_{U,V}$, suppose we take $\rho\in{\mathcal{P}}_{U}$. Then,

$H^{\prime}_{\gamma,\rho,\rho}=\frac{1}{|Aut(U)|}\mathop{\mathbb{E}}_{y_{U_{2}}\sim{\mathcal{D}}^{U_{2}}}\left[(v_{\rho,y_{U_{2}}}^{-\gamma})(v_{\rho,y_{U_{2}}}^{-\gamma})^{T}\right]$

We can finally show the qualitative intersection term bounds.

###### Proof of the qualitative intersection term bounds Lemma 4.10.

Let $U^{\prime},V^{\prime},W^{\prime}$ be defined as in 4.24. We have

$\displaystyle\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}R(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}$
$\displaystyle=\sum_{\rho\in
P_{\gamma}}\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}R(\gamma)^{2}}H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}$
$\displaystyle=\sum_{\rho\in
P_{\gamma}}\frac{1}{|Aut(U)|}\cdot\frac{1}{R(\gamma)^{2}}\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]$

We will now prove that, for all $\rho\in P_{\gamma}$,

$\displaystyle\frac{1}{|Aut(U)|}\cdot\frac{1}{R(\gamma)^{2}}\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]\preceq
H^{\prime}_{\gamma,\rho,\rho}$

which reduces to proving that

$\displaystyle\frac{2}{R(\gamma)^{2}}\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]$
$\displaystyle\preceq
2\mathop{\mathbb{E}}_{y_{U_{2}}\sim{\mathcal{D}}^{U_{2}}}\left[(v_{\rho,y_{U_{2}}}^{-\gamma})(v_{\rho,y_{U_{2}}}^{-\gamma})^{T}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}+(v_{\rho,x_{V^{\prime}}}^{-\gamma})(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]$

where the last equality followed from linearity of expectation and the fact
that $U^{\prime}\equiv V^{\prime}\equiv U_{2}$.

Since $H_{Id_{V},\rho,\rho}^{-\gamma,\gamma}$ is symmetric, we have

$\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]=\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{V^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}\right]$

So, it suffices to prove

$\displaystyle\frac{1}{R(\gamma)^{2}}$
$\displaystyle\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}+(v_{\rho,x_{V^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}\right]$
$\displaystyle\preceq\mathop{\mathbb{E}}_{x}\left[(v_{\rho,x_{U^{\prime}}}^{-\gamma})(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}+(v_{\rho,x_{V^{\prime}}}^{-\gamma})(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}\right]$

We will prove that for every sampling of the $x_{i}$ from ${\mathcal{D}}$, we
have

$\displaystyle\frac{1}{R(\gamma)^{2}}$
$\displaystyle\left((v_{\rho,x_{U^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}+(v_{\rho,x_{V^{\prime}}}^{-\gamma})\left(\prod_{i\in
U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}\right)(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}\right)$
$\displaystyle\preceq(v_{\rho,x_{U^{\prime}}}^{-\gamma})(v_{\rho,x_{U^{\prime}}}^{-\gamma})^{T}+(v_{\rho,x_{V^{\prime}}}^{-\gamma})(v_{\rho,x_{V^{\prime}}}^{-\gamma})^{T}$

Then, taking expectations will give the result. Indeed, fix a sampling of the
$x_{i}$ from ${\mathcal{D}}$. Let $E=\prod_{i\in U^{\prime}\cup W^{\prime}\cup
V^{\prime}}x_{i}^{deg^{\gamma\circ\gamma^{T}}(i)}$ and let
$w_{1}=v_{\rho,x_{U^{\prime}}}^{-\gamma},w_{2}=v_{\rho,x_{V^{\prime}}}^{-\gamma}$.
Then, the inequality we need to show is

$\frac{E}{R(\gamma)^{2}}(w_{1}w_{2}^{T}+w_{2}w_{1}^{T})\preceq
w_{1}w_{1}^{T}+w_{2}w_{2}^{T}$

Now, since $|x_{i}|\leq C_{disc}\sqrt{D_{E}}$ for all $i$, we have
$|E|\leq\prod_{i\in U^{\prime}\cup W^{\prime}\cup
V^{\prime}}(C_{disc}\sqrt{D_{E}})^{deg^{\gamma\circ\gamma^{T}}(i)}=R(\gamma)^{2}$.
If $E\geq 0$, using
$\frac{E}{R(\gamma)^{2}}(w_{1}-w_{2})(w_{1}-w_{2})^{T}\succeq 0$ gives

$\displaystyle\frac{E}{R(\gamma)^{2}}(w_{1}w_{2}^{T}+w_{2}w_{1}^{T})$
$\displaystyle\preceq\frac{E}{R(\gamma)^{2}}(w_{1}w_{1}^{T}+w_{2}w_{2}^{T})\preceq
w_{1}w_{1}^{T}+w_{2}w_{2}^{T}$

since $0\leq E\leq R(\gamma)^{2}$. And if $E<0$, using
$\frac{-E}{R(\gamma)^{2}}(w_{1}+w_{2})(w_{1}+w_{2})^{T}\succeq 0$ gives

$\displaystyle\frac{E}{R(\gamma)^{2}}(w_{1}w_{2}^{T}+w_{2}w_{1}^{T})$
$\displaystyle\preceq\frac{-E}{R(\gamma)^{2}}(w_{1}w_{1}^{T}+w_{2}w_{2}^{T})\preceq
w_{1}w_{1}^{T}+w_{2}w_{2}^{T}$

since $0\leq-E\leq R(\gamma)^{2}$. Finally, we use the fact that for all
$\rho\in{\mathcal{P}}_{U}$, we have $H^{\prime}_{\gamma,\rho,\rho}\succeq 0$
which can be proved the same way as the proof of Lemma 4.5. Therefore,

$\displaystyle\frac{|Aut(V)|}{|Aut(U)|}\cdot\frac{1}{S(\gamma)^{2}R(\gamma)^{2}}H_{Id_{V}}^{-\gamma,\gamma}$
$\displaystyle\preceq\sum_{\rho\in
P_{\gamma}}H^{\prime}_{\gamma,\rho,\rho}\preceq\sum_{\rho\in{\mathcal{P}}_{U}}H^{\prime}_{\gamma,\rho,\rho}=H^{\prime}_{\gamma}$

####  3 Intuition for quantitative bounds

In this section, we will give some intuition on the bounds needed for our main
theorem Theorem 2.3, which is formally proved in Section 3. Informally, the
theorem states that when $m\leq\frac{d}{\lambda^{2}}$ and
$m\leq\frac{k^{2}}{\lambda^{2}}$, then $\Lambda\succeq 0$ with high
probability.

We will try and understand why the inequality
$\lambda_{\sigma\circ\tau\circ\sigma^{\prime T}}^{2}\left\lVert
M_{\tau}\right\rVert^{2}\leq\lambda_{\sigma\circ\sigma^{T}}\lambda_{\sigma^{\prime}\circ\sigma^{\prime
T}}$ holds. Assume for simplicity that $d<n$ and consider the shapes in Fig.
4. The assumption $d<n$ is used in this example since otherwise, if $d>n$, the
decomposition differs from what’s shown in the figure.

Figure 4: Shapes
$\sigma\circ\tau_{1}\circ\sigma^{T},\sigma\circ\tau_{2}\circ\sigma^{T}$ and
$\sigma\circ\sigma^{T}$. All edges have label $1$.

Firstly, the shape $\sigma\circ\sigma^{T}$ has a coefficient of
$\lambda_{\sigma\circ\sigma^{T}}\approx\left(\frac{1}{\sqrt{k}}\right)^{4}\left(\frac{k}{d}\right)^{2}$.
The first shape $\sigma\circ\tau_{1}\circ\sigma^{T}$ has a coefficient of
$\lambda_{\sigma\circ\tau_{1}\circ\sigma^{T}}\approx\left(\frac{1}{\sqrt{k}}\right)^{4}\left(\frac{k}{d}\right)^{4}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{4}$
and with high probability, upto lower order terms, $\left\lVert
M_{\tau_{1}}\right\rVert\leq md$. So, the inequality
$\lambda_{\sigma\circ\tau_{1}\circ\sigma^{T}}^{2}\left\lVert
M_{\tau_{1}}\right\rVert^{2}\leq\lambda_{\sigma\circ\sigma^{T}}\lambda_{\sigma\circ\sigma^{T}}$
rearranges to $m\leq\frac{d}{\lambda^{2}}$. But this is precisely one of the
assumptions on $m$. Moreover, this also confirms that we need this assumption
on $m$ in order for our strategy to go through.

The second shape $\sigma\circ\tau_{2}\circ\sigma^{T}$ has a coefficient of
$\lambda_{\sigma\circ\tau_{2}\circ\sigma^{T}}\approx\left(\frac{1}{\sqrt{k}}\right)^{4}\left(\frac{k}{d}\right)^{4}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{8}$
and with high probability, upto lower order terms, $\left\lVert
M_{\tau_{2}}\right\rVert\leq m^{2}d$. So, the inequality
$\lambda_{\sigma\circ\tau_{2}\circ\sigma^{T}}^{2}\left\lVert
M_{\tau_{2}}\right\rVert^{2}\leq\lambda_{\sigma\circ\sigma^{T}}\lambda_{\sigma\circ\sigma^{T}}$
rearranges to $m^{2}\leq\frac{k^{2}d}{\lambda^{4}}$. But this is obtained
simply by multiplying our assumptions on $m$, namely
$m\leq\frac{k^{2}}{\lambda^{2}}$ and $m\leq\frac{d}{\lambda^{2}}$.

Moreover, consider a shape of the form $\sigma\circ\tau_{3}\circ\sigma^{T}$
where $\tau_{3}$ is similar to $\tau_{2}$ except it has $t$ (instead of $3$)
different circle vertices that are common neighbors to the top 2 square
vertices. Analyzing our required inequality, we get for our strategy to go
through, $m$ has to satisfy
$m\leq\frac{k^{2}}{\lambda^{2}}\cdot\left(\frac{d}{k^{2}}\right)^{\frac{2}{t+1}}$.
By taking $t$ arbitrarily large, we can see that the condition
$m\leq\frac{k^{2}}{\lambda^{2}}$ is needed.

So, we get that for our analysis to go through, the assumptions
$m\leq\frac{d}{\lambda^{2}}$ and $m\leq\frac{k^{2}}{\lambda^{2}}$ are
necessary. We will prove that in fact, these are sufficient. To do this, we
use a charging argument that exploits the special structure of the shapes
$\alpha$ that appear in our decomposition of $\Lambda$ and their coefficients
$\lambda_{\alpha}$, as we obtained in Definition 4.3. For details, see Section
3.

##  Chapter 6 Quantitative bounds

In this chapter, we will prove the main Sum of Squares lower bounds Theorem
4.1, Theorem 3.3 and Theorem 2.3 by building on the qualitative bounds from
Chapter 5. The material in this chapter is adapted from
[potechin2020machinery], however several typos have been fixed and the
technical exposition has been improved.

###  1 Planted slightly denser subgraph: Full verification

In this section, we will prove our main theorem on Planted slightly denser
subgraph, Theorem 4.1.

See 4.1

We will apply the machinery. Here, we choose $\varepsilon$ in the theorem, not
to be confused with the $\varepsilon$ in Theorem 4.1, to be an arbitrarily
small constant. We build on the qualitative bounds (and use the same notation)
from Section 2. The result will follow once we verify the main conditions and
apply the machinery.

####  1 Middle shape bounds

######  Lemma 1.1.

Suppose $k\leq n^{1/2-\varepsilon}$. For all $U\in{\mathcal{I}}_{mid}$ and
$\tau\in{\mathcal{M}}_{U}$,

$\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)\leq\frac{1}{n^{C_{p}\varepsilon|E(\tau)|}}$

###### Proof.

This result follows by plugging in the value of $S(\tau)$. Using $k\leq
n^{1/2-\varepsilon}$,

$\displaystyle\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$
$\displaystyle=\sqrt{n}^{|V(\tau)|-|U_{\tau}|}\left(\frac{k}{n}\right)^{|V(\tau)|-|U_{\tau}|}(2(\frac{1}{2}+\frac{1}{2n^{C_{p}\varepsilon}})-1)^{|E(\tau)|}\leq\frac{1}{n^{C_{p}\varepsilon|E(\tau)|}}$

######  Corollary 1.2.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, we have

$c(\tau)B_{norm}(\tau)S(\tau)\leq 1$

###### Proof.

Since $\tau$ is a proper middle shape, we have $w(I_{\tau})=0$ and
$w(S_{\tau})=w(U_{\tau})$. This implies
$n^{\frac{w(V(\tau))+w(I_{\tau})-w(S_{\tau})}{2}}=\sqrt{n}^{|V(\tau)|-|U_{\tau}|}$.
Since $\tau$ is proper, every vertex $i\in V(\tau)\setminus U_{\tau}$ or $i\in
V(\tau)\setminus V_{\tau}$ has $deg^{\tau}(i)\geq 1$ and hence,
$|V(\tau)\setminus U_{\tau}|+|V(\tau)\setminus V_{\tau}|\leq 4|E(\tau)|$.
Also, $q=n^{O(1)\cdot\varepsilon C_{V}}$. We can set $C_{V}$ sufficiently
small so that, using Lemma 1.1,

$\displaystyle c(\tau)$ $\displaystyle B_{norm}(\tau)S(\tau)$
$\displaystyle=100(3D_{V})^{|U_{\tau}\setminus V_{\tau}|+|V_{\tau}\setminus
U_{\tau}|+2|E(\tau)|}2^{|V(\tau)\setminus(U_{\tau}\cup
V_{\tau})|}\cdot(6D_{V}\sqrt[4]{2eq})^{|V(\tau)\setminus
U_{\tau}|+|V(\tau)\setminus V_{\tau}|}\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$
$\displaystyle\leq n^{O(1)\cdot\varepsilon
C_{V}\cdot|E(\tau)|}\cdot\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$
$\displaystyle\leq n^{O(1)\cdot\varepsilon
C_{V}\cdot|E(\tau)|}\cdot\frac{1}{n^{C_{p}\varepsilon|E(\tau)|}}$
$\displaystyle\leq 1$

We can now obtain middle shape bounds.

######  Lemma 1.3.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,

$\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}\succeq
0$

###### Proof.

We have

$\displaystyle\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}$
$\displaystyle\qquad=\begin{bmatrix}\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}&0\\\
0&\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}\end{bmatrix}$
$\displaystyle\qquad\qquad+B_{norm}(\tau)\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$

By Lemma 2.7, $\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$, so the
second term above is positive semidefinite. For the first term, by Lemma 2.5,
$H_{Id_{U}}\succeq 0$ and by Corollary 1.2,
$\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\geq 0$,
which proves that the first term is also positive semidefinite.

####  2 Intersection term bounds

######  Lemma 1.4.

Suppose $k\leq n^{1/2-\varepsilon}$. For all $U,V\in{\mathcal{I}}_{mid}$ where
$w(U)>w(V)$ and for all $\gamma\in\Gamma_{U,V}$,

$n^{w(V(\gamma)\setminus
U_{\gamma})}S(\gamma)^{2}\leq\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+|E(\gamma)|)}}$

for some constant $B$ that depends only on $C_{p}$. In particular, it is
independent of $C_{V}$.

###### Proof.

Since $\gamma$ is a left shape, we have $|U_{\gamma}|\geq|V_{\gamma}|$ as
$V_{\gamma}$ is the unique minimum vertex separator of $\gamma$ and so,
$n^{w(V(\gamma)\setminus U_{\gamma})}=n^{|V(\gamma)|-|U_{\gamma}|}\leq
n^{|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2}}$. Also, note that
$2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|=|U_{\gamma}\setminus
V_{\gamma}|+|V_{\gamma}\setminus U_{\gamma}|+2|V(\gamma)\setminus
U_{\gamma}\setminus V_{\gamma}|\geq|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|$. Therefore,

$\displaystyle n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}$
$\displaystyle=n^{|V(\gamma)\setminus
U_{\gamma})|}\left(\frac{k}{n}\right)^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}(2(\frac{1}{2}+\frac{1}{2n^{C_{p}\varepsilon}})-1)^{2|E(\gamma)|}$
$\displaystyle\leq
n^{|V(\gamma)|-\frac{|U_{\gamma}|+|V_{\gamma}|}{2}}\left(\frac{1}{n^{1/2+\varepsilon}}\right)^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}\left(\frac{1}{n^{2C_{p}\varepsilon}}\right)^{|E(\gamma)|}$
$\displaystyle\leq\left(\frac{1}{n^{\varepsilon}}\right)^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}\left(\frac{1}{n^{2C_{p}\varepsilon}}\right)^{|E(\gamma)|}$
$\displaystyle\leq\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

for a constant $B$ that depends only on $C_{p}$.

We obtain intersection term bounds.

######  Lemma 1.5.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}\preceq
H_{\gamma}^{\prime}$

###### Proof.

By Lemma 2.8, we have

$\displaystyle
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}$
$\displaystyle=c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}H^{\prime}_{\gamma}$

Using the same proof as in Lemma 2.5, we can see that
$H^{\prime}_{\gamma}\succeq 0$. Therefore, it suffices to prove that
$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}\leq
1$. Since $U,V\in{\mathcal{I}}_{mid}$, $|Aut(U)|=|U|!,|Aut(V)|=|V|!$.
Therefore, $\frac{|Aut(U)|}{|Aut(V)|}=\frac{|U|!}{|V|!}\leq
D_{V}^{|U_{\gamma}\setminus V_{\gamma}|}$. Also, $q=n^{O(1)\cdot\varepsilon
C_{V}}$. Let $B$ be the constant from Lemma 1.4. We can set $C_{V}$
sufficiently small so that, using Lemma 1.4,

$\displaystyle
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}$
$\displaystyle\leq 100^{2}(3D_{V})^{2|U_{\gamma}\setminus
V_{\gamma}|+2|V_{\gamma}\setminus
U_{\gamma}|+4|E(\alpha)|}4^{|V(\gamma)\setminus(U_{\gamma}\cup V_{\gamma})|}$
$\displaystyle\quad\cdot(3D_{V})^{4|V(\gamma)\setminus
V_{\gamma}|+2|V(\gamma)\setminus
U_{\gamma}|}(6D_{V}\sqrt[4]{2eq})^{2|V(\gamma)\setminus
U_{\gamma}|+2|V(\gamma)\setminus V_{\gamma}|}$ $\displaystyle\quad\cdot
n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}\cdot
D_{V}^{|U_{\gamma}\setminus V_{\gamma}|}$ $\displaystyle\leq
n^{O(1)\cdot\varepsilon C_{V}\cdot(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}\cdot n^{w(V(\gamma)\setminus
U_{\gamma})}S(\gamma)^{2}$ $\displaystyle\leq n^{O(1)\cdot\varepsilon
C_{V}\cdot(|V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})|+\sum_{e\in
E(\gamma)}l_{e})}\cdot\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$ $\displaystyle\leq 1$

####  3 Truncation error bounds

In this section, we will prove truncation error bounds. We use the strategy
and notation from [potechin2020machinery, Section 10]. First, we will need a
bound on
$B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})$
that is obtained below.

######  Lemma 1.6.

Suppose $k\leq n^{1/2-\varepsilon}$. For all $U\in{\mathcal{I}}_{mid}$ and
$\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}$,

$B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})\leq\frac{1}{n^{0.5\varepsilon|V(\alpha)|+C_{p}\varepsilon|E(\alpha)|}}\left(\frac{k}{n}\right)^{|U|}$

###### Proof.

Let $\alpha=\sigma\circ\sigma^{\prime}$. Observe that
$|V(\sigma)|+|V(\sigma^{\prime})|=|V(\alpha)|+|U|$. By choosing $C_{V}$
sufficiently small,

$\displaystyle
B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})$
$\displaystyle=(6D_{V}\sqrt[4]{2eq})^{|V(\sigma)\setminus
U_{\sigma}|+|V(\sigma)\setminus V_{\sigma}|}n^{\frac{w(V(\sigma))-w(U)}{2}}$
$\displaystyle\quad\cdot(6D_{V}\sqrt[4]{2eq})^{|V(\sigma^{\prime})\setminus
U_{\sigma^{\prime}}|+|V(\sigma^{\prime})\setminus
V_{\sigma^{\prime}}|}n^{\frac{w(V(\sigma^{\prime}))-w(U)}{2}}$
$\displaystyle\quad\cdot\frac{1}{|Aut(U)|}\left(\frac{k}{n}\right)^{|V(\alpha)|}(2(\frac{1}{2}+\frac{1}{2n^{C_{p}\varepsilon}})-1)^{|E(\alpha)|}$
$\displaystyle\leq n^{O(1)\cdot\varepsilon
C_{V}\cdot|V(\alpha)|}\sqrt{n}^{|V(\sigma)|-|U|}\sqrt{n}^{|V(\sigma^{\prime})|-|U|}\left(\frac{k}{n}\right)^{|V(\alpha)|}\frac{1}{n^{C_{p}\varepsilon|E(\alpha)|}}$
$\displaystyle\leq\frac{1}{n^{0.5\varepsilon|V(\alpha)|+C_{p}\varepsilon|E(\alpha)|}}\left(\frac{k}{n}\right)^{|U|}$

Now, we are ready to apply the strategy.

######  Lemma 1.7.

Whenever $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in{\mathcal{M}}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq\frac{1}{n^{K_{1}D_{sos}^{2}}}Id_{sym}$

for a constant $K_{1}>0$.

###### Proof.

For $V\in{\mathcal{I}}_{mid}$, we have
$\lambda_{V}=\left(\frac{k}{n}\right)^{|V|}$. Now, we choose
$w_{V}=\left(\frac{k}{n}\right)^{D_{sos}-|V|}$. Then, for all
$\sigma\in{\mathcal{L}}_{V}$, we have
$w_{V}\leq\frac{w_{U_{\sigma}}\lambda_{U_{\sigma}}}{|\mathcal{I}_{mid}|B_{norm}(\sigma)^{2}{c(\sigma)^{2}}{H_{Id_{V}}(\sigma,\sigma)}}$
which is easily verified using Lemma 1.6. The result now follows.

######  Lemma 1.8.

$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}\leq\frac{n^{K_{2}D_{sos}}}{2^{D_{V}}}$

for a constant $K_{2}>0$.

###### Proof.

We have

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle=\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{1}{|Aut(U)|c(\gamma)}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}_{U_{\gamma}}:|V(\sigma)|\leq
D_{V},|V(\sigma^{\prime})|\leq D_{V},\atop|V(\sigma\circ\gamma)|>D_{V}\text{
or
}|V(\sigma^{\prime}\circ\gamma)|>D_{V}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U_{\gamma}}}(\sigma,\sigma^{\prime})}$

The set of $\sigma,\sigma^{\prime}$ that could appear in the above sum must
necessarily be non-trivial and hence,
$\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}^{\prime}$. Then,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle=\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})}\sum_{\gamma\in\Gamma_{U,*}:|V(\sigma\circ\gamma)|>D_{V}\text{
or }|V(\sigma^{\prime}\circ\gamma)|>D_{V}}\frac{1}{|Aut(U)|c(\gamma)}$

For $\sigma\in{\mathcal{L}}^{\prime}_{U}$, define
$m_{\sigma}=D_{V}+1-|V(\sigma)|\geq 1$. This is precisely set so that for all
$\gamma\in\Gamma_{U,*}$, we have $|V(\sigma\circ\gamma)|>D_{V}$ if and only if
$|V(\gamma)|\geq|U|+m_{\sigma}$. So, for
$\sigma,\sigma^{\prime}\in{\mathcal{L}}^{\prime}_{U}$,

$\displaystyle\sum_{\gamma\in\Gamma_{U,*}:|V(\sigma\circ\gamma)|>D_{V}\text{
or }|V(\sigma^{\prime}\circ\gamma)|>D_{V}}$
$\displaystyle\frac{1}{|Aut(U)|c(\gamma)}$
$\displaystyle=\sum_{\gamma\in\Gamma_{U,*}:|V(\gamma)|\geq|U|+\min(m_{\sigma},m_{\sigma^{\prime}})}\frac{1}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\frac{1}{2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$

Also, for $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}^{\prime}$, we have
$|V(\sigma\circ\sigma^{\prime})|+min(m_{\sigma},m_{\sigma^{\prime}})-1\geq
D_{V}$. Therefore,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}$
$\displaystyle\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})\frac{1}{2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{n^{O(1)D_{sos}}}{n^{0.5\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$

where we used Lemma 1.6. Using
$n^{0.5\varepsilon|V(\sigma\circ\sigma^{\prime})|}\geq
n^{0.1\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{|V(\sigma\circ\sigma^{\prime})|}$,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{n^{O(1)D_{sos}}}{n^{0.1\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{|V(\sigma\circ\sigma^{\prime})|}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{n^{O(1)D_{sos}}}{n^{0.1\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{D_{V}}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{n^{O(1)D_{sos}}}{D_{sos}^{D_{sos}}n^{0.1\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{D_{V}}}$

The final step will be to argue that
$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{D_{sos}^{D_{sos}}n^{0.1\varepsilon|V(\sigma\circ\sigma^{\prime})|}}\leq
1$ which will complete the proof. But this will follow if we set $C_{V}$ small
enough.

We conclude the following.

######  Lemma 1.9.

Whenever $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in\mathcal{M}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

###### Proof.

Choose $C_{sos}$ sufficiently small so that
$\frac{1}{n^{K_{1}D_{sos}^{2}}}\geq 6\frac{n^{K_{2}D_{sos}}}{2^{D_{V}}}$ which
can be satisfied by setting $C_{sos}<K_{3}C_{V}$ for a sufficiently small
constant $K_{3}>0$. Then, since $Id_{Sym}\succeq 0$, using Lemma 1.7 and Lemma
1.8,

$\displaystyle\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}$
$\displaystyle\succeq\frac{1}{n^{K_{1}D_{sos}^{2}}}Id_{sym}$
$\displaystyle\succeq 6\frac{n^{K_{2}D_{sos}}}{2^{D_{V}}}Id_{sym}$
$\displaystyle\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

###  2 Tensor PCA: Full verification

In this section, we will prove all the bounds required to prove Theorem 3.3.

See 3.3

We reuse the notation and qualitative bounds from Section 3. Once we verify
the conditions, this theorem will simply follow from the machinery.

####  1 Middle shape bounds

######  Lemma 2.1.

Suppose $\lambda\leq n^{\frac{k}{4}-\varepsilon}$. For all
$U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, suppose
$deg^{\tau}(i)$ is even for all $i\in V(\tau)\setminus U_{\tau}\setminus
V_{\tau}$, then

$\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)\leq\frac{1}{n^{0.5\varepsilon\sum_{e\in
E(\tau)}l_{e}}}$

###### Proof.

Firstly, we claim that $\sum_{e\in E(\tau)}kl_{e}\geq
2(|V(\tau)|-|U_{\tau}|)$. For any vertex $i\in V(\tau)\setminus
U_{\tau}\setminus V_{\tau}$, $deg^{\tau}(i)$ is even and is not $0$, hence,
$deg^{\tau}(i)\geq 2$. Any vertex $i\in U_{\tau}\setminus V_{\tau}$ cannot
have $deg^{\tau}(i)=0$ otherwise $U_{\tau}\setminus\\{i\\}$ is a vertex
separator of strictly smaller weight than $U_{\tau}$, which is not possible,
hence, $deg^{\tau}(i)\geq 1$. Therefore,

$\displaystyle\sum_{e\in E(\tau)}kl_{e}=\sum_{i\in V(\tau)}deg^{\tau}(i)$
$\displaystyle\geq\sum_{i\in V(\tau)\setminus U_{\tau}\setminus
V_{\tau}}deg^{\tau}(i)+\sum_{i\in U_{\tau}\setminus
V_{\tau}}deg^{\tau}(i)+\sum_{i\in V_{\tau}\setminus U_{\tau}}deg^{\tau}(i)$
$\displaystyle\geq 2|V(\tau)\setminus U_{\tau}\setminus
V_{\tau}|+|U_{\tau}\setminus V_{\tau}|+|V_{\tau}\setminus U_{\tau}|$
$\displaystyle=2(|V(\tau)|-|U_{\tau}|)$

By choosing $C_{\Delta}$ sufficiently small, we have

$\displaystyle\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$
$\displaystyle=\sqrt{n}^{|V(\tau)|-|U_{\tau}|}\Delta^{|V(\tau)|-|U_{\tau}|}\prod_{e\in
E(\tau)}\left(\frac{\lambda}{(\Delta n)^{\frac{k}{2}}}\right)^{l_{e}}$
$\displaystyle\leq\sqrt{n}^{|V(\tau)|-|U_{\tau}|}\Delta^{|V(\tau)|-|U_{\tau}|}\prod_{e\in
E(\tau)}n^{(-\frac{k}{4}-0.5\varepsilon)l_{e}}$
$\displaystyle=\sqrt{n}^{|V(\tau)|-|U_{\tau}|-\frac{\sum_{e\in
E(\tau)}kl_{e}}{2}}\Delta^{|V(\tau)|-|U_{\tau}|}\prod_{e\in
E(\tau)}n^{-0.5\varepsilon l_{e}}$
$\displaystyle=\Delta^{|V(\tau)|-|U_{\tau}|}\prod_{e\in
E(\tau)}n^{-0.5\varepsilon l_{e}}$
$\displaystyle\leq\frac{1}{n^{0.5\varepsilon\sum_{e\in E(\tau)}l_{e}}}$

######  Corollary 2.2.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, we have

$c(\tau)B_{norm}(\tau)S(\tau)\leq 1$

###### Proof.

Since $\tau$ is a proper middle shape, we have $w(I_{\tau})=0$ and
$w(S_{\tau,min})=w(U_{\tau})$. This implies
$n^{\frac{w(V(\tau))+w(I_{\tau})-w(S_{\tau,min})}{2}}=\sqrt{n}^{|V(\tau)|-|U_{\tau}|}$.
If $deg^{\tau}(i)$ is odd for any vertex $i\in V(\tau)\setminus
U_{\tau}\setminus V_{\tau}$, then $S(\tau)=0$ and the inequality is true. So,
assume $deg^{\tau}(i)$ is even for all $i\in V(\tau)\setminus
U_{\tau}\setminus V_{\tau}$. As was observed in the proof of Lemma 2.1, every
vertex $i\in V(\tau)\setminus U_{\tau}$ or $i\in V(\tau)\setminus V_{\tau}$
has $deg^{\tau}(i)\geq 1$ and hence, $|V(\tau)\setminus
U_{\tau}|+|V(\tau)\setminus V_{\tau}|\leq 4\sum_{e\in E(\tau)}l_{e}$. Also,
$|E(\tau)|\leq\sum_{e\in E(\tau)}l_{e}$ and
$q=n^{O(1)\cdot\varepsilon(C_{V}+C_{E})}$. We can set $C_{V},C_{E}$
sufficiently small so that, using Lemma 2.1,

$\displaystyle c(\tau)B_{norm}(\tau)S(\tau)$
$\displaystyle=100(3D_{V})^{|U_{\tau}\setminus V_{\tau}|+|V_{\tau}\setminus
U_{\tau}|+k|E(\tau)|}2^{|V(\tau)\setminus(U_{\tau}\cup V_{\tau})|}$
$\displaystyle\quad\cdot 2e(6qD_{V})^{|V(\tau)\setminus
U_{\tau}|+|V(\tau)\setminus V_{\tau}|}\prod_{e\in
E(\tau)}(400D_{V}^{2}D_{E}^{2}q)^{l_{e}}\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$
$\displaystyle\leq n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot\sum_{e\in
E(\tau)}l_{e}}\cdot\sqrt{n}^{|V(\tau)|-|U_{\tau}|}S(\tau)$ $\displaystyle\leq
n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot\sum_{e\in
E(\tau)}l_{e}}\cdot\frac{1}{n^{0.5\varepsilon\sum_{e\in E(\tau)}l_{e}}}$
$\displaystyle\leq 1$

We can now show middle shape bounds.

######  Lemma 2.3.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,

$\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}\succeq
0$

###### Proof.

We have

$\displaystyle\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}$
$\displaystyle\qquad=\begin{bmatrix}\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}&0\\\
0&\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}\end{bmatrix}$
$\displaystyle\qquad\qquad+B_{norm}(\tau)\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$

By Lemma 3.8, $\begin{bmatrix}\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$, so the
second term above is positive semidefinite. For the first term, by Lemma 3.6,
$H_{Id_{U}}\succeq 0$ and by Corollary 2.2,
$\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)B_{norm}(\tau)}{|Aut(U)|}\geq 0$,
which proves that the first term is also positive semidefinite.

####  2 Intersection term bounds

######  Lemma 2.4.

Suppose $\lambda\leq n^{\frac{k}{4}-\varepsilon}$. For all
$U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and for all
$\gamma\in\Gamma_{U,V}$,

$n^{w(V(\gamma)\setminus
U_{\gamma})}S(\gamma)^{2}\leq\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

for some constant $B$ that depends only on $C_{\Delta}$. In particular, it is
independent of $C_{V}$ and $C_{E}$.

###### Proof.

Suppose there is a vertex $i\in V(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}$ such that $deg^{\gamma}(i)$ is odd, then $S(\gamma)=0$ and the
inequality is true. So, assume $deg^{\gamma}(i)$ is even for all vertices
$i\in V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$. We first claim that
$k\sum_{e\in E(\gamma)}l_{e}\geq 2|V(\gamma)\setminus U_{\gamma}|$. Since
$\gamma$ is a left shape, all vertices $i$ in $V(\gamma)\setminus U_{\gamma}$
have $deg^{\gamma}(i)\geq 1$. In particular, all vertices $i\in
V_{\gamma}\setminus U_{\gamma}$ have $deg^{\gamma}(i)\geq 1$. Moreover, if
$i\in V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$, since
$deg^{\gamma}(i)$ is even, we must have $deg^{\gamma}(i)\geq 2$.

Let $S^{\prime}$ be the set of vertices $i\in U_{\gamma}\setminus V_{\gamma}$
that have $deg^{\gamma}(i)\geq 1$. Then, note that
$|S^{\prime}|+|U_{\gamma}\cap
V_{\gamma}|\geq|V_{\gamma}|\Longrightarrow|S^{\prime}|\geq|V_{\gamma}\setminus
U_{\gamma}|$ since otherwise $S^{\prime}\cup(U_{\gamma}\cap V_{\gamma})$ will
be a vertex separator of $\gamma$ of weight strictly less than $V_{\gamma}$,
which is not possible. Then,

$\displaystyle\sum_{e\in E(\gamma)}kl_{e}$ $\displaystyle=\sum_{i\in
V(\gamma)}deg^{\gamma}(i)$ $\displaystyle\geq\sum_{i\in V(\gamma)\setminus
U_{\gamma}\setminus V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in U_{\gamma}\setminus
V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in V_{\gamma}\setminus
U_{\gamma}}deg^{\gamma}(i)$ $\displaystyle\geq 2|V(\gamma)\setminus
U_{\gamma}\setminus V_{\gamma}|+|S^{\prime}|+|V_{\gamma}\setminus U_{\gamma}|$
$\displaystyle\geq 2|V(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}|+2|V_{\gamma}\setminus U_{\gamma}|$
$\displaystyle=2|V(\gamma)\setminus U_{\gamma}|$

Finally, note that
$2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|=|U_{\gamma}\setminus
V_{\gamma}|+|V_{\gamma}\setminus U_{\gamma}|+2|V(\gamma)\setminus
U_{\gamma}\setminus V_{\gamma}|\geq|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|$. By choosing $C_{\Delta}$ sufficiently small, we have

$\displaystyle n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}$
$\displaystyle=n^{|V(\gamma)\setminus
U_{\gamma})|}\Delta^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}\prod_{e\in
E(\gamma)}\left(\frac{\lambda^{2}}{(\Delta n)^{k}}\right)^{l_{e}}$
$\displaystyle\leq n^{|V(\gamma)\setminus
U_{\gamma})|}\Delta^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}\prod_{e\in
E(\gamma)}n^{-(\frac{k}{2}+\varepsilon)l_{e}}$
$\displaystyle\leq\Delta^{2|V(\gamma)|-|U_{\gamma}|-|V_{\gamma}|}\prod_{e\in
E(\gamma)}n^{-\varepsilon l_{e}}$
$\displaystyle\leq\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

for a constant $B$ that depends only on $C_{\Delta}$.

######  Remark 2.5.

In the above bounds, note that there is a decay of $n^{B\varepsilon}$ for each
vertex in $V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})$. One of the main
technical reasons for introducing the slack parameter $C_{\Delta}$ in the
planted distribution was to introduce this decay, which is needed in the
current machinery.

We can now obtain the intersection term bounds.

######  Lemma 2.6.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}\preceq
H_{\gamma}^{\prime}$

###### Proof.

By Lemma 3.9, we have

$\displaystyle
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}$
$\displaystyle\preceq
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}H^{\prime}_{\gamma}$

Using the same proof as in Lemma 3.6, we can see that
$H^{\prime}_{\gamma}\succeq 0$. Therefore, it suffices to prove that
$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}\leq
1$. Since $U,V\in{\mathcal{I}}_{mid}$, $|Aut(U)|=|U|!,|Aut(V)|=|V|!$.
Therefore, $\frac{|Aut(U)|}{|Aut(V)|}=\frac{|U|!}{|V|!}\leq
D_{V}^{|U_{\gamma}\setminus V_{\gamma}|}$. Also, $|E(\gamma)|\leq\sum_{e\in
E(\gamma)}l_{e}$ and $q=n^{O(1)\cdot\varepsilon(C_{V}+C_{E})}$. Let $B$ be the
constant from Lemma 2.4. We can set $C_{V},C_{E}$ sufficiently small so that,
using Lemma 2.4,

$\displaystyle c(\gamma)^{2}$ $\displaystyle
N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}$
$\displaystyle\leq 100^{2}(3D_{V})^{2|U_{\gamma}\setminus
V_{\gamma}|+2|V_{\gamma}\setminus
U_{\gamma}|+2k|E(\alpha)|}4^{|V(\gamma)\setminus(U_{\gamma}\cup V_{\gamma})|}$
$\displaystyle\quad\cdot(3D_{V})^{4|V(\gamma)\setminus
V_{\gamma}|+2|V(\gamma)\setminus U_{\gamma}|}(6qD_{V})^{2|V(\gamma)\setminus
U_{\gamma}|+2|V(\gamma)\setminus V_{\gamma}|}\prod_{e\in
E(\gamma)}(400D_{V}^{2}D_{E}^{2}q)^{2l_{e}}$ $\displaystyle\quad\cdot
n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}\cdot
D_{V}^{|U_{\gamma}\setminus V_{\gamma}|}$ $\displaystyle\leq
n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}\cdot n^{w(V(\gamma)\setminus
U_{\gamma})}S(\gamma)^{2}$ $\displaystyle\leq
n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in
E(\gamma)}l_{e})}\cdot\frac{1}{n^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$ $\displaystyle\leq 1$

####  3 Truncation error bounds

In this section, we will obtain the truncation error bounds using the strategy
sketched in section 10 of [potechin2020machinery]. We also reuse the notation.
First, we need the following bound on
$B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})$.

######  Lemma 2.7.

Suppose $\lambda=n^{\frac{k}{4}-\varepsilon}$. For all
$U\in{\mathcal{I}}_{mid}$ and $\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}$,

$B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})\leq\frac{1}{n^{0.5\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}n^{|U|}}$

###### Proof.

Suppose there is a vertex $i\in V(\sigma)\setminus V_{\sigma}$ such that
$deg^{\sigma}(i)+deg^{U_{\sigma}}(i)$ is odd, then
$H_{Id_{U}}(\sigma,\sigma^{\prime})=0$ and the inequality is true. So, assume
that $deg^{\sigma}(i)+deg^{U_{\sigma}}(i)$ is even for all $i\in
V(\sigma)\setminus V_{\sigma}$. Similarly, assume that
$deg^{\sigma^{\prime}}(i)+deg^{U_{\sigma^{\prime}}}(i)$ is even for all $i\in
V(\sigma^{\prime})\setminus V_{\sigma^{\prime}}$. Also, if
$\rho_{\sigma}\neq\rho_{\sigma^{\prime}}$, we will have
$H_{Id_{U}}(\sigma,\sigma^{\prime})=0$ and we’d be done. So, assume
$\rho_{\sigma}=\rho_{\sigma^{\prime}}$.

Let $\alpha=\sigma\circ\sigma^{\prime}$. We will first prove that $\sum_{e\in
E(\alpha)}kl_{e}+2deg(\alpha)\geq 2|V(\alpha)|+2|U|$. Firstly, note that all
vertices $i\in V(\alpha)\setminus(U_{\alpha}\cup V_{\alpha})$ have
$deg^{\alpha}(i)$ to be even and nonzero, and hence at least $2$. Moreover, in
both the sets $U_{\alpha}\setminus(U_{\alpha}\cap V_{\alpha})$ and
$V_{\alpha}\setminus(U_{\alpha}\cap V_{\alpha})$, there are at least
$|U|-|U_{\alpha}\cap V_{\alpha}|$ vertices of degree at least $1$, because $U$
is a minimum vertex separator. Also, note that
$deg(\alpha)\geq|U_{\alpha}|+|V_{\alpha}|$. This implies that

$\displaystyle\sum_{e\in E(\alpha)}kl_{e}$ $\displaystyle+2deg(\alpha)$
$\displaystyle\geq 2|V(\alpha)\setminus(U_{\alpha}\cup
V_{\alpha})|+2(|U|-|U_{\alpha}\cap V_{\alpha}|)+2(|U_{\alpha}|+|V_{\alpha}|)$
$\displaystyle=2(|V(\alpha)|-|U_{\alpha}\cup
V_{\alpha}|)+2(|U|-|U_{\alpha}\cap V_{\alpha}|)+2(|U_{\alpha}\cup
V_{\alpha}|+|U_{\alpha}\cap V_{\alpha}|)$ $\displaystyle=2|V(\alpha)|+2|U|$

where we used the fact that $U_{\alpha}\cap V_{\alpha}\subseteq U$. Finally,
by choosing $C_{V},C_{E}$ sufficiently small,

$\displaystyle
B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})$
$\displaystyle=2e(6qD_{V})^{|V(\sigma)\setminus
U_{\sigma}|+|V(\sigma)\setminus V_{\sigma}|}\prod_{e\in
E(\sigma)}(400D_{V}^{2}D_{E}^{2}q)^{l_{e}}n^{\frac{w(V(\sigma))-w(U)}{2}}$
$\displaystyle\quad\cdot 2e(6qD_{V})^{|V(\sigma^{\prime})\setminus
U_{\sigma^{\prime}}|+|V(\sigma^{\prime})\setminus
V_{\sigma^{\prime}}|}\prod_{e\in
E(\sigma^{\prime})}(400D_{V}^{2}D_{E}^{2}q)^{l_{e}}n^{\frac{w(V(\sigma^{\prime}))-w(U)}{2}}$
$\displaystyle\quad\cdot\frac{1}{|Aut(U)|}\Delta^{|V(\alpha)|}\left(\frac{1}{\sqrt{\Delta
n}}\right)^{deg(\alpha)}\prod_{e\in E(\alpha)}\left(\frac{\lambda}{(\Delta
n)^{\frac{k}{2}}}\right)^{l_{e}}$ $\displaystyle\leq
n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot(|V(\alpha)|+\sum_{e\in
E(\alpha)}l_{e})}\Delta^{|V(\alpha)|}\left(\frac{1}{\sqrt{\Delta}}\right)^{deg(\alpha)}$
$\displaystyle\quad\cdot\sqrt{n}^{|V(\alpha)|-|U|}\left(\frac{1}{\sqrt{n}}\right)^{deg(\alpha)}\prod_{e\in
E(\alpha)}n^{(-\frac{k}{4}-0.5\varepsilon)l_{e}}$
$\displaystyle\leq\frac{n^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot(|V(\alpha)|+\sum_{e\in
E(\alpha)}l_{e})}}{n^{\varepsilon
C_{\Delta}|V(\alpha)|}n^{0.5\varepsilon\sum_{e\in
E(\alpha)}l_{e}}}\cdot\frac{1}{\Delta^{D_{sos}}n^{|U|}}\sqrt{n}^{|V(\alpha)|+|U|-deg(\alpha)-\frac{1}{2}\sum_{e\in
E(\alpha)}kl_{e}}$ $\displaystyle\leq\frac{1}{n^{0.5\varepsilon
C_{\Delta}|V(\alpha)|}\Delta^{D_{sos}}n^{|U|}}$

where we used the facts $\Delta\leq 1,deg(\alpha)\leq 2D_{sos}$.

We now apply the strategy by showing the following bounds.

######  Lemma 2.8.

Whenever $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in{\mathcal{M}}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq\frac{\Delta^{2D_{sos}^{2}}}{n^{D_{sos}}}Id_{sym}$

###### Proof.

For $V\in{\mathcal{I}}_{mid}$, $\lambda_{V}=\frac{1}{n^{|V|}}$. We then choose
$w_{V}=\left(\frac{1}{n}\right)^{D_{sos}-|V|}$. For all left shapes
$\sigma\in{\mathcal{L}}_{V}$, it’s easy to verify
$w_{V}\leq\frac{w_{U_{\sigma}}\lambda_{U_{\sigma}}}{|\mathcal{I}_{mid}|B_{norm}(\sigma)^{2}{c(\sigma)^{2}}{H_{Id_{V}}(\sigma,\sigma)}}$
using Lemma 2.7. This completes the proof.

######  Lemma 2.9.

$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}\leq\frac{1}{\Delta^{2D_{sos}}2^{D_{V}}}$

###### Proof.

We use the same argument and notation as in Lemma 1.8. When we plug in the
bounds, we get

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}$
$\displaystyle\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})\frac{1}{2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{n^{0.5\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}n^{|U|}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{n^{0.5\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$

where we used Lemma 2.7. Using
$n^{0.5C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\geq n^{0.1\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}2^{|V(\sigma\circ\sigma^{\prime})|}$,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}$
$\displaystyle\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{n^{0.1\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}2^{|V(\sigma\circ\sigma^{\prime})|}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{n^{0.1\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{D_{sos}}2^{D_{V}}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{D_{sos}^{D_{sos}}n^{0.1\varepsilon
C_{\Delta}|V(\sigma\circ\sigma^{\prime})|}\Delta^{2D_{sos}}2^{D_{V}}}$

where we set $C_{sos}$ small enough so that $D_{sos}=n^{\varepsilon
C_{sos}}\leq n^{c\varepsilon C_{\Delta}}=\frac{1}{\Delta}$. The final step
will be to argue that
$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{D_{sos}^{D_{sos}}n^{0.1C_{\Delta}\varepsilon|V(\sigma\circ\sigma^{\prime})|}}\leq
1$ which will complete the proof. But this will follow if we set $C_{V},C_{E}$
small enough.

We can finally complete the analysis of the truncation error.

######  Lemma 2.10.

Whenever $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in\mathcal{M}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

###### Proof.

Choose $C_{sos}$ sufficiently small so that
$\frac{\Delta^{2D_{sos}^{2}}}{n^{D_{sos}}}\geq\frac{6}{\Delta^{2D_{sos}}2^{D_{V}}}$
which is satisfied by setting $C_{sos}<0.5C_{V}$. Then, since $Id_{Sym}\succeq
0$, using Lemma 2.8 and Lemma 2.9,

$\displaystyle\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}$
$\displaystyle\succeq\frac{\Delta^{2D_{sos}^{2}}}{n^{D_{sos}}}Id_{sym}$
$\displaystyle\succeq\frac{6}{\Delta^{2D_{sos}}2^{D_{V}}}Id_{sym}$
$\displaystyle\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

###  3 Sparse PCA: Full verification

In this section, we will full prove Theorem 2.3.

See 2.3

We already showed the relevant qualitative bounds in Section 4. We use the
bounds and also the notation from that section. We will apply the machinery.

######  Definition 3.1.

Define $n=\max(d,m)$.

The above definition conforms with the notation used in the machinery. So, we
can use the bounds as stated there. Once we verify the conditions, the theorem
will immediately follow from the machinery.

####  1 Middle shape bounds

######  Lemma 3.2.

Suppose $0<A<\frac{1}{4}$ is a constant such that
$\frac{\sqrt{\lambda}}{\sqrt{k}}\leq d^{-A\varepsilon}$ and
$\frac{1}{\sqrt{k}}\leq d^{-2A}$. For all $m$ such that
$m\leq\frac{d^{1-\varepsilon}}{\lambda^{2}},m\leq\frac{k^{2-\varepsilon}}{\lambda^{2}}$,
for all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, suppose
$deg^{\tau}(i)$ is even for all $i\in V(\tau)\setminus U_{\tau}\setminus
V_{\tau}$, then

$\sqrt{d}^{|\tau|_{1}-|U_{\tau}|_{1}}\sqrt{m}^{|\tau|_{2}-|U_{\tau}|_{2}}S(\tau)\leq\prod_{j\in
V_{2}(\tau)\setminus U_{\tau}\setminus
V_{\tau}}(deg^{\tau}(j)-1)!!\cdot\frac{1}{d^{A\varepsilon\sum_{e\in
E(\tau)}l_{e}}}$

###### Proof.

Let $r_{1}=|\tau|_{1}-|U_{\tau}|_{1},r_{2}=|\tau|_{2}-|U_{\tau}|_{2}$. Since
$\Delta\leq 1$, it suffices to prove

$E:=\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{\sum_{e\in
E(\tau)}l_{e}}\leq\frac{1}{d^{A\varepsilon\sum_{e\in E(\tau)}l_{e}}}$

We will need the following claim.

######  Claim 3.3.

$\sum_{e\in E(\tau)}l_{e}\geq 2\max(r_{1},r_{2})$.

###### Proof.

We will first prove $\sum_{e\in E(\tau)}l_{e}\geq 2r_{1}$. For any vertex
$i\in V_{1}(\tau)\setminus U_{\tau}\setminus V_{\tau}$, $deg^{\tau}(i)$ is
even and is not $0$, hence, $deg^{\tau}(i)\geq 2$. Any vertex $i\in
U_{\tau}\setminus V_{\tau}$ cannot have $deg^{\tau}(i)=0$ otherwise
$U_{\tau}\setminus\\{i\\}$ is a vertex separator of strictly smaller weight
than $U_{\tau}$, which is not possible, hence, $deg^{\tau}(i)\geq 1$.
Similarly, for $i\in V_{\tau}\setminus U_{\tau}$, $deg^{\tau}(i)\geq 1$. Also,
since $H_{\tau}$ is bipartite, we have $\sum_{i\in
V_{1}(\tau)}deg^{\tau}(i)=\sum_{j\in V_{2}(\tau)}deg^{\tau}(j)=\sum_{e\in
E(\tau)}l_{e}$. Consider

$\displaystyle\sum_{e\in E(\tau)}l_{e}$ $\displaystyle=\sum_{i\in
V_{1}(\tau)}deg^{\tau}(i)$ $\displaystyle\geq\sum_{i\in V_{1}(\tau)\setminus
U_{\tau}\setminus V_{\tau}}deg^{\tau}(i)+\sum_{i\in(U_{\tau})_{1}\setminus
V_{\tau}}deg^{\tau}(i)+\sum_{i\in(V_{\tau})_{1}\setminus
U_{\tau}}deg^{\tau}(i)$ $\displaystyle\geq 2|V_{1}(\tau)\setminus
U_{\tau}\setminus V_{\tau}|+|(U_{\tau})_{1}\setminus
V_{\tau}|+|(V_{\tau})_{1}\setminus U_{\tau}|$ $\displaystyle=2r_{1}$

We can similarly prove $\sum_{e\in E(\tau)}l_{e}\geq 2r_{2}$

To illustrate the main idea, we will start by proving the weaker bound $E\leq
1$. Observe that our assumptions imply
$m\leq\frac{d}{\lambda^{2}},m\leq\frac{k^{2}}{\lambda^{2}}$ and also, using
the fact $\frac{\sqrt{\lambda}}{\sqrt{k}}\leq d^{-A\varepsilon}\leq 1$, we
have
$E\leq\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2\max(r_{1},r_{2})}$.

######  Claim 3.4.

For integers $r_{1},r_{2}\geq 0$, if $m\leq\frac{d}{\lambda^{2}}$ and
$m\leq\frac{k^{2}}{\lambda^{2}}$, then,

$\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2\max(r_{1},r_{2})}\leq
1$

###### Proof.

We will consider the cases $r_{1}\geq r_{2}$ and $r_{1}<r_{2}$ separately. If
$r_{1}\geq r_{2}$, we have

$\displaystyle\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{1}}$
$\displaystyle\leq\sqrt{d}^{r_{1}}\left(\frac{\sqrt{d}}{\lambda}\right)^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{1}}$
$\displaystyle=\left(\frac{\lambda}{\sqrt{d}}\right)^{r_{1}-r_{2}}$
$\displaystyle\leq\left(\frac{1}{\sqrt{m}}\right)^{r_{1}-r_{2}}$
$\displaystyle\leq 1$

And if $r_{1}<r_{2}$, we have

$\displaystyle\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{2}}$
$\displaystyle=\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}-r_{1}}\sqrt{m}^{r_{1}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{2}}$
$\displaystyle\leq\sqrt{d}^{r_{1}}\left(\frac{k}{\lambda}\right)^{r_{2}-r_{1}}\left(\frac{\sqrt{d}}{\lambda}\right)^{r_{1}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{2}}$
$\displaystyle=1$

For the desired bounds, we mimic this argument while carefully keeping track
of factors of $d^{\varepsilon}$.

######  Claim 3.5.

For integers $r_{1},r_{2}\geq 0$ and an integer $r\geq 2\max(r_{1},r_{2})$, if
$m\leq\frac{d^{1-\varepsilon}}{\lambda^{2}}$ and
$m\leq\frac{k^{2-\varepsilon}}{\lambda^{2}}$, then,

$\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r}\leq\left(\frac{1}{d^{A\varepsilon}}\right)^{r}$

###### Proof.

If $r_{1}\geq r_{2}$,

$\displaystyle E$
$\displaystyle=\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{1}}$
$\displaystyle\leq\sqrt{d}^{r_{1}}\left(\frac{\sqrt{d}^{1-\varepsilon}}{\lambda}\right)^{r_{2}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{1}}$
$\displaystyle=\left(\frac{\lambda}{\sqrt{d}^{1-\varepsilon}}\right)^{r_{1}-r_{2}}\left(\frac{1}{\sqrt{d}}\right)^{\varepsilon
r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{1}}$
$\displaystyle\leq\left(\frac{1}{\sqrt{m}}\right)^{r_{1}-r_{2}}\left(\frac{1}{\sqrt{d}}\right)^{\varepsilon
r_{1}}\left(\frac{1}{d^{A\varepsilon}}\right)^{r-2r_{1}}$
$\displaystyle\leq\left(\frac{1}{d^{2A}}\right)^{\varepsilon
r_{1}}\left(\frac{1}{d^{A\varepsilon}}\right)^{r-2r_{1}}$
$\displaystyle=\left(\frac{1}{d^{A\varepsilon}}\right)^{r}$

And if $r_{1}<r_{2}$,

$\displaystyle E$
$\displaystyle=\sqrt{d}^{r_{1}}\sqrt{m}^{r_{2}-r_{1}}\sqrt{m}^{r_{1}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{2}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{2}}$
$\displaystyle\leq\sqrt{d}^{r_{1}}\left(\frac{\sqrt{k}^{2-\varepsilon}}{\lambda}\right)^{r_{2}-r_{1}}\left(\frac{\sqrt{d}^{1-\varepsilon}}{\lambda}\right)^{r_{1}}\left(\frac{k}{d}\right)^{r_{1}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{2r_{2}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{2}}$
$\displaystyle=\left(\frac{\sqrt{k}}{\sqrt{d}}\right)^{\varepsilon
r_{1}}\left(\frac{1}{\sqrt{k}}\right)^{\varepsilon
r_{2}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{2}}$
$\displaystyle\leq\left(\frac{1}{\sqrt{k}}\right)^{\varepsilon
r_{2}}\left(\frac{\sqrt{\lambda}}{\sqrt{k}}\right)^{r-2r_{2}}$
$\displaystyle\leq\left(\frac{1}{d^{2A}}\right)^{\varepsilon
r_{2}}\left(\frac{1}{d^{A\varepsilon}}\right)^{r-2r_{2}}$
$\displaystyle\leq\left(\frac{1}{d^{A\varepsilon}}\right)^{\sum_{e\in
E(\tau)}l_{e}}$

The result follows by setting $r=\sum_{e\in E(\tau)}l_{e}$ in the above claim.

######  Corollary 3.6.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$, we have

$c(\tau)B_{norm}(\tau)S(\tau)R(\tau)\leq 1$

###### Proof.

First, note that if $deg^{\tau}(i)$ is odd for any vertex $i\in
V(\tau)\setminus U_{\tau}\setminus V_{\tau}$, then $S(\tau)=0$ and the
inequality is true. So, assume that $deg^{\tau}(i)$ is even for all $i\in
V(\tau)\setminus U_{\tau}\setminus V_{\tau}$. Since $\tau$ is a proper middle
shape, we have $w(I_{\tau})=0$ and $w(S_{\tau,min})=w(U_{\tau})$. This implies
$n^{\frac{w(V(\tau))+w(I_{\tau})-w(S_{\tau,min})}{2}}=\sqrt{d}^{|\tau|_{1}-|U_{\tau}|_{1}}\sqrt{m}^{|\tau|_{2}-|U_{\tau}|_{2}}$.
As was observed in the proof of Lemma 3.2, every vertex $i\in V(\tau)\setminus
U_{\tau}$ or $i\in V(\tau)\setminus V_{\tau}$ has $deg^{\tau}(i)\geq 1$ and
hence, $|V(\tau)\setminus U_{\tau}|+|V(\tau)\setminus V_{\tau}|\leq
4\sum_{e\in E(\tau)}l_{e}$. Also, $q=d^{O(1)\cdot\varepsilon(C_{V}+C_{E})}$.
We can set $C_{V},C_{E}$ sufficiently small so that

$\displaystyle c(\tau)B_{norm}(\tau)S(\tau)R(\tau)$
$\displaystyle=100(6D_{V})^{|U_{\tau}\setminus V_{\tau}|+|V_{\tau}\setminus
U_{\tau}|+2|E(\tau)|}4^{|V(\tau)\setminus(U_{\tau}\cup V_{\tau})|}$
$\displaystyle\cdot 2e(6qD_{V})^{|V(\tau)\setminus U_{\tau}|+|V(\tau)\setminus
V_{\tau}|}\prod_{e\in E(\tau)}(400D_{V}^{2}D_{E}^{2}q)^{l_{e}}$
$\displaystyle\cdot\sqrt{d}^{|\tau|_{1}-|U_{\tau}|_{1}}\sqrt{m}^{|\tau|_{2}-|U_{\tau}|_{2}}S(\tau)(C_{disc}\sqrt{D_{E}})^{\sum_{j\in(U_{\tau})_{2}\cup(V_{\tau})_{2}}deg^{\tau}(j)}$
$\displaystyle\leq d^{O(1)\cdot(C_{V}+C_{E})\cdot\varepsilon\sum_{e\in
E(\tau)}l_{e}}\cdot\prod_{j\in V_{2}(\tau)\setminus V_{2}(U_{\tau})\setminus
V_{2}(V_{\tau})}(deg^{\tau}(j)-1)!!\cdot\frac{1}{d^{A\varepsilon\sum_{e\in
E(\tau)}l_{e}}}$ $\displaystyle\leq
d^{O(1)\cdot(C_{V}+C_{E})\cdot\varepsilon\sum_{e\in
E(\tau)}l_{e}}\cdot(D_{V}D_{E})^{\sum_{e\in
E(\tau)}l_{e}}\cdot\frac{1}{d^{A\varepsilon\sum_{e\in E(\tau)}l_{e}}}$
$\displaystyle\leq 1$

We can now obtain our desired middle shape bounds.

######  Lemma 3.7.

For all $U\in{\mathcal{I}}_{mid}$ and $\tau\in{\mathcal{M}}_{U}$,

$\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}\succeq
0$

###### Proof.

We have

$\displaystyle\begin{bmatrix}\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}&B_{norm}(\tau)H_{\tau}\\\
B_{norm}(\tau)H_{\tau}^{T}&\frac{1}{|Aut(U)|c(\tau)}H_{Id_{U}}\end{bmatrix}$
$\displaystyle\qquad=\begin{bmatrix}\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)R(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}&0\\\
0&\left(\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)R(\tau)B_{norm}(\tau)}{|Aut(U)|}\right)H_{Id_{U}}\end{bmatrix}$
$\displaystyle\qquad\quad+B_{norm}(\tau)\begin{bmatrix}\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}$

By Lemma 4.9,
$\begin{bmatrix}\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}&H_{\tau}\\\
H_{\tau}^{T}&\frac{S(\tau)R(\tau)}{|Aut(U)|}H_{Id_{U}}\end{bmatrix}\succeq 0$,
so the second term above is positive semidefinite. For the first term, by
Lemma 4.5, $H_{Id_{U}}\succeq 0$ and by Corollary 3.6,
$\frac{1}{|Aut(U)|c(\tau)}-\frac{S(\tau)R(\tau)B_{norm}(\tau)}{|Aut(U)|}\geq
0$, which proves that the first term is also positive semidefinite.

####  2 Intersection term bounds

######  Lemma 3.8.

Suppose $0<A<\frac{1}{4}$ is a constant such that
$\frac{\sqrt{\lambda}}{\sqrt{k}}\leq d^{-A\varepsilon},\frac{1}{\sqrt{k}}\leq
d^{-2A}$ and $\frac{k}{d}\leq d^{-A\varepsilon}$. For all $m$ such that
$m\leq\frac{d^{1-\varepsilon}}{\lambda^{2}},m\leq\frac{k^{2-\varepsilon}}{\lambda^{2}}$,
for all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and for all
$\gamma\in\Gamma_{U,V}$,

$n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}\leq\left(\prod_{j\in
V_{2}(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}}(deg^{\gamma}(j)-1)!!\right)^{2}\frac{1}{d^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

for some constant $B>0$ that depends only on $C_{\Delta}$. In particular, it
is independent of $C_{V}$ and $C_{E}$.

###### Proof.

Suppose there is a vertex $i\in V(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}$ such that $deg^{\gamma}(i)$ is odd, then $S(\gamma)=0$ and the
inequality is true. So, assume $deg^{\gamma}(i)$ is even for all vertices
$i\in V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$. We have
$n^{w(V(\gamma)\setminus
U_{\gamma})}=d^{|\gamma|_{1}-|U_{\gamma}|_{1}}m^{|\gamma|_{2}-|U_{\gamma}|_{2}}$.
Plugging in $S(\gamma)$, we get that we have to prove

$\displaystyle
E:=d^{|\gamma|_{1}-|U_{\gamma}|_{1}}m^{|\gamma|_{2}-|U_{\gamma}|_{2}}\left(\frac{k}{d}\right)^{2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}}\Delta^{2|\gamma|_{2}-|U_{\gamma}|_{2}-|V_{\gamma}|_{2}}\prod_{e\in
E(\gamma)}\frac{\lambda^{l_{e}}}{k^{l_{e}}}\leq\frac{1}{d^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

Let $S^{\prime}$ be the set of vertices $i\in U_{\gamma}\setminus V_{\gamma}$
that have $deg^{\gamma}(i)\geq 1$. Let $e,f$ be the number of type $1$
vertices and the number of type $2$ vertices in $S^{\prime}$ respectively.
Observe that $S^{\prime}\cup(U_{\gamma}\cap V_{\gamma})$ is a vertex separator
of $\gamma$. Let $g=|V_{\gamma}\setminus U_{\gamma}|_{1}$ (resp.
$h=|V_{\gamma}\setminus U_{\gamma}|_{2}$) be the number of type $1$ vertices
(resp. type $2$ vertices) in $V_{\gamma}\setminus U_{\gamma}$. We first claim
that $d^{e}m^{f}\geq d^{g}m^{h}$. To see this, note that the vertex separator
$S^{\prime}\cup(U_{\gamma}\cap V_{\gamma})$ has weight
$\sqrt{d}^{e+|U_{\gamma}\cap V_{\gamma}|_{1}}\sqrt{m}^{f+|U_{\gamma}\cap
V_{\gamma}|_{2}}$. On the other hand, $V_{\gamma}$ has weight
$\sqrt{d}^{g+|U_{\gamma}\cap V_{\gamma}|_{1}}\sqrt{m}^{h+|U_{\gamma}\cap
V_{\gamma}|_{2}}$. Since $\gamma$ is a left shape, $V_{\gamma}$ is the unique
minimum vertex separator and hence, we have the inequality
$\sqrt{d}^{e+|U_{\gamma}\cap V_{\gamma}|_{1}}\sqrt{m}^{f+|U_{\gamma}\cap
V_{\gamma}|_{2}}\geq\sqrt{d}^{g+|U_{\gamma}\cap
V_{\gamma}|_{1}}\sqrt{m}^{h+|U_{\gamma}\cap V_{\gamma}|_{2}}$ which implies
$d^{e}m^{f}\geq d^{g}m^{h}$. Let $p=|V(\gamma)\setminus(U_{\gamma}\cup
V_{\gamma})|_{1}$ (resp. $q=|V(\gamma)\setminus(U_{\gamma}\cup
V_{\gamma})|_{2}$) be the number of type $1$ vertices (resp. type $2$
vertices) in $V(\gamma)\setminus(U_{\gamma}\cup V_{\gamma})$. To illustrate
the main idea, we will first prove the weaker inequality $E\leq 1$. Since
$\Delta\leq 1$, it suffices to prove

$\displaystyle
d^{|\gamma|_{1}-|U_{\gamma}|_{1}}m^{|\gamma|_{2}-|U_{\gamma}|_{2}}\left(\frac{k}{d}\right)^{2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}}\prod_{e\in
E(\gamma)}\frac{\lambda^{l_{e}}}{k^{l_{e}}}\leq 1$

We have
$d^{|\gamma|_{1}-|U_{\gamma}|_{1}}m^{|\gamma|_{2}-|U_{\gamma}|_{2}}=d^{p+g}m^{q+h}\leq
n^{p+\frac{e+g}{2}}m^{q+\frac{f+h}{2}}$ since $d^{e}m^{f}\geq d^{g}m^{h}$.
Also, $2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}=2p+e+g$. So, it
suffices to prove

$\displaystyle
n^{p+\frac{e+g}{2}}m^{q+\frac{f+h}{2}}\left(\frac{k}{d}\right)^{2p+e+g}\prod_{e\in
E(\gamma)}\left(\frac{\lambda}{k}\right)^{l_{e}}\leq 1$

We will need the following claim.

######  Claim 3.9.

$\sum_{e\in E(\gamma)}l_{e}\geq\max(2p+e+g,2q+f+h)$

###### Proof.

Since $H_{\gamma}$ is bipartite, we have $\sum_{e\in
E(\gamma)}l_{e}=\sum_{i\in V_{1}(\gamma)}deg^{\gamma}(i)=\sum_{i\in
V_{2}(\gamma)}deg^{\gamma}(i)$. Observe that all vertices $i\in
V(\gamma)\setminus U_{\gamma}\setminus V_{\gamma}$ have $deg^{\gamma}(i)$
nonzero and even, and hence, $deg^{\gamma}(i)\geq 2$. Then,

$\displaystyle\sum_{e\in E(\gamma)}l_{e}$ $\displaystyle=\sum_{i\in
V_{1}(\gamma)}deg^{\gamma}(i)$ $\displaystyle\geq\sum_{i\in
V_{1}(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in(U_{\gamma})_{1}\setminus
V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in(V_{\gamma})_{1}\setminus
U_{\gamma}}deg^{\gamma}(i)$ $\displaystyle\geq 2p+e+g$

Similarly,

$\displaystyle\sum_{e\in E(\gamma)}l_{e}$ $\displaystyle=\sum_{i\in
V_{2}(\gamma)}deg^{\gamma}(i)$ $\displaystyle\geq\sum_{i\in
V_{2}(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in(U_{\gamma})_{2}\setminus
V_{\gamma}}deg^{\gamma}(i)+\sum_{i\in(V_{\gamma})_{2}\setminus
U_{\gamma}}deg^{\gamma}(i)$ $\displaystyle\geq 2q+f+h$

Therefore, $\sum_{e\in E(\gamma)}l_{e}\geq\max(2p+e+g,2q+f+h)$.

Now, let $r_{1}=p+\frac{e+g}{2},r_{2}=q+\frac{f+h}{2}$. Then, $\sum_{e\in
E(\gamma)}l_{e}\geq 2\max(r_{1},r_{2})$ and we wish to prove
$d^{r_{1}}m^{r_{2}}\left(\frac{k}{d}\right)^{2r_{1}}\left(\frac{\lambda}{k}\right)^{2\max(r_{1},r_{2})}\leq
1$ This expression simply follows by squaring 3.4.

Now, to prove that
$E\leq\frac{1}{d^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$, we mimic this argument while
carefully keeping track of factors of $d^{\varepsilon}$. Again, using
$d^{e}m^{f}\geq d^{g}m^{h}$, it suffices to prove that

$\displaystyle
d^{p+\frac{e+g}{2}}m^{q+\frac{f+h}{2}}\left(\frac{k}{d}\right)^{2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}}$
$\displaystyle\Delta^{2|\gamma|_{2}-|U_{\gamma}|_{2}-|V_{\gamma}|_{2}}\prod_{e\in
E(\gamma)}\frac{\lambda^{l_{e}}}{k^{l_{e}}}$
$\displaystyle\leq\frac{1}{d^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$

The idea is that the $d^{B\varepsilon}$ decay for the edges are obtained from
the stronger assumption on $m$, namely
$m\leq\frac{d^{1-\varepsilon}}{\lambda^{2}},m\leq\frac{k^{2-\varepsilon}}{\lambda^{2}}$.
And the $d^{B\varepsilon}$ decay for the type $1$ vertices of
$V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})$ are obtained both from the
stronger assumption on $m$ as well as the factors of $\frac{k}{d}$, the latter
especially useful for the degree $0$ vertices. Finally, the $d^{B\varepsilon}$
decay for the type $2$ vertices of $V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})$ are obtained from the factors of $\Delta$. Indeed, note that for
a constant $B$ that depends on $C_{\Delta}$,
$\Delta^{2|\gamma|_{2}-|U_{\gamma}|_{2}-|V_{\gamma}|_{2}}\leq
d^{-B\varepsilon|V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})|_{2}}$. So, we
would be done if we prove

$\displaystyle
d^{p+\frac{e+g}{2}}m^{q+\frac{f+h}{2}}\left(\frac{k}{d}\right)^{2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}}\left(\frac{\lambda}{k}\right)^{\sum_{e\in
E(\gamma)}l_{e}}\leq\frac{1}{d^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|_{1}+\sum_{e\in E(\gamma)}l_{e})}}$

Let $c_{0}$ be the number of type $1$ vertices $i$ in
$V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})$ such that $deg^{\gamma}(i)=0$.
Since they have degree $0$, they must be in $(U_{\gamma})_{1}\setminus
V_{\gamma}$. Also, we have
$2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}=2p+e+g+c_{0}$ and hence,
$\left(\frac{k}{d}\right)^{2|\gamma|_{1}-|U_{\gamma}|_{1}-|V_{\gamma}|_{1}}=\left(\frac{k}{d}\right)^{2p+e+g+c_{0}}$.
For these degree $0$ vertices, we have that the factors of $\frac{k}{d}\leq
d^{-A\varepsilon}$ offer a decay of $\frac{1}{d^{B\varepsilon}}$. Therefore,
it suffices to prove

$\displaystyle
d^{p+\frac{e+g}{2}}m^{q+\frac{f+h}{2}}\left(\frac{k}{d}\right)^{2p+e+g}\left(\frac{\lambda}{k}\right)^{\sum_{e\in
E(\gamma)}l_{e}}\leq\frac{1}{d^{B\varepsilon(p+q+e+f+g+h)+\sum_{e\in
E(\gamma)}l_{e})}}$

for a constant $B>0$. Observe that $p+q+e+f+g+h\leq 2(\sum_{e\in
E(\gamma)}l_{e})$. Therefore, using the notation
$r_{1}=p+\frac{e+g}{2},r_{2}=q+\frac{f+h}{2}$, it suffices to prove

$\displaystyle
d^{r_{1}}m^{r_{2}}\left(\frac{k}{d}\right)^{2r_{1}}\left(\frac{\lambda}{k}\right)^{\sum_{e\in
E(\gamma)}l_{e}}\leq\frac{1}{d^{B\varepsilon\sum_{e\in E(\gamma)}l_{e}}}$

for a constant $B>0$. But this follows by squaring 3.5 where we set
$r=\sum_{e\in E(\gamma)}l_{e}$.

######  Remark 3.10.

In the above bounds, note that there is a decay of $d^{B\varepsilon}$ for each
vertex in $V(\gamma)\setminus(U_{\gamma}\cap V_{\gamma})$. One of the main
technical reasons for introducing the slack parameter $C_{\Delta}$ in the
planted distribution was to introduce this decay, which is needed in the
current machinery.

With this, we obtain intersection term bounds.

######  Lemma 3.11.

For all $U,V\in{\mathcal{I}}_{mid}$ where $w(U)>w(V)$ and all
$\gamma\in\Gamma_{U,V}$,

$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}\preceq
H_{\gamma}^{\prime}$

###### Proof.

By Lemma 4.10, we have

$\displaystyle
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}H_{Id_{V}}^{-\gamma,\gamma}$
$\displaystyle\preceq
c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}R(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}H^{\prime}_{\gamma}$

Using the same proof as in Lemma 4.5, we can see that
$H^{\prime}_{\gamma}\succeq 0$. Therefore, it suffices to prove that
$c(\gamma)^{2}N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}R(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}\leq
1$. Since $U,V\in{\mathcal{I}}_{mid}$,
$Aut(U)=|U|_{1}!|U|_{2}!,Aut(V)=|V|_{1}!|V|_{2}!$. Therefore,
$\frac{|Aut(U)|}{|Aut(V)|}=\frac{|U|_{1}!|U|_{2}!}{|V|_{1}!|V|_{2}!}\leq
D_{V}^{|U_{\gamma}\setminus V_{\gamma}|}$. Also, $|E(\gamma)|\leq\sum_{e\in
E(\gamma)}l_{e}$ and $q=d^{O(1)\cdot\varepsilon(C_{V}+C_{E})}$. Note
$R(\gamma)^{2}=(C_{disc}\sqrt{D_{E}})^{2\sum_{j\in(U_{\gamma})_{2}\cup(V_{\gamma})_{2}}deg^{\gamma}(j)}\leq
d^{O(1)\cdot\varepsilon C_{E}\cdot\sum_{e\in E(\gamma)}l_{e}}$ and

$\left(\prod_{j\in V_{2}(\gamma)\setminus U_{\gamma}\setminus
V_{\gamma}}(deg^{\gamma}(j)-1)!!\right)^{2}\leq(D_{V}D_{E})^{2\sum_{e\in
E(\tau)}l_{e}}\leq d^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot\sum_{e\in
E(\gamma)}l_{e}}$

Let $B$ be the constant from Lemma 3.8. We can set $C_{V},C_{E}$ sufficiently
small so that, using Lemma 3.8,

$\displaystyle c(\gamma)^{2}$ $\displaystyle
N(\gamma)^{2}B(\gamma)^{2}S(\gamma)^{2}R(\gamma)^{2}\frac{|Aut(U)|}{|Aut(V)|}$
$\displaystyle\leq 100^{2}(6D_{V})^{2|U_{\gamma}\setminus
V_{\gamma}|+2|V_{\gamma}\setminus
U_{\gamma}|+|E(\alpha)|}16^{|V(\gamma)\setminus(U_{\gamma}\cup V_{\gamma})|}$
$\displaystyle\quad\cdot(3D_{V})^{4|V(\gamma)\setminus
V_{\gamma}|+2|V(\gamma)\setminus U_{\gamma}|}(6qD_{V})^{2|V(\gamma)\setminus
U_{\gamma}|+2|V(\gamma)\setminus V_{\gamma}|}\prod_{e\in
E(\gamma)}(400D_{V}^{2}D_{E}^{2}q)^{2l_{e}}$ $\displaystyle\quad\cdot
n^{w(V(\gamma)\setminus U_{\gamma})}S(\gamma)^{2}d^{O(1)\cdot\varepsilon
C_{E}\cdot\sum_{e\in E(\gamma)}l_{e}}\cdot D_{V}^{|U_{\gamma}\setminus
V_{\gamma}|}$ $\displaystyle\leq
d^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}\cdot n^{w(V(\gamma)\setminus
U_{\gamma})}S(\gamma)^{2}$ $\displaystyle\leq
d^{O(1)\cdot\varepsilon(C_{V}+C_{E})\cdot(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in
E(\gamma)}l_{e})}\cdot\frac{1}{d^{B\varepsilon(|V(\gamma)\setminus(U_{\gamma}\cap
V_{\gamma})|+\sum_{e\in E(\gamma)}l_{e})}}$ $\displaystyle\leq 1$

####  3 Truncation error bounds

In this section, we will obtain truncation error bounds using the strategy
sketched in [potechin2020machinery, Section 10]. We also reuse the notation.
To do this, we need to first obtain a bound on the quantity
$B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})$.

######  Lemma 3.12.

Suppose $0<A<\frac{1}{4}$ is a constant such that
$\frac{\sqrt{\lambda}}{\sqrt{k}}\leq d^{-A\varepsilon}$ and
$\frac{1}{\sqrt{k}}\leq d^{-2A}$. Suppose $m$ is such that
$m\leq\frac{d^{1-\varepsilon}}{\lambda^{2}},m\leq\frac{k^{2-\varepsilon}}{\lambda^{2}}$.
For all $U\in{\mathcal{I}}_{mid}$ and
$\sigma,\sigma^{\prime}\in{\mathcal{L}}_{U}$,

$B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})\leq\frac{1}{d^{0.5A\varepsilon(|V(\sigma\circ\sigma^{\prime})|+\sum_{e\in
E(\alpha)l_{e}}}}\cdot\frac{1}{d^{|U_{\sigma}|_{1}+|U_{\sigma^{\prime}}|_{1}}m^{|U_{\sigma^{\prime}}|_{2}+|U_{\sigma^{\prime}}|_{2}}}$

###### Proof.

Suppose there is a vertex $i\in V(\sigma)\setminus V_{\sigma}$ such that
$deg^{\sigma}(i)+deg^{U_{\sigma}}(i)$ is odd, then
$H_{Id_{U}}(\sigma,\sigma^{\prime})=0$ and the inequality is true. So, assume
that $deg^{\sigma}(i)+deg^{U_{\sigma}}(i)$ is even for all $i\in
V(\sigma)\setminus V_{\sigma}$. Similarly, assume that
$deg^{\sigma^{\prime}}(i)+deg^{U_{\sigma^{\prime}}}(i)$ is even for all $i\in
V(\sigma^{\prime})\setminus V_{\sigma^{\prime}}$. Also, if
$\rho_{\sigma}\neq\rho_{\sigma^{\prime}}$, we will have
$H_{Id_{U}}(\sigma,\sigma^{\prime})=0$ and we would be done. So, assume
$\rho_{\sigma}=\rho_{\sigma^{\prime}}$.

Let there be $e$ (resp. $f$) vertices of type $1$ (resp. type $2$) in
$V(\sigma)\setminus U_{\sigma}\setminus V_{\sigma}$. Then,
$n^{\frac{w(V(\sigma))-w(U)}{2}}=\sqrt{d}^{|V(\sigma)|_{1}-|U|_{1}}\sqrt{m}^{|V(\sigma)|_{2}-|U|_{2}}=\sqrt{d}^{|U_{\sigma}|_{1}}\sqrt{m}^{|U_{\sigma}|_{2}}\sqrt{d}^{e}\sqrt{m}^{f}$.
Let there be $g$ (resp. $h$) vertices of type $1$ (resp. type $2$) in
$V(\sigma^{\prime})\setminus U_{\sigma^{\prime}}\setminus
V_{\sigma^{\prime}}$. Then, similarly,
$n^{\frac{w(V(\sigma^{\prime}))-w(U)}{2}}\leq\sqrt{d}^{|U_{\sigma^{\prime}}|_{1}}\sqrt{m}^{|U_{\sigma^{\prime}}|_{2}}\sqrt{d}^{g}\sqrt{m}^{h}$.

Let $\alpha=\sigma\circ\sigma^{\prime}$. Since all vertices in
$V(\alpha)\setminus U_{\alpha}\setminus V_{\alpha}$ have degree at least $2$,
we have $\sum_{e\in E(\alpha)}l_{e}\geq\sum_{i\in V_{1}(\alpha)\setminus
U_{\alpha}\setminus V_{\alpha}}deg^{\alpha}(i)\geq
2(e+g)+|U_{\sigma}|_{1}+|U_{\sigma}|_{2}$. Similarly, $\sum_{e\in
E(\alpha)}l_{e}\geq
2(f+h)+|U_{\sigma^{\prime}}|_{1}+|U_{\sigma^{\prime}}|_{2}$. Therefore, by
setting $r_{1}=e+g,r_{2}=f+h$ in 3.5, we have

$\sqrt{d}^{e+g}\sqrt{m}^{f+h}\left(\frac{k}{d}\right)^{e+g}\prod_{e\in
E(\alpha)}\frac{\sqrt{\lambda}^{l_{e}}}{\sqrt{k}^{l_{e}}}\leq\frac{1}{d^{A\varepsilon\sum_{e\in
E(\alpha)}l_{e}}}$

Also,

$\left(\frac{k}{d}\right)^{|\alpha|_{1}}\leq\left(\frac{k}{d}\right)^{e+g+|U_{\sigma}|_{1}+|U_{\sigma^{\prime}}|_{1}}$

and

$\prod_{j\in V_{2}(\alpha)}(deg^{\alpha}(j)-1)!!\leq d^{\varepsilon
C_{V}\sum_{e\in E(\alpha)}l_{e}}$

Therefore,

$\displaystyle
n^{\frac{w(V(\sigma))-w(U)}{2}}n^{\frac{w(V(\sigma^{\prime}))-w(U)}{2}}H_{Id_{U}}(\sigma,\sigma^{\prime})$
$\displaystyle\leq
d^{O(1)D_{sos}}\sqrt{d}^{e}\sqrt{m}^{f}d^{O(1)D_{sos}}\sqrt{d}^{g}\sqrt{m}^{h}$
$\displaystyle\qquad\cdot\frac{1}{|Aut(U)|}\left(\frac{1}{\sqrt{k}}\right)^{deg(\alpha)}\left(\frac{k}{d}\right)^{|\alpha|_{1}}\Delta^{|\alpha|_{2}}\prod_{j\in
V_{2}(\alpha)}(deg^{\alpha}(j)-1)!!\prod_{e\in
E(\alpha)}\frac{\sqrt{\lambda}^{l_{e}}}{\sqrt{k}^{l_{e}}}$ $\displaystyle\leq
d^{O(1)D_{sos}}d^{\varepsilon C_{V}\sum_{e\in
E(\alpha)}l_{e}}\sqrt{d}^{e+g}\sqrt{m}^{f+h}\left(\frac{k}{d}\right)^{e+g}\prod_{e\in
E(\alpha)}\frac{\sqrt{\lambda}^{l_{e}}}{\sqrt{k}^{l_{e}}}\cdot\frac{1}{d^{|U_{\sigma}|_{1}+|U_{\sigma^{\prime}}|_{1}}m^{|U_{\sigma^{\prime}}|_{2}+|U_{\sigma^{\prime}}|_{2}}}$
$\displaystyle\leq\frac{d^{\varepsilon C_{V}\sum_{e\in
E(\alpha)}l_{e}}}{d^{A\varepsilon\sum_{e\in
E(\alpha)}l_{e}}}\cdot\frac{1}{d^{|U_{\sigma}|_{1}+|U_{\sigma^{\prime}}|_{1}}m^{|U_{\sigma^{\prime}}|_{2}+|U_{\sigma^{\prime}}|_{2}}}$

By setting $C_{V},C_{E}$ sufficiently small and plugging in the expressions
for $B_{norm}(\sigma),B_{norm}(\sigma^{\prime})$, we obtain the result.

We can apply the the strategy now.

######  Lemma 3.13.

Whenever $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in{\mathcal{M}}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq\frac{1}{d^{K_{1}D_{sos}^{2}}}Id_{sym}$

for a constant $K_{1}>0$ that can depend on $C_{\Delta}$.

###### Proof.

For $V\in{\mathcal{I}}_{mid}$,
$\lambda_{V}=\frac{\Delta^{|V|_{2}}}{d^{|V|_{1}}k^{|V|_{2}}}$. Let the minimum
value of this quantity over all $V$ be $N$. We then choose
$w_{V}=N/\lambda_{V}$ so that for all left shapes
$\sigma\in{\mathcal{L}}_{V}$, Lemma 3.12 implies
$w_{V}\leq\frac{w_{U_{\sigma}}\lambda_{U_{\sigma}}}{|\mathcal{I}_{mid}|B_{norm}(\sigma)^{2}{c(\sigma)^{2}}{H_{Id_{V}}(\sigma,\sigma)}}$,
completing the proof.

######  Lemma 3.14.

$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}\leq\frac{d^{K_{2}D_{sos}}}{2^{D_{V}}}$

for a constant $K_{2}>0$ that can depend on $C_{\Delta}$.

###### Proof.

We do the same calculations as in the proof of Lemma 1.8, until

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}$
$\displaystyle\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}{B_{norm}(\sigma)B_{norm}(\sigma^{\prime})H_{Id_{U}}(\sigma,\sigma^{\prime})\frac{1}{2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{d^{O(1)D_{sos}}}{d^{0.5A\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$

where we used Lemma 3.12. Using
$d^{0.5A\varepsilon|V(\sigma\circ\sigma^{\prime})|}\geq
d^{0.1A\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{|V(\sigma\circ\sigma^{\prime})|}$,

$\displaystyle\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\gamma\in\Gamma_{U,*}}\frac{d_{Id_{U}}(H_{Id_{U}},H^{\prime}_{\gamma})}{|Aut(U)|c(\gamma)}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{d^{O(1)D_{sos}}}{d^{0.1A\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{|V(\sigma\circ\sigma^{\prime})|}2^{\min(m_{\sigma},m_{\sigma^{\prime}})-1}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{d^{O(1)D_{sos}}}{d^{0.1A\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{D_{V}}}$
$\displaystyle\leq\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{d^{O(1)D_{sos}}}{D_{sos}^{D_{sos}}d^{0.1A\varepsilon|V(\sigma\circ\sigma^{\prime})|}2^{D_{V}}}$

The final step will be to argue that
$\sum_{U\in{\mathcal{I}}_{mid}}\sum_{\sigma,\sigma^{\prime}\in\mathcal{L}^{\prime}_{U}}\frac{1}{D_{sos}^{D_{sos}}d^{0.1A\varepsilon|V(\sigma\circ\sigma^{\prime})|}}\leq
1$ which will complete the proof. But this will follow if we set $C_{V},C_{E}$
small enough.

We can finally show that truncation errors can be handled.

######  Lemma 3.15.

Whenever $\left\lVert M_{\alpha}\right\rVert\leq B_{norm}(\alpha)$ for all
$\alpha\in\mathcal{M}^{\prime}$,

$\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

###### Proof.

Choose $C_{sos}$ sufficiently small so that
$\frac{1}{d^{K_{1}D_{sos}^{2}}}\geq 6\frac{d^{K_{2}D_{sos}}}{2^{D_{V}}}$ which
can be satisfied by setting $C_{sos}<K_{3}C_{V}$ for a sufficiently small
constant $K_{3}>0$. Then, since $Id_{Sym}\succeq 0$, using Lemma 3.13 and
Lemma 3.14,

$\displaystyle\sum_{U\in\mathcal{I}_{mid}}{M^{fact}_{Id_{U}}{(H_{Id_{U}})}}$
$\displaystyle\succeq\frac{1}{d^{K_{1}D_{sos}^{2}}}Id_{sym}$
$\displaystyle\succeq 6\frac{d^{K_{2}D_{sos}}}{2^{D_{V}}}Id_{sym}$
$\displaystyle\succeq
6\left(\sum_{U\in\mathcal{I}_{mid}}{\sum_{\gamma\in\Gamma_{U,*}}{\frac{d_{Id_{U}}(H^{\prime}_{\gamma},H_{Id_{U}})}{|Aut(U)|c(\gamma)}}}\right)Id_{sym}$

##  Chapter 7 Followup and Future work

In this chapter, we go over some follow-up works that are not covered in this
dissertation and also suggest directions for future work. We then conclude
this dissertation with a note on the broader implications of our work for
computer science.

###  1 Nonlinear concentration for non-product distributions

Our techniques in Chapter 1 apply to a collection of random variables that are
sampled independently of each other. A natural question is to ask if we can
generalize to the case when they are not independent. For example, this is
useful when instead of analyzing Erdős-Rényi random graphs, we wish to analyze
uniform $d$-regular graphs. Such a generalization seems extremely likely
because our proof techniques essentially requires a Markov Chain that mixes
rapidly to the given distribution, and then we can recursively apply the
Poincaré inequality. We leave this for future work.

###  2 Sum of Squares lower bounds

In this dissertation, we saw several SoS lower bounds and while they build on
fundamental conceptual building blocks such as the nonlinear concentration
results we show and simple heuristics like pseudocalibration, an important
technical barrier in the current proofs is that the proofs are highly
technical and have many moving parts. It’s an important research question to
understand if the proofs can be simplified. Apart from enabling a better
understanding of the SoS hierarchy, this will also help us understand the
computational barriers of several fundamental problems in computer science.
Examples of such problems follow.

####  1 Sparse Independent Set

In a follow-up work [jones2022sum], we prove SoS lower bounds for the
important problem of maximum independent set on sparse Erdős-Rényi random
graphs.

In this dissertation, the SoS lower bounds studied were in the setting when
the input was sampled from product distributions where each distribution was
either Rademacher or Gaussian. This is also the case in many prior works on
SoS lower bounds. Recall that this was termed the dense setting in Chapter 1.
It’s equally important to study problems in the fascinating average-case
sparse setting where the input distribution could have high Orlicz norm, for
example when the input is an Erdős-Rényi random graph sampled from $G_{n,p}$
instead of $G_{n,\frac{1}{2}}$ for some $p=o(1)$. The techniques developed in
this work and prior works for high degree SoS lower bounds do not easily
generalize to this setting. The work [jones2022sum] initiates this research
direction for the fundamental problem of maximum independent set on random
sparse graphs.

Consider the independent set problem on a graph $G\sim G_{n,\frac{d}{n}}$
where $d$ is the average degree. If $d=\frac{n}{2}$, then this is the same as
the maximum clique problem and SoS lower bounds were obtained in [BHKKMP16].
We now focus on the setting $d\ll n$. We first state the size of the true
optimum.

######  Fact 2.1 ([COE15, DM11, DSS16]).

W.h.p. the max independent set in $G$ has size $(1+o_{d}(1))\cdot\frac{2\ln
d}{d}\cdot n$.

The famous Lovász $\vartheta$ function efficiently computes an upper bound on
this value and its value is well-known on such random graphs.

######  Fact 2.2 ([CO05]).

W.h.p. $\vartheta(G)=\Theta(\frac{n}{\sqrt{d}})$.

The value of the $\vartheta$ function is also the output of the degree $2$ SoS
relaxation for this problem. So, there is an integrality gap of approximately
$\sqrt{d}$. We therefore naturally ask whether higher degree SoS can perform
better or this gap persists. In our work, we show that this $\sqrt{d}$
integrality gap persists for higher degrees of SoS as well

We prove two main results, one in the setting $(\log n)^{2}\leq d\leq\sqrt{n}$
and the other in the setting $n^{\Omega(1)}\leq d\leq\frac{n}{2}$. Note that
we have not covered the case when the average degree $d$ is constant. This is
an interesting direction for future work.

In the first setting $(\log n)^{2}\leq d\leq\sqrt{n}$, we show a tradeoff
between the degree $D_{sos}$ of the SoS relaxation and the integrality gap.

######  Theorem 2.3.

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,D_{\text{SoS}}$ satisfying
$k~{}\leq~{}\frac{n}{D_{\text{SoS}}^{c_{0}}\cdot\log n\cdot d^{1/2}},$ w.h.p.
over $G~{}\sim~{}G_{n,~{}d/n}$, there exists a degree-$D_{\text{SoS}}$
pseudoexpectation for the maximum independent set problem with objective value
$(1-o(1))k$.

In particular, when $d\in[n^{\Omega(1)},\sqrt{n}]$, this exhibits an SoS lower
bound against polynomial degree $n^{\Omega(1)}$ SoS. In the second setting
$n^{\Omega(1)}\leq d\leq\frac{n}{2}$, we show an SoS lower bound for
logarithmic degree SoS.

######  Theorem 2.4.

For any $\varepsilon_{1},\varepsilon_{2}>0$ there is $\delta>0$, such that for
$d\in[n^{\varepsilon_{1}},n/2]$ and $k\leq\frac{n}{d^{1/2+\varepsilon_{2}}}$,
w.h.p. over $G~{}\sim~{}G_{n,~{}d/n}$, there exists a degree-$(\delta\log d)$
pseudoexpectation with objective value $(1-o(1))k$.

We remark that these theorems rule out polynomial-time certification (i.e.
constant degree SoS) for any $d\geq{\mathrm{polylog}}(n)$.

Broadly speaking, we utilize similar techniques to show these results, namely
pseudo-calibration, graph matrices and approximate PSD decomposition. However,
the approach does not readily work and we overcome the difficulties with
several new ideas and techniques. We summarize some of them below.

  * •

The first conceptual difficulty we overcome is that we are unable to apply
pseudo-calibration due to the lack of a good candidate planted distribution.
For most natural choices of the planted distribution, simple statistics
distinguish the random distribution from the planted distribution. While a
suitable planted distribution that enables the use of pseudo-calibration may
very well exist, we are yet to find one. Instead, in this work, we simply use
the naïve planted distribution but instead modify the heuristic of pseudo-
calibration (that we term pseudo-calibration with connected trunction) to
construct our candidate moment matrix.

  * •

The second conceptual difficulty was the lack of good norm bounds for graph
matrices built from sparse graphs. In that work, we utilized the trace method
with a careful analysis to obtain better norm bounds. Moreover, as we saw in
Chapter 1, we are able to obtain similar norm bounds without the trace method,
using our general recursion theorem.

Apart from the above developments, we develop several technical tools such as
conditioning, a generalization of the intersection tradeoff lemma, etc. For
more details, see [jones2022sum].

####  2 Planted Affine Planes and Maximum Cut

For the Planted Affine Planes problem from Chapter 4 where we sampled $m$
vectors $d_{1},\ldots,d_{m}$ independently from $\mathcal{N}(0,I_{n})$, we
showed an SoS lower bound for $m\leq n^{3/2-\varepsilon}$. However, from the
analysis of $\widetilde{{\mathbb{E}}}[1]$ in Remark 4.9, we expect a lower
bound to hold for $m\ll n^{2-\varepsilon}$. This is because, as we saw in
Chapter 2 and which we will revisit in the next section, analyzing
$\widetilde{{\mathbb{E}}}[1]$ is an established way to hypothesize about the
power of SoS. Therefore, we conjecture

######  Conjecture 2.5.

Theorem 1.4 holds with the bound on the number of sampled vectors $m$ loosened
to $m\leq n^{2-\varepsilon}$.

Dual to this (in fact, we exploit the duality in our proof in Chapter 4), we
conjecture an SoS lower bound for the Planted Boolean Vector problem holds
whenever $p\geq n^{1/2+\varepsilon}$.

######  Conjecture 2.6.

Theorem 1.5 holds with the bound on the dimension $p$ of a random subspace
loosened to $p\geq n^{1/2+\varepsilon}$.

We remark that recent work [zadik2021latticebased] has exhibited a polynomial
time for the search variant of Planted Affine Planes for $m\geq n+1$, as
opposed to prior known algorithms that required $m\gg n^{2}$ [mao2021optimal].
The algorithm in [mao2021optimal] is spectral and robust to noise, moreover it
is likely captured by SoS. On the other hand, the algorithm in
[zadik2021latticebased] is lattice-based and is not robust to noise, (i.e. it
assumes that all vectors must exactly lie in the two planes), and is not
captured by SoS.

In our SoS lower bounds for the Planted Boolean Vector problem and the Planted
Affine Planes problem, we assumed that the input entries were chosen i.i.d
Gaussian or Boolean. In fact, it’s plausible that our proof techniques go
through when the distribution is “random enough”, such as the uniform
distribution from the sphere. One potential extension of this intuition is as
follows: In the Planted Boolean Vector problem, if the subspace is the
eigenspace of the bottom eigenvectors of a random adjacency matrix, the
instance should still be difficult. This last setting arises in Maximum Cut,
for which we conjecture the following.

######  Conjecture 2.7.

Let $d\geq 3$, and let $G$ be a random $d$-regular graph on $n$ vertices. For
some $\delta>0$, w.h.p. there is a degree-$n^{\delta}$ pseudoexpectation
operator $\widetilde{{\mathbb{E}}}$ on boolean variables $x_{i}$ with maximum
cut value at least

$\frac{1}{2}+\frac{\sqrt{d-1}}{d}(1-\operatorname{o}_{d,n}(1))$

The above expression is w.h.p. the value of the spectral relaxation for
Maximum Cut, therefore qualitatively this conjecture expresses that degree
$n^{\delta}$ SoS cannot significantly tighten the basic spectral relaxation.

We should remark that, with respect to the goal of showing SoS cannot
significantly outperform the Goemans-Williamson relaxation, random instances
are not integrality gap instances. The main difficulty in comparing (even
degree 4) SoS to the Goemans-Williamson algorithm seems to be the lack of a
candidate hard input distribution.

Evidence for this conjecture comes from the fact that the only property
required of the random inputs $d_{1},\dots,d_{m}$ was that norm bounds hold
for the graph matrix with Hermite polynomial entries. When the variables
$\\{d_{u,i}\\}$ are i.i.d from some other distribution, if we use graph
matrices for the orthonormal polynomials under the distribution and assuming
suitable bounds on the moments of the distribution, the same norm bounds hold
[ahn2016graph]. When $d_{u}$ is sampled uniformly from the sphere or another
distribution for which the coordinates are not i.i.d, it seems likely that
similar norm bounds hold. Moreover, as explained in the previous section, the
techniques from Chapter 1 will likely be useful to obtain such norm bounds.

####  3 Unique Games

The famous Unique Games conjecture (UGC) [Khot02:unique] postulates that a
graph theory problem known as the Unique Games problem is NP-hard. This
conjecture gained tremendous traction in the community because of it’s
numerous consequences (e.g. [Khot02:unique, KhotKMO04, Raghavendra08])) and
connections to various other fields such as metric geometry [KhotV05] and
discrete Fourier analysis [KR03]. An exciting array of recent works
[dinur2018towards, barak2018small, subhash2018pseudorandom] has shown that a
problem closely related to unique games, known as $2$-to-$2$ games, is NP-
hard. This is an important step towards proving the UGC and offers evidence
that the UGC is true.

On the algorithmic side, there have been various attempts (see for e.g.
[T05:unique, CharikarMM06, arora2015subexponential]) to disprove the UGC. In
particular, Barak et al. [barak2012hypercontractivity] showed that degree $8$
SoS can efficiently solve integrality gap instances of the Unique Games
problem that were proposed for linear programs and SDPs considered earlier.
This work caused significant interest in the community, since it suggests that
SoS might be a way to refute the UGC.

Therefore, it’s tremendously important to understand the performance of SoS on
the unique games problem. A good first step would be to understand the
performance of SoS for the problem of maximum cut, which is a special case of
the Unique Games problem. In fact, we can be even more concrete and ask for
the performance of SoS for the problem of maximum cut on random graphs, more
precisely 2.7. Lower bounds were shown for degree $2$ and degree $4$ in [MS16,
mohanty2020lifting] and generalizing their analyses for higher degree SoS is a
nontrivial but important open problem.

###  3 Low degree likelihood ratio hypothesis

As explained in Chapter 2, the low-degree likelihood ratio hypothesis
analytically predicts the computational barriers for hypothesis testing in
bounded time, for sufficiently nice distributions. See [hop18, kunisky19notes,
holmgren2020counterexamples] and references therein for more details. A full
proof of this hypothesis is beyond current techniques, since it’s likely
harder than proving say $P\neq NP$. Despite this, confirming the hypothesis in
restricted proof systems is a fascinating and important field for future
research. In particular, building on the notation from Chapter 2, we would
like to prove that for sufficiently nice distributions $\nu,\mu$, after
pseudo-calibrating, if $\widetilde{{\mathbb{E}}}[1]=1+o(1)$, then there exists
an SoS lower bound. Indeed, in this work, we confirm this for several
fundamental problems. Proving this in general will go a long way towards
understanding the power of bounded-time algorithms.

###  4 Technical improvements

Having covered some general directions for future research, we now specify a
few directions for improving some technical aspects of our results.

##### Improving parameter dependences

In many of our lower bounds, we require polynomial decay in the Fourier
coefficients. For example, we require a decay of $n^{\varepsilon}$ for each
new Fourier character, where $n$ is the input size. This is done to handle
various other factors that appear in norm bounds when doing the charging
arguments. In the proofs, we term these as vertex or edge decay, corresponding
to how they are encoded in the graph matrix arguments we use. By doing this,
we obtain a slightly weaker lower bound. For example, instead of getting a
$n^{1/4}$ lower bound (up to polylogarithmic factors) for Tensor PCA, we
obtain a $n^{1/4-\varepsilon}$ lower bound for any $\varepsilon>0$. In
general, while they facilitate the proof, it’s not clear that this sort of
decay is necessary and it’s open to find a tighter analysis so as to close the
gap from known upper bounds up to a polylogarithmic factor.

Related to the above discussion, another open problem is to push the degree of
SoS higher in our lower bounds. For example, in the Sherrington-Kirkpatrick
lower bound, it’s open to push the SoS degree from $n^{\varepsilon}$ to
$\widetilde{\Omega}(n)$. Our current techniques do not handle this but we
expect the lower bound to nevertheless hold.

##### Satisfying constraints exactly

In some of our lower bounds, our planted distributions only approximately
satisfy constraints such as having a subgraph of size $k$, having a unit
vector $u$, and having $u$ be $k$-sparse. While we would like to use planted
distributions which satisfy such constraints exactly, the moment matrix
becomes much harder to analyze.

We do resolve it for the Sherrington-Kirkpatrick lower bound by using a
rounding technique [ghosh2020sum]. This same issue also appeared in the SoS
lower bounds for planted clique [BHKKMP16], which was fixed in a recent paper
by Pang [Pang21]. We leave it to future work to resolve this in general.

###  5 Implications for Computer Science

As we saw in the introduction, the current state of affairs in Theoretical
Computer Science research seems to be to understand the limits of computation
for various problems. Even though there maybe potential ultimate goals such as
settling the P vs NP problem or even relatively modest goals such as settling
the Unique Games Conjecture, there’s much to be learnt and uncovered from this
process. For example, for various problems, there seems to be a discernible
gap between what’s information theoretically possible and what’s
computationally feasible. Our work adds insight into this intriguing
phenomenon, known as the information-computation tradeoff. However, there are
also other questions that need answering. For example, what makes
certification seemingly harder than estimation or recovery? Can we
characterize the precise property of problems that potentially make them hard
or easy for various classes of algorithms such as Sum of Squares? While much
rich structure is slowly being uncovered in this general pursuit, a proper
understanding still eludes us. However, applications of what we’ve discovered
so far, both technically and philosophically, are already numerous in various
branches of mathematics and science, therefore research in this field is more
than for the sake of mere curiosity. We hope our work serves as a meaningful
progress towards this grand goal.