&+{\rm{TV}}\left(\mathcal{L}({\mathbfcal{M}}_{5}),\int\mathcal{L}\left(\frac{\xi}{\sqrt{d!}}\kappa^{\frac{d}{2}}\mathbf{u}_{1}\circ\cdots\circ\mathbf{u}_{d}\right)d\pi(\mathbf{u}_{1},\ldots,\mathbf{u}_{d})\right)\\\
\overset{(a)}{\leq}&O(\frac{1}{\sqrt{\log n}}),\end{split}$

where (a) is due to (111), (112). This has finished the proof.

##  Appendix F Proofs for the Evidence of HPC Conjecture 1 and HPDS Conjecture
2

###  F.1 Proof of Proposition 1

Without loss of generality, we can assume $N$ is a multiplier of $d$,
otherwise we can replace $N=d\lfloor\frac{N}{d}\rfloor$. Recall the planted
dense subgraph index set is $K$, and let
$K_{i}=K\bigcap[(i-1)\frac{N}{d}+1:\frac{iN}{d}]$. By symmetry, we only need
to consider recovering $K_{1}$ and $K_{2}$.

First by the same argument as (103), we can show
$|K_{1}|\asymp|K_{2}|\asymp\frac{\kappa}{d}$. Denote $\\{X_{i}^{(1)}\\}$ as
i.i.d. ${\rm{Bern}}(q_{2})$ random variables and $\\{X_{i}^{(2)}\\}$ as i.i.d.
${\rm{Bern}}(q_{1})$ random variables. Following the same notation in
Algorithm 5, for $(k_{1},k_{2})\notin K_{1}\times K_{2}$,

${\mathbf{Y}}^{(1,2)}_{[k_{1},k_{2}]}=\frac{\sum_{i=1}^{(\frac{N}{d})^{d-2}}\left(X_{i}^{(1)}-q_{2}\right)}{\sqrt{\left(\frac{N}{d}\right)^{d-2}\left(q_{2}(1-q_{2})\right)}},$

and for $(k_{1},k_{2})\in K_{1}\times K_{2}$,

${\mathbf{Y}}^{(1,2)}_{[k_{1},k_{2}]}=\frac{\sum_{i=1}^{(\frac{N}{d})^{d-2}-C(\frac{\kappa}{d})^{d-2}}\left(X_{i}^{(1)}-q_{2}\right)}{\sqrt{\left(\frac{N}{d}\right)^{d-2}\left(q_{2}(1-q_{2})\right)}}+\frac{\sum_{i=1}^{C(\frac{\kappa}{d})^{d-2}}\left(X_{i}^{(2)}-q_{2}\right)}{\sqrt{\left(\frac{N}{d}\right)^{d-2}\left(q_{2}(1-q_{2})\right)}},$

for some constant $C>0$.

By Chernoff bound, we have if $(k_{1},k_{2})\notin K_{1}\times K_{2}$

$\mathbb{P}\left(|{\mathbf{Y}}^{(1,2)}_{[k_{1},k_{2}]}|>t\right)\leq{\rm{exp}}(-t^{2}),$

and if $(k_{1},k_{2})\in K_{1}\times K_{2}$,

$\mathbb{P}\left(\left|{\mathbf{Y}}^{(1,2)}_{[k_{1},k_{2}]}-C\frac{(\frac{\kappa}{d})^{d-2}(q_{1}-q_{2})}{\sqrt{\left(\frac{N}{d}\right)^{d-2}\left(q_{2}(1-q_{2})\right)}}\right|>t\right)\leq{\rm{exp}}(-t^{2})$

So we can write ${\mathbf{Y}}=\lambda\cdot
1_{K_{1}}1_{K_{2}}^{\top}+{\mathbf{Z}}$ where
$\lambda=C\frac{(\frac{\kappa}{d})^{d-2}(q_{1}-q_{2})}{\sqrt{\left(\frac{N}{d}\right)^{d-2}\left(q_{2}(1-q_{2})\right)}}$
and entries ${\mathbf{Z}}_{ij}$ are independent subgaussian random variable
with variance $1$.

To recover $K_{1},K_{2}$, it is the same as biclustering recovery problem
studied in literature with parameters $(\frac{N}{d},|K_{1}|,|K_{2}|,\lambda)$.
By Lemma 1 of Cai et al., (2017), when

$\lambda\geq C^{\prime}\frac{\sqrt{\frac{N}{d}}}{|K_{1}|\land|K_{2}|},\text{
i.e.,
}\limsup_{N\to\infty}\log_{N}\left(\frac{\kappa^{d-1}(q_{1}-q_{2})}{\sqrt{q_{2}(1-q_{2})}}\right)\geq\frac{d}{2}-\frac{1}{2},$

then with probability at least
$1-(\frac{N}{d})^{-c}-{\rm{exp}}(-C\frac{N}{d})$, the output of the Algorithm
can exactly recover $K_{1}$ and $K_{2}$. Similar analysis holds for other
modes.

However when
$\limsup_{N\to\infty}\log_{N}\left(\frac{\kappa^{d-1}(q_{1}-q_{2})}{\sqrt{q_{2}(1-q_{2})}}\right)<\frac{d}{2}-\frac{1}{2}$,
then under a variant PC recovery conjecture Cai et al., (2017), the
biclustering recovery procedure of Algorithm 5 fails with non-trivial
probability, so as Algorithm 6.

###  F.2 Proof of Lemma 1

The proof of this lemma is by a contradiction argument. Suppose for sufficient
large $N$, there is no polynomial-time recovery algorithm can output the right
clique of $\mathcal{G}_{d}(N,1/2,\kappa)$ with success probability at least
$1-1/N$, but we can distinguish in polynomial time whether a hypergraph $G$ is
drawn from $\mathcal{G}_{d}(N,\frac{1}{2})$ or
$\mathcal{G}_{d}(N,\frac{1}{2},\kappa/3)$ with probability at least
$\frac{1}{4N^{d}}$. Denote $\varphi$ as this distinguisher.

In Algorithm 12, we provide an polynomial-time algorithm which can find a
clique of size $\kappa$ in $G$ using the distinguisher $\varphi$ for $G$ from
$\mathcal{G}_{d}(N,\frac{1}{2},\kappa)$. Denote the clique set in HPC as $K$.
We first give a high level idea why the algorithm works. When
$\mathbf{v}\subsetneq K$, by construction, after remove $\mathbf{v}$ and $X$,
at most $2\kappa/3$ nodes in the clique is removed with high probability by
concentration, thus the graph $G_{x}$ is a random graph with a planted clique
of size at least $\kappa/3$, i.e., chosen from
$\mathcal{G}_{d}(N_{x},1/2,\kappa^{\prime})$ for some
$\kappa^{\prime}>\kappa/3$. When $\mathbf{v}\subset K$, then after remove
$\mathbf{v}$ and $X$, we remove the entire clique $K$, and the remaining
hypergraph $G_{i}$ is a random graph from
$\mathcal{G}_{d}(N_{x},\frac{1}{2})$. In this case we include all vertices in
$\mathbf{v}$ to $Q$ set.

Based on the idea above, we formalize the proof next. The proof can be divided
into two steps.

Step 1. In this step, we consider $\mathbf{v}\subsetneq K$ in step 3 of
Algorithm 12. When $\mathbf{v}\subsetneq K$, then each entry of
${\mathbfcal{A}}_{[v_{1},\ldots,v_{d-1},x]}$ are independent
${\rm{Bern}}(1/2)$ random variables. Thus each vertex in clique will be
removed with probability $1/2$. By concentration result, for each $G_{x}$, we
have $\mathbb{P}(\kappa^{\prime}>\frac{\kappa}{3})\geq 1-{\rm{exp}}(-C\kappa)$
where $\kappa^{\prime}$ is the clique size in graph $G_{x}$. So $\varphi$ will
output $\mathcal{G}_{d}(N_{x},1/2,\kappa/3)$ with probability at least
$1-{\rm{exp}}(-C\kappa)-1/(4N^{d})$.

Step 2. In this step, we consider $\mathbf{v}\subset K$. Given
$\mathbf{v}\subset K$, by the construction of Algorithm 12, the whole clique
set $K$ is removed in $G_{x}$. So
$G_{x}\sim\mathcal{G}_{d}(N_{i},\frac{1}{2})$, and we have

$\begin{split}\mathbb{P}(\kappa^{\prime}>\frac{\kappa}{3})\leq{N_{x}\choose\kappa/3}(\frac{1}{2})^{{\kappa/3\choose
d}}\leq{\rm{exp}}(-C\kappa),\end{split}$

here$\kappa^{\prime}$ is the clique size in graph $G_{x}$. So $\varphi$
outputs $G_{d}(N_{x},\frac{1}{2})$ with probability at least
$1-{\rm{exp}}(-C\kappa)-\frac{1}{4N^{d}}$.

By the union bound over all possible choices of $\mathbf{v}$, there exists
$C>0$ that for $\kappa\geq C\log N$,

$\begin{split}\mathbb{P}(Q=K)&\geq 1-{N\choose
d-1}{\rm{exp}}(-C\kappa)-{N\choose d-1}\frac{1}{2N^{d}}\geq
1-\frac{1}{N}.\end{split}$

This contracts the assumption. So we have finished the proof of this lemma.

Algorithm 12 Algorithm for HPC Recovery based on HPC Detection

1:Input: hypergraph $G$ with adjacency tensor ${\mathbfcal{A}}$, HPC detection
algorithm $\varphi$.

2:Let $H=\\{\mathbf{v}:\mathbf{v}\subset[N],|\mathbf{v}|=d-1\\}$,
$Q=\emptyset$ (representing the current clique).

3:for $\mathbf{v}\in H$ do

4: Denote all vertices in $\mathbf{v}$ as
$\mathbf{v}_{1},\ldots,\mathbf{v}_{d-1}$. Let
$X=\\{x\in[N]\setminus\mathbf{v}\,|\,{\mathbfcal{A}}_{[v_{1},v_{2},\ldots,v_{d-1},x]}=1\\}$,
$G_{x}=G\setminus\\{\mathbf{v}\bigcup X\\}$, and $N_{x}=|G_{x}|$.

5: Input $G_{x}$ to the HPC detection algorithm $\varphi$. If $\varphi$
outputs $\mathcal{G}_{d}(N_{x},\frac{1}{2})$, then set $Q=Q\bigcup\mathbf{v}$.

6:end for

7:Output: $Q$.

###  F.3 Proof of Theorem 18

We begin the theorem by introducing the concept "m-gateway" proposed in
Jerrum, (1992). A state $K$ is callled m-gateway if there exists a sequence of
states $K_{0},K_{1},\ldots,K_{s}$ such that $K_{0}=K,K_{i}\oplus
K_{i+1}=1,0\leq i\leq s-1$, $|K_{s}|=m$ and $|K_{i}|>|K_{0}|$ for $1\leq i\leq
s$.

Next, we introduce Lemma 20 which is useful in the proof of this theorem.

###### Lemma 20

Suppose $0<\epsilon<1,0<\beta<\frac{1}{2}$ and
$\frac{1}{3}\epsilon<\frac{1}{2}-\beta$. For
$G\sim\mathcal{G}_{d}(N,\frac{1}{2},N^{\beta})$ and let
$m=2k-\lceil\left((1+\frac{2}{3}\epsilon)(d-1)!\log_{2}N\right)^{\frac{1}{d-1}}\rceil$
where
$k=\lceil\left((1+\frac{2}{3}\epsilon)\frac{d!}{2}\log_{2}N\right)^{\frac{1}{d-1}}\rceil$.
Let $\rho(G)$ the proportion of size k cliques in $G$ that are m-gateway. Then
$\rho(G)\leq N^{-\Omega\left((\log_{2}N)^{\frac{1}{d-1}}\right)}$ for almost
every $G$.

Recall $\Gamma$ denotes the collection of all cliques in $G$ and
$\Gamma_{k}\subseteq\Gamma$ is the set of k-cliques in $G$. Let
$Q\subseteq\Gamma_{k}$ be the set of all k-cliques that are m-gateways, where
$k,m$ are quantities defined in Lemma 20. Divide cliques in $G$ into two sets
$S$ and $\bar{S}:=\Gamma\setminus S$ where $S$ can be reached without passing
through $Q$. It is easy to see that $\Gamma_{k}\subseteq S$ and all m-cliques
are in $\bar{S}$. The intuition underlying the proof is that $Q$ is rather
small which makes it hard to transit from $S$ to m-cliques.

First we calculate the probability, in the stationary distribution, of
transiting from $S$ to $\bar{S}$ conditional on being in $S$,

$\Phi_{S}:=\mathbb{P}\left(\text{ transit from S to }\bar{S}|\text{ being in
}S\right)=\sum_{K\in
S,K^{\prime}\in\bar{S}}\pi(K)\mathbb{P}(K,K^{\prime})/(\sum_{K\in S}\pi(K)).$
(113)

By the definition of $\bar{S}$, to transit to $\bar{S}$, we need to pass nodes
in $Q$. So the numerator in (113) is bounded by $\pi(Q)$. Since
$\Gamma_{k}\subseteq S$, $\pi(S)$ in the denominator is greater or equal to
$\pi(\Gamma_{k})$. Thus the conditional transition probability in (113) is no
more than $\frac{\pi(Q)}{\pi(\Gamma_{k})}$, which is the proportion of
$k-$clique that are m-gateways in Lemma 20. Based on the results in Lemma 20,
we have

$\Phi_{S}\leq N^{-\Omega((\log_{2}N)^{\frac{1}{d-1}})}.$

Next, we make rigorous argument that the restriction on $Q$ makes it hard to
transit from $S$ to $\bar{S}$. We modify the Metropolis process to make states
in $\bar{S}$ absorbing; this is done by setting
$\mathbb{P}(K^{\prime},K)=\delta_{K^{\prime}K}$ for all $K^{\prime}\in\bar{S}$
where $\delta_{K^{\prime}K}$ is the Kronecker delta. Also define the initial
distribution $\pi_{0}$ by

$\pi_{0}(K)=\left\\{\begin{array}[]{lc}\pi(K)/\pi(S),&\text{ if }K\in S;\\\
0,&\text{otherwise}.\end{array}\right.$

Note that given the initial distribution $\pi_{0}$, the probability that the
Metropolis process transit to $S$ in the first step is $\Phi_{S}$. Also since
the states in $\bar{S}$ are absorbing, for any fixed $K\in S$, the probability
$\pi_{t}(K)$ of being in state $K$ at time $t$ is a monotonically decreasing
function of $t$. So the probability of transition from $S$ to $\bar{S}$ in
each subsequent step is bounded above by $\Phi_{S}$. Hence the expected time
of first entry into $\bar{S}$, given initial distribution $\pi_{0}$, is
bounded below by $\frac{1}{2\Phi_{S}}$. Clearly, there must be some choice of
initial state from which the expected time to reach $\bar{S}$ (and hence a
clique of size $m$) is at least $\frac{1}{2\Phi_{S}}$. This has finished the
proof.

####  F.3.1 Proof of Lemma 20

Let $\mathcal{X}$ be the set of all pairs $(G,K)$ where $K$ is the clique with
size $k$ in $G$ and $\mathcal{Y}$ be the set of pairs $(G,K)\in\mathcal{X}$
such that $K$ is also a m-gateway.

Let $V=\\{0,1,\ldots,n-1\\}$ be the set of all nodes and
$Q=\\{0,1,\ldots,\kappa-1\\}$ be the node set of planted clique. Define
$f(t)={\kappa\choose t}{N-\kappa\choose
k-t}\left(\frac{1}{2}\right)^{{k\choose d}-{t\choose d}}$ as the probability
that $t$ nodes in $K$ come from $Q$ and rest of $(k-t)$ nodes in $K$ come from
$V\setminus Q$ and let $F=\sum_{t=0}^{k}f(t)$. In the following we define a
sampling way of sampling $(G,K)$ from $\mathcal{X}$ such that it has the same
distribution as uniformly sample $(G,K)$ from k-cliques in
$G\sim\mathcal{G}_{d}(N,\frac{1}{2},\kappa)$ and we call this sampling
strategy “uniform sampling from $\mathcal{X}$". The uniform sampling of
$(G,K)$ from $\mathcal{X}$ is the following:

  * •

Pick $t\in[0,k]$ with probability $\frac{f(t)}{F}$.

  * •

Select $K^{\prime}$ of size $t$ uniformly at random from $Q$ and select
$K^{\prime\prime}$ of size $(k-t)$ uniformly at random from the subset of
$V\setminus Q$, and set $K=K^{\prime}+K^{\prime\prime}$.

  * •

Include all edges that have both endpoints in $Q$ or have both endpoints in
$K$ in $G$; decide whether to include the remaining potential edges in $G$
with probability $\frac{1}{2}$.

We first show that the size of $K^{\prime}$ is often small when
$k=\lceil\left(\frac{d!}{2}(1+\frac{2}{3}\epsilon)\log_{2}N\right)^{\frac{1}{d-1}}\rceil$.
Using the fact ${\kappa\choose t}\leq\kappa^{t}$, ${N-\kappa\choose
k-t}\leq{N-\kappa\choose k}\left(\frac{2k}{N}\right)^{t}$ and
$\kappa=N^{\beta}$, $f(t)$ could be upper bounded in the following way

$\begin{split}f(t)&\leq\kappa^{t}{N-\kappa\choose
k}\left(\frac{2k}{N}\right)^{t}\left(\frac{1}{2}\right)^{{k\choose
d}-{t\choose d}}\\\
&\leq\left(\kappa\frac{2k}{N}2^{\frac{(t-1)\ldots(t-d+1)}{d!}}\right)^{t}f(0)\\\
&\leq\left(\kappa\frac{2k}{N}2^{\frac{k^{d-1}}{d!}}\right)^{t}f(0)\leq\left(2kN^{-\frac{1}{2}+\beta+\frac{1}{3}\epsilon}\right)^{t}f(0)\\\
&\leq f(0)N^{-ct},\end{split}$

where the last inequality is because $\beta-\frac{1}{2}<-\frac{1}{3}\epsilon$.
So $f(0)=1-N^{-c}$ and for any $t^{*}>0$,

$\mathbb{P}(t\geq t^{*})\leq N^{-ct^{*}}.$ (114)

For $(G,K)$ sampled uniformly at random from $\mathcal{X}$, we show that the
probability $(G,K)\in\mathcal{Y}$ is
$N^{-\Omega\left((\log_{2}N)^{\frac{1}{d-1}}\right)}$. When
$(G,K)\in\mathcal{Y}$, by definition $K$ is a m-gateway. Consider a path that
lead the Metropolis process from $K$ to a $m$-clique and denote $K^{*}$ as the
first clique in this path satisfying $|K^{*}\setminus K|=m-k$. Set
$A=K^{*}\setminus K$. Then, $a=|A|=m-k$. Since $|K^{*}|>k$, $|K^{*}\bigcap
K|>k-a$, there exists a set $B\subseteq K$ of cardinality $b=k-a=2k-m$ such
that the bipartite subgraph of $G$ induced by $A$ and $B$ is complete. So
condition on $t\leq t^{*}$, the probability that $(G,K)\in\mathcal{Y}$ is less
than the probability of the existence of the complete bipartite graph between
$A$ and $B\setminus K^{\prime}$ where $|B\setminus K^{\prime}|\geq b-t^{*}$,
i.e.,

$\begin{split}&\mathbb{P}\left((G,K)\in\mathcal{Y}|(G,K)\in\mathcal{X},\left|B\bigcap
Q\right|\leq t^{*}\right)\leq{N-k\choose m-k}{k\choose
2k-m}2^{-(m-k){b-t^{*}\choose d-1}}\\\ &\leq{N\choose m-k}{k\choose
m-k}2^{-(m-k){b-t^{*}\choose d-1}}\\\
&\leq\left(\frac{eN}{m-k}\frac{ek}{m-k}2^{-{2k-m-t^{*}\choose
d-1}}\right)^{m-k}\\\
&\leq\left(\frac{eN}{m-k}\frac{ek}{m-k}2^{-\frac{(2k-m-t^{*}-d+2)^{d-1}}{(d-1)!}}\right)^{m-k}\\\
&\leq\left(\frac{eN}{m-k}\frac{ek}{m-k}N^{-1-\frac{1}{6}\epsilon}\right)^{m-k}\leq
N^{-\Omega\left((\log_{2}N)^{\frac{1}{d-1}}\right)},\end{split}$ (115)

here the first inequality is because all hyper-edges between $|B\setminus
K^{\prime}|$ and $A$ are connected with probability $1/2$ by construction and
in the forth inequality, we choose $t^{*}$ such that
$2k-m-t^{*}=\lceil\left((1+\frac{1}{3}\epsilon)(d-1)!\log_{2}N\right)^{\frac{1}{d-1}}\rceil$
and for large enough $N$, we have
$2k-m-t^{*}-d+2\geq\lceil\left((1+\frac{1}{6}\epsilon)(d-1)!\log_{2}N\right)^{\frac{1}{d-1}}\rceil$.

Using Bayesian formula and (114), (115) with the choice of
$t^{*}=2k-m-\lceil\left((1+\frac{1}{3}\epsilon)(d-1)!\log_{2}N\right)^{\frac{1}{d-1}}\rceil$,
and marginalizing $\left|B\bigcap Q\right|\leq t^{*}$ we get

$\mathbb{P}\left((G,K)\in\mathcal{Y}|(G,K)\in\mathcal{X}\right)\leq
N^{-\Omega((\log_{2}N)^{\frac{1}{d-1}})}.$ (116)

Given $G\in\mathcal{G}_{d}(N,\frac{1}{2},\kappa)$ with $\kappa=N^{\beta}$, let
$X=X(G)$ be the number of $k$-cliques in $G$ and $Y=Y(G)$ be the number of
$k$-cliques that are also m-gateways. By the uniform sampling property and
(116), we have

$\frac{\mathbb{E}(Y)}{\mathbb{E}(X)}=\mathbb{P}\left((G,K)\in\mathcal{Y}|(G,K)\in\mathcal{X}\right)\leq
N^{-\Omega((\log_{2}N)^{\frac{1}{d-1}})}.$

So to show the result $\frac{Y}{X}=N^{-\Omega((\log_{2}N)^{\frac{1}{d-1}})}$,
we only need to show that $X,Y$ are concentrated around
$\mathbb{E}(X),\mathbb{E}(Y)$. Let $c(N)$ be a sequence that goes to $\infty$
as $N\to\infty$, since $\mathcal{Y}$ is non-negative, by Markov inequality,
$\mathbb{P}(\mathcal{Y}\geq\mathbb{E}(Y)c(N))\leq\frac{1}{c(N)}\to 0$. Since
the subgraph of $G$ induced by $V\setminus Q$ is a random Erdős-Rényi graph on
$N-\kappa$ vertices, by the same argument of Bollobás, (2001) p284, the number
of $k$-clique in $G$ is concentrated and we have

$X\geq\frac{3}{4}{N-\kappa\choose k}2^{-{k\choose d}}+{\kappa\choose k}.$

At the same time, $\mathbb{E}(X)={N-\kappa\choose k}2^{-{k\choose
d}}+{\kappa\choose k}$, and this yields $X\geq\frac{1}{2}\mathbb{E}(X)$ for
almost every $G$. Finally we have

$\frac{Y}{X}\leq\frac{c(N)\mathbb{E}(Y)}{\frac{1}{2}\mathbb{E}(X)}\leq
2c(N)N^{-\Omega((\log_{2}N)^{\frac{1}{d-1}})}\leq
O(N^{-\Omega((\log_{2}N)^{\frac{1}{d-1}})}),$

the last inequality is because we can choose $c(N)$ such that it grows slow
enough.

###  F.4 Proof of Theorem 19

We first introduce some preliminary results in literature we will use in the
proof. The following Proposition 2 comes from Hopkins, (2018).

######  Proposition 2 (Page 35 of Hopkins, (2018))

Let likelihood ratio be
${\rm{LR}}(x)=\frac{p_{H_{1}}(x)}{p_{H_{0}}(x)}:\Omega^{n}\to\mathbb{R}$. For
every $D\in\mathbb{Z}_{+}$, we have

$\frac{{\rm{LR}}^{\leq D}-1}{\|{\rm{LR}}^{\leq D}-1\|}=\mathop{\rm
arg\max}_{\begin{subarray}{c}f\in D-\text{simple}:\\\
\mathbb{E}_{H_{0}}f^{2}(X)=1,\mathbb{E}_{H_{0}}f(X)=0\end{subarray}}\mathbb{E}_{H_{1}}f(X)$

and

$\|{\rm{LR}}^{\leq
D}-1\|=\max_{\begin{subarray}{c}f:\mathbb{E}_{H_{0}}f^{2}(X)=1,\\\
\mathbb{E}_{H_{0}}f(X)=0\end{subarray}}\mathbb{E}_{H_{1}}f(X),$

where $\|f\|=\sqrt{\mathbb{E}_{H_{0}}f^{2}(X)}$ and $f^{\leq_{H_{0}}D}$ is the
projection of a function $f$ to the span of coordinate-degree-D functions,
where the projection is orthonormal with respect to the inner product
$\langle\cdot,\cdot\rangle_{H_{0}}$. When it is clear from the context, we may
drop the subscript $H_{0}$.

By the above Proposition, we know to bound $\mathbb{E}_{H_{1}}f(G)$ for $f$
satisfying $\mathbb{E}_{H_{0}}f(G)=0$ and $\mathbb{E}_{H_{0}}f^{2}(G)=1$, we
just need to bound $\|{\rm{LR}}^{\leq D}-1\|$.

Also suppose $D\geq 1$ is fixed, $f_{0},f_{1},\ldots,f_{m}:\Omega^{n}\to R$
are orthonormal basis for the coordinate-degree $D$ functions (with respect to
$\langle\cdot,\cdot\rangle_{H_{0}}$), and that $f_{0}(x)=1$ is a constant
function. Then by the property of basis functions, we have

$\begin{split}\|{\rm{LR}}^{\leq D}-1\|^{2}&=\sum_{i=1}^{m}\langle
f_{i},{\rm{LR}}^{\leq
D}-1\rangle^{2}=\sum_{i=1}^{m}\left(\mathbb{E}_{H_{0}}(f_{i}(X)({\rm{LR}}^{\leq
D}-1))\right)^{2}\\\
&\overset{(a)}{=}\sum_{i=1}^{m}\left(\mathbb{E}_{H_{0}}(f_{i}(X){\rm{LR}}(X))\right)^{2}=\sum_{i=1}^{m}(\mathbb{E}_{H_{1}}f_{i}(X))^{2},\end{split}$

here (a) is because ${\rm{LR}}-({\rm{LR}}^{\leq D}-1)$ is orthogonal to
$f_{i}$ by assumption.

Now, we start the proof of the main result. We consider a simple variant of
hypergraphic planted clique model with $G\sim\mathcal{G}_{d}(N,\frac{1}{2})$
and each vertex is included in the clique set with probability
$\frac{\kappa}{N}$ and denote its adjacency tensor as ${\mathbfcal{A}}$. By
concentration result, the clique size of the modified hypergraphic planted
clique is of order $\kappa$ and it is easy to see that if we could solve above
modified hypergraphic planted clique problem, then we can solve the original
hypergraphic planted clique problem with high probability. In the HPC problem,
by the Boolean Fourier analysis O’Donnell, (2014), functions
$\\{\chi_{\alpha}({\mathbfcal{A}})=\prod_{(i_{1},\ldots,i_{d})\in\alpha}(2{\mathbfcal{A}}_{[i_{1},\ldots,i_{d}]}-1)\\}_{\alpha\subseteq{N\choose
d},|\alpha|\leq|D|}$ form an orthonormal basis for the degree-D functions,
i.e. $f_{i}$s mentioned above. Fix $\alpha\subseteq{N\choose d}$ and the
planted clique indices set $S$. Then

$\mathbb{E}\chi_{\alpha}({\mathbfcal{A}})=\mathbb{E}_{S}\prod_{(i_{1},\ldots,i_{d})\in\alpha}\mathbb{E}\left[(2{\mathbfcal{A}}_{[i_{1},\ldots,i_{d}]}-1)|S\right].$

This is non-zero if and only if $V(\alpha)\subseteq S$ where $V(\alpha)$ is
the vertex set appear in $\alpha$. So we have

$\mathbb{E}\chi_{\alpha}({\mathbfcal{A}})=(\frac{\kappa}{N})^{|V(\alpha)|}.$
(117)

If $|\alpha|\leq D$, then $|V(\alpha)|\leq dD$ and for every $t\leq dD$, we
can compute the number of sets $\alpha$ with $|V(\alpha)|=t$ and $|\alpha|\leq
D$ is ${N\choose t}{{t\choose d}\choose|\alpha|}$ and denote this set of
$\alpha$ as $\mathcal{E}_{0}$.

Let $D=C\log N,\kappa=N^{\frac{1}{2}-\epsilon}$, then

$\begin{split}\sum_{\alpha\in\mathcal{E}_{0},0<|\alpha|\leq
D}(\mathbb{E}_{H_{1}}\chi_{\alpha}({\mathbfcal{A}}))^{2}&\overset{(a)}{\leq}\sum_{t\leq
dC\log N}\left(\frac{\kappa}{N}\right)^{2t}{N\choose t}{{t\choose
d}\choose|\alpha|}\\\ &\leq\sum_{t\leq dC\log N}N^{-t-2\epsilon
t}N^{t}{t\choose d}^{\min(|\alpha|,{t\choose d}/2)}\\\ &\leq\sum_{t\leq dC\log
N}N^{-2\epsilon t}(t^{d})^{\min(|\alpha|,t^{d})}\\\ &\leq\sum_{t\leq(C\log
N)^{\frac{1}{d}}}N^{-2\epsilon t}t^{dt^{d}}+\sum_{(C\log N)^{\frac{1}{d}}\leq
t\leq dC\log N}N^{-2\epsilon t}t^{dC\log N}\\\ &=\sum_{t\leq(C\log
N)^{\frac{1}{d}}}{\rm{exp}}(-2\epsilon t\log N+dC\log N\log t)\\\
&\quad+\sum_{(C\log N)^{\frac{1}{d}}\leq t\leq dC\log N}{\rm{exp}}(-2\epsilon
t\log N+dC\log N\log t)\\\ &\leq\sum_{t\leq(C\log
N)^{\frac{1}{d}}}{\rm{exp}}(-\epsilon t\log N)+\sum_{(C\log
N)^{\frac{1}{d}}\leq t\leq dC\log N}{\rm{exp}}(-\epsilon t\log
N)=O(1),\end{split}$ (118)

where (a) is due to (117) and last inequality is due to the fact that when $N$
is large enough, we have $\epsilon t\log N\geq C\log t\log N$.