Here step $1$ can be argued as follows.

  * a.

For the first term, note that the hyperedge $e^{+}$ consists of vertices with
biases within $[\delta^{C^{*}_{0}},1/2]$. Furthermore,
$\nu_{e^{+}}=\max_{i,j\in
e^{+}}\|v^{\prime}_{i}-v^{\prime}_{j}\|^{2}\leq\max_{i,j\in
e}\|v^{\prime}_{i}-v^{\prime}_{j}\|^{2}\leq\nu_{e}$. Therefore, we can use
case 1 to bound the probability of $e^{+}$ getting cut.

  * b.

For the second term, note that $e^{-}$ consists of vertices with biases within
$[1/2,1-\delta^{C^{*}_{0}}]$. Similar to the previous case, we get
$\nu_{e^{-}}\leq\nu_{e}$. Therefore, we can use case 2 to bound the
probability of $e^{-}$ getting cut.

  * c.

The third term constitutes the analysis of an edge getting cut for which we
use Lemma A.5 from [RT11]. Additionally we observe that
$\sqrt{\nu_{e}}\lesssim\sqrt{\nu_{e}\alpha_{e}}$ since $\alpha_{e}\geq 0.4$
from the above discussion.

Step $2$ follows from the observations that

$\max\left(\alpha_{e^{+}},\alpha_{e^{-}}\right)\leq\frac{1}{2}\leq\frac{5\alpha_{e}}{4}\
\ \ \ \textnormal{ and }\ \ \ \ \max(\nu_{e^{+}},\nu_{e^{-}})\leq\nu_{e}.$

$\square$

###  7.1 Proof of Theorem 1.1

We begin by recalling some notation we will use in this proof. Recall that
$H=(V,E,w,W)$ is the weighted hypergraph constructed using Lemma 3.1, where
$w:E\to\mathbbm{R}_{\geq 0}$ is the edge weight function and
$W:V\to\mathbbm{R}_{\geq 0}$ is the vertex weight function. The proof of the
theorem consists of two parts: first we will establish that the weight of the
subset $S$ rounded by Algorithm 1 in Step 14 is $\Theta(\delta\cdot W(V))$.
Conditioned on this, we will show that the subset $S$ has the intended
hypergraph expansion guarantee. Finally using Lemma 3.1 (vi), we can conclude
the set $S$ can be used to identify a set $S^{\prime}\subset V_{G}$ in $G$ of
size $\sim\delta|V_{G}|$ with matching (up to constant factors) vertex
expansion guarantee.

#### Bounding vertex weight $W(S)$

Recall that $S\subset V$ is the set rounded off in Step 14 of Algorithm 1. Let
$i\sim V$ denote the random draw of a vertex according to vertex weight
function $W$. To begin with, observe that the conditioned degree-$2$ pseudo-
distribution $\mu$ obtained in Step 1 must satisfy:

${\mathsf{E}}_{i\sim V}\big{[}\mu_{i}\big{]}={\mathsf{E}}_{i\sim
V}\Pr_{X_{i}\sim\mu}\left[X_{i}=1\right]=\delta.$

Furthermore, using Lemma 4.3, we can relate the analogous expression on the
shifted biases to the above as

$\left|{\mathsf{E}}_{i\sim
V}\big{[}\mu^{\prime}_{i}\big{]}-{\mathsf{E}}_{i\sim
V}\big{[}\mu_{i}\big{]}\right|\leq\delta^{10}$

For a subset $T\subseteq V$, let $\delta_{\rm rel}(T)$ denote the relative
weight of the set with respect to vertex weight function $W$. We have the
following bounds on the expected relative vertex weight of the set rounded off
by the algorithm in Line 14:

$\displaystyle{\mathsf{E}}_{S}\left[\delta_{\rm
rel}(S)\right]:={\mathsf{E}}_{S}\left[\frac{W(S)}{W(V)}\right]={\mathsf{E}}_{S}{\mathsf{E}}_{i\sim
V}\left[\mathbbm{1}_{S}(i)\right]={\mathsf{E}}_{i\sim
V}\left[\mu^{\prime}_{i}\right]\in\delta(1\pm o_{\delta}(1)).$ (36)

On the other hand, from Lemma 6.2 we have

$\Pr_{S}\Big{[}\delta_{\rm
rel}(S)\notin[0.99,1.01]{\mathsf{E}}_{S}\left[\delta_{\rm
rel}(S)\right]\Big{]}\leq 0.1.$ (37)

Therefore combining the bounds from (36) and (37) we have

$\Pr_{S}\left[\frac{W(S)}{W(V)}\notin[0.9,1.1]\delta\right]\leq 0.1.$ (38)

#### Bounding the expansion.

To begin with, recall that from Lemma 4.2

$\frac{1}{\delta W(V)}\sum_{e\in E}w(e)\max_{i,j\in
e}\Pr_{X_{ij}\sim\mu^{*}}\left[X_{i}\neq X_{j}\right]\leq\phi^{\sf
V}_{\delta},$

Denoting $\Delta_{e}=\max_{i,j\in e}\Pr_{X_{ij}\sim\mu}\left[X_{i}\neq
X_{j}\right]$, with probability at least $0.9$ over the choice of $\mu$
obtained by the random conditioning $X_{t}\leftarrow\alpha$, using Markov’s
inequality we have

$\frac{1}{\delta W(V)}\sum_{e\in E}w(e)\Delta_{e}\leq 10\cdot\phi^{\sf
V}_{\delta},$ (39)

Further, conditioning on the above, we observe that

$\displaystyle\sum_{e\in E}w(e)\nu_{e}$ $\displaystyle=\sum_{e\in
E}\max_{i,j\in e}\|v^{\prime}_{i}-v^{\prime}_{j}\|^{2}$ (40)
$\displaystyle\leq\sum_{e\in E}w(e)\max_{i,j\in e}\|v_{i}-v_{j}\|^{2}$
$\displaystyle=4\sum_{e\in E}w(e)\Delta_{e}$ $\displaystyle\leq 40\phi^{\sf
V}_{\delta}\left(\delta W(V)\right),$ (41)

where the last step is using (39). Next, we account for the weight of edges
removed in the deletion step.

###### Claim 7.2

The deletion step (Step 1) removes at most $10\sum_{e\in E}w(e)\nu_{e}$ weight
of edges.

  * Proof.

We can bound the weight of edges deleted in Step 1 as follows.

$\sum_{e\in E}w(e)\nu_{e}\geq\sum_{\begin{subarray}{c}e\in E\\\ \nu_{e}\geq
0.1\end{subarray}}w(e)\nu_{e}\geq 0.1\sum_{\begin{subarray}{c}e\in E\\\
\nu_{e}\geq 0.1\end{subarray}}w(e)$

which on rearranging gives us that the weight of edges is deleted is at most
$10\sum_{e}\nu_{e}w(e)$. $\square$

Finally, the following claim accounts for the cost of edges cut from the
rounding step.

###### Claim 7.3

For every edge $e\in E$ such that $\nu_{e}\leq 0.1$ we have

$\Pr\left[e\textrm{ is cut}\right]\lesssim\sqrt{\mu^{\prime}_{v(e)}\nu_{e}\log
d\log(1/\delta)}+\tilde{O}(d)\cdot\nu_{e}(\log(1/\delta))^{2}$

where recall that $v(e):=\pi(e)\in e$ is the unique vertex identified by edge
$e$ from Lemma 3.1 (v).

  * Proof.

From Lemma 3.1 (v), recall that every hyperedge $e\in E$ is uniquely
identified with a vertex $v(e)\in V$ such that $v(e)\in e$. We shall need the
following observation.

###### Observation 7.4

For every hyperedge $e$, we have $\alpha_{e}\leq\mu^{\prime}_{v(e)}+2\nu_{e}$.

  * Proof.

Fix a hyperedge $e$, and let $i_{0}\in e$ be such that
$\alpha_{e}=\min(\mu^{\prime}_{i_{0}},1-\mu^{\prime}_{i_{0}})$. Hence,

$\alpha_{e}=\min(\mu^{\prime}_{i_{0}}~{},1-\mu^{\prime}_{i_{0}})\leq\mu^{\prime}_{i_{0}}\leq\mu^{\prime}_{v(e)}+2\nu_{e}$

where the last inequality follows from Claim 4.6. $\square$

Combining the above with Lemma 7.1, we can establish

$\displaystyle\Pr\left[e\mbox{ is cut }\right]$ $\displaystyle\leq$
$\displaystyle\sqrt{\alpha_{e}\nu_{e}\log
d\log(1/\delta)}+\tilde{O}(d)\cdot\nu_{e}(\log(1/\delta))^{2}$ (42)
$\displaystyle\overset{1}{\leq}$
$\displaystyle\sqrt{(\mu^{\prime}_{v(e)}+2\nu_{e})\nu_{e}\log
d\log(1/\delta)}+\tilde{O}(d)\cdot\nu_{e}(\log(1/\delta))^{2}$
$\displaystyle\overset{2}{\leq}$
$\displaystyle\sqrt{\mu^{\prime}_{v(e)}\nu_{e}\log
d\log(1/\delta)}+2\nu_{e}\sqrt{\log
d\log(1/\delta)}+\tilde{O}(d)\cdot\nu_{e}\log(1/\delta)^{2}$
$\displaystyle\overset{3}{\leq}$
$\displaystyle\sqrt{\mu^{\prime}_{v(e)}\nu_{e}\log
d\log(1/\delta)}+\tilde{O}(d)\cdot\nu_{e}(\log(1/\delta))^{2}$

where step $1$ uses Observation 7.4, step 2 uses
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for nonnegative $a,b$, and step $3$ follows
by observing that the second term in the previous expression is dominated by
the third term. $\square$

Cleaning up. Note that with probability at least $0.8$, we have
$W(S)\in[0.9\delta n,1.1\delta n]$ and (41) holds. Using this we can derive
the following bound on the weighted sum of shifted biases:

$\displaystyle\sum_{e\in E}w(e)\mu^{\prime}_{v(e)}$ $\displaystyle=\sum_{e\in
E}W(v(e))\mu^{\prime}_{v(e)}$ $\displaystyle\overset{1}{\leq}\sum_{e\in
E}W(v(e))\mu_{v(e)}+\delta^{C^{*}_{0}}\sum_{e\in E}W(v(e))$
$\displaystyle=\sum_{i\in V}W(i)\mu_{i}+\delta^{C^{*}_{0}}\sum_{i\in V}W(i)$
$\displaystyle\overset{2}{\leq}\delta n+\delta^{C^{*}_{0}}n\leq 2\delta n,$
(43)

where in step $1$ above, we apply the first point of Claim 4.3 point wise to
bound every $\mu^{\prime}_{v(e)}$. In step $2$, we bound the first term using
the feasibility of $\mu_{i}$’s from the SDP solution, and the second term is
bounded using the weight bound from Lemma 3.1. Now we are ready to bound the
hyperedge expansion of $S$ in $H$ as:

$\displaystyle\phi^{\sf E}_{H}(S)\lesssim$ $\displaystyle\frac{\sum_{e\in
E}w(e)\left(\sqrt{\mu^{\prime}_{v(e)}\nu_{e}\log
d\log(1/\delta)}+\tilde{O}(d)\cdot\nu_{e}(\log(1/\delta))^{2}\right)}{W(S)}$
$\displaystyle\lesssim\sum_{e\in
E}w(e)\frac{\sqrt{\mu^{\prime}_{v(e)}\nu_{e}\log d\log(1/\delta)}}{\delta
n}+\frac{\sum_{e\in E}\tilde{O}(d)\cdot
w(e)\nu_{e}(\log(1/\delta))^{2}}{\delta n}$ (Since $W(S)\geq 0.9\delta n$)
$\displaystyle\leq\sqrt{\frac{\sum_{e\in E}w(e)\mu^{\prime}_{v(e)}}{\delta
n}}\sqrt{\frac{\sum_{e\in E}w(e)\nu_{e}\log d\log(1/\delta)}{\delta
n}}+\tilde{O}(d)\cdot\phi^{\sf V}_{\delta}(\log(1/\delta))^{2}$ (Using (41))
$\displaystyle\lesssim\sqrt{\phi^{\sf V}_{\delta}\log
d\log(1/\delta)}+\tilde{O}(d)\cdot\phi^{\sf V}_{\delta}(\log(1/\delta))^{2}.$

where in the last step we bound the first term using the bound from (43) and
the second term using (41).

Putting things together. The above arguments imply that with probability at
least $0.9$, the set $S\subset V$ constructed in line 14 satisfies
$|S|\in(1\pm o_{\delta}(1))\cdot|V_{G}|$ and

$\phi^{E}_{H}(S)\lesssim\sqrt{\phi^{\sf V}_{\delta}\log
d\log(1/\delta)}+\tilde{O}(d)\cdot\phi^{\sf V}_{\delta}(\log(1/\delta))^{2}.$

Then in final step of the Algorithm 1 (Line 1), using item (vi) of Lemma 3.1,
the algorithm can find a subset $S^{\prime}\subseteq V_{G}$ such that
$|S^{\prime}|\in[0.8,1.2]\delta n$ and

$\phi^{\sf V}_{G}(S^{\prime})\leq\phi^{\sf E}_{H}(S)\lesssim\sqrt{\phi^{\sf
V}_{\delta}\log d\log(1/\delta)}+\tilde{O}(d)\cdot\phi^{\sf
V}_{\delta}(\log(1/\delta))^{2},$

which completes the proof of Theorem 1.1.

##  8 $f(d)$-inapproximability for SSVE

We prove the following SSEH based hardness result for SSVE which rules out any
$f(d)$-approximation for SSVE.

See 1.1

Our starting point is the following alternative but equivalent form of the
SSEH.

######  Conjecture 8.1 ([RS10, RST12])

Given an $\varepsilon\in(0,1),M\geq 1$, there exists $\delta\in(0,1)$ such
that the following holds. Given a regular graph $G=(V,E)$, it is NP-Hard to
distinguish between the following two cases.

  * •

YES: There exists $S\subseteq V$ such that $\mu(S)=\delta$ and
$\phi(S)\leq\varepsilon$.

  * •

NO: For every $S\subseteq V$ such that $\mu(S)\in[\delta/M,M\delta]$, we have
$\phi(S)\geq 1-\varepsilon$.

For a regular graph $G=(V,E)$ and $S\subseteq V$, we use $\mu_{G}(S)$ to
denote $|S|/|V|$. We first describe a degree reduction procedure which
approximately maintains the completeness and soundness guarantees of SSEH.

######  Lemma 8.2 (Folklore)

There exists constants $g\in\mathbbm{N}$ and $\alpha_{0}\in(0,1)$ and a
polynomial time reduction from any regular
$(\varepsilon,1-\varepsilon)$-instance with parameters $M$ and $\delta$ (as
defined in Conjecture 8.1) to a $(g+1)$-regular instance
$G^{\prime}=(V^{\prime},E^{\prime})$ with the following properties.

  * •

Completeness. If $G$ is a YES instance, then there exists $S\subseteq
V^{\prime}$ such that $\mu_{G^{\prime}}(S)=\delta$ and
$\phi_{G^{\prime}}(S)\leq\varepsilon/(g+1)$.

  * •

Soundness. If $G$ is a NO instance, then for every $S\subseteq V^{\prime}$
such that $\mu_{G^{\prime}}(S)=\delta$, we have
$\phi_{G^{\prime}}(S)\geq\alpha_{0}$.

The reduction for the above lemma is folklore and uses the replacement product
trick introduced in [PY91]; for e.g., [RS13] also use an identical
construction for degree reduction for a different range of parameters. We
include a proof of it here for our setting for completeness.

  * Proof.

Construction. Given a $d$-regular graph $G=(V,E)$, we construct a graph
$G^{\prime}=(V^{\prime},E^{\prime})$ as follows. Let $H=(V_{H},E_{H})$ be a
$g$-regular $\alpha$-expander on $d$-vertices. For every $i\in V$, we replace
it with a copy of $H$ in $G^{\prime}$, which we call $H_{i}$ on vertex set
$\mathcal{C}_{i}$. (Note that by construction $|\mathcal{C}_{v}|=d$). For
every $i\in V$, fix an arbitrary ordering $i(1),i(2),\ldots,i(d)$ on the
vertices in $\mathcal{C}_{i}$. For every edge $(i,j)\in E$, we identify a
unique vertex $i(a)\in\mathcal{C}_{i}$ and $j(b)\in\mathcal{C}_{j}$ and put an
edge between $(i(a),j(b))$ in $G^{\prime}$. Note that this can be done
consistently such that in the resultant $G^{\prime}$, every vertex has degree
$g+1$.

We fix $M=2$ and argue completeness and soundness of the reduction.

Completeness. Suppose there exists a set $S\subseteq V$ such that
$\mu_{G}(S)=\delta$ and $\phi(S)\leq\varepsilon$. Then consider the
corresponding set $S^{\prime}=\cup_{i\in S}\mathcal{C}_{i}$. It is easy to see
that $\mu_{G^{\prime}}(S)=\delta$ and
$\phi_{G^{\prime}}(S)=|\partial_{G}(S)|/((g+1)(d\delta
n))\leq\varepsilon/(g+1)$.

Soundness. Suppose there exists a set $S^{\prime}\subset V^{\prime}$ of
measure $\delta$ such that
$\phi_{G^{\prime}}(S)\leq\varepsilon^{\prime}/(g+1)$ where
$\varepsilon^{\prime}=\alpha/100$. Then
$\left|\partial_{G^{\prime}}(S^{\prime})\right|\leq\varepsilon^{\prime}d\delta
n$.

For every $i\in V$, let $\mathcal{C}^{\prime}_{i}\overset{\rm
def}{=}\mathcal{C}_{i}\cap S^{\prime}$ and $\gamma_{i}\overset{\rm
def}{=}|\mathcal{C}^{\prime}_{i}|/|\mathcal{C}_{i}|=|\mathcal{C}^{\prime}_{i}|/d$.
Define

$T_{\rm Good}\overset{\rm def}{=}\left\\{i\in V|\gamma_{i}\geq
1/2\right\\}\qquad\textnormal{and}\qquad T_{\rm bad}\overset{\rm
def}{=}\left\\{i\in V|\gamma_{i}<1/2\right\\}.$

Note that by definition of $H$ we have

$\displaystyle\varepsilon^{\prime}d\delta
n\geq\left|\partial_{G^{\prime}}(S^{\prime})\right|$
$\displaystyle\geq\sum_{i\in T_{\rm
Bad}}|E_{G^{\prime}}(\mathcal{C}^{\prime}_{i},\mathcal{C}_{i}\setminus\mathcal{C}^{\prime}_{i})|$
$\displaystyle\geq\alpha\sum_{i\in{T_{\rm
bad}}}\min\\{\gamma_{i},1-\gamma_{i}\\}\cdot g\cdot d$ (Expansion of
$H_{i}$’s) $\displaystyle\geq\alpha\sum_{i\in{T_{\rm bad}}}\gamma_{i}gd$
(Definition of $T_{\rm bad}$)

or rearranging we get that

$\sum_{i\in T_{\rm
bad}}\mu_{G^{\prime}}(\mathcal{C}^{\prime}_{i})=\frac{1}{n}\sum_{i\in{T_{\rm
bad}}}\gamma_{i}\leq\frac{1}{n}\cdot\frac{\varepsilon^{\prime}d\delta
n}{\alpha gd}=\frac{\varepsilon^{\prime}\delta}{\alpha g}.$ (44)

Therefore we have $\sum_{i\in T_{\rm
good}}\mu(\mathcal{C}^{\prime}_{i})\geq\delta-\varepsilon^{\prime}\delta/(\alpha
g)\geq 0.99\delta$. Now note that every cloud $\mathcal{C}^{\prime}_{i}$
corresponding to each $i\in T_{\rm good}$ can contribute at most $1/n$ mass
(recall that $T_{\rm good}\subseteq V$), and by definition of $T_{\rm good}$,
must contribute at least $1/(2n)$ mass. Therefore, using the upper and lower
bound we get that $|T_{\rm good}|\in[0.99\delta n,2\delta n]$. Now using the
fact that $\mathcal{C}_{i}$’s are disjoint, we note that

$\displaystyle\sum_{\begin{subarray}{c}i,j\in T_{\rm good}\\\ i\neq
j\end{subarray}}\left|E_{G^{\prime}}(\mathcal{C}^{\prime}_{i},\mathcal{C}^{\prime}_{j})\right|$
$\displaystyle\leq\sum_{\begin{subarray}{c}i,j\in T_{\rm good}\\\ i\neq
j\end{subarray}}\left|E_{G}(i,j)\right|={\sf vol}_{G}(T_{\rm
good})-\phi_{G}(T_{\rm good}){\sf vol}_{G}(T_{\rm good})$
$\displaystyle\leq{\sf vol}_{G}(T_{\rm good})-(1-\varepsilon){\sf
vol}_{G}(T_{\rm good})=\varepsilon{\sf vol}_{G}(T_{\rm good})$
$\displaystyle\leq 2\varepsilon d\delta n$ (45)

where in the second inequality we use that $\phi_{G}(A)\geq(1-\varepsilon)$
for every $A$ such that ${\sf vol}_{G}(A)\in[\delta dn/2,2\delta dn]$.

Note that every $i(a)\in\cup_{j\in T_{\rm good}}\mathcal{C}^{\prime}_{j}$ has
exactly one $E$-edge incident on it. Therefore the total number of $E$-edge
incident on $\cup_{j\in T_{\rm good}}\mathcal{C}^{\prime}_{j}$ is at least

$|\cup_{j\in T_{\rm good}}\mathcal{C}^{\prime}_{j}|=\sum_{j\in T_{\rm
good}}|\mathcal{C}^{\prime}_{j}|=\sum_{j\in T_{\rm
good}}\gamma_{i}d\geq|T_{\rm good}|d/2\geq\delta nd/4$

which uses $\gamma_{i}\geq 1/2\ ~{}\forall i\in T_{\rm good}$.

Out of these, at most $(\varepsilon^{\prime}/\alpha g)\delta dn$ are incident
on $T_{\rm bad}$ (from (44)) and at most $2\varepsilon d\delta n$ are incident
on itself (using (45)). Therefore, at least

$d\delta n/4-(\varepsilon^{\prime}/\alpha g)\delta dn-2\varepsilon d\delta
n\geq d\delta n/8$

number of $E$-edges leave the set $S^{\prime}$ from $\cup_{i\in T_{\rm
good}}\mathcal{C}^{\prime}_{i}$. Therefore,
$|\partial_{G^{\prime}}(S^{\prime})|\geq d\delta n/8$, which gives us a
contradiction. $\square$

###### Fact 8.3

For any graph $G=(V,E)$ with maximum degree $d$ we have

$\phi^{V}_{\delta}(G)\leq\phi^{E}_{\delta}(G)\leq d\cdot\phi^{V}_{\delta}(G).$

We now prove Proposition 1.1.

  * Proof of Proposition 1.1.

Fixing $\varepsilon$, let $G=(V,E)$ be an instance of SmallSetEdgeExpansion as
guaranteed by Conjecture 8.1. Let $G^{\prime}=(V^{\prime},E^{\prime})$ be the
graph obtained by instantiating Lemma 8.2 on $G=(V,E)$. Note that from the
guarantee of Lemma 8.2, we have that the maximum degree of $G^{\prime}$ is
$g+1$. Denote $\varepsilon^{\prime}:=\varepsilon/(g+1)$. Then, if $G$ is a YES
instance, using Proposition 8.3 we have

$\phi^{V^{\prime}}_{\delta}(G^{\prime})\leq\phi^{E^{\prime}}_{\delta}(G^{\prime})\leq\frac{\varepsilon}{g+1}.$

On the other hand, if $G$ is a NO instance, then using the lower bound from
Proposition 8.3 we get that

$\phi^{V^{\prime}}_{\delta}(G^{\prime})\geq\frac{\phi^{E^{\prime}}_{\delta}(G^{\prime})}{g+1}\geq\frac{1}{8g^{2}}.$

Putting the two case together, and setting $\varepsilon<f^{-1}(8g)$
establishes the claim. $\square$

##  9 Proof of Theorem 1.2

The algorithm for Theorem 1.2 is almost identical to that of Theorem 1.1; the
only change required is that the cardinality/expected weight constraint now
compares with the total weight of edges, in order to accommodate the
definition of hypergraph expansion. For completeness we state the algorithm
below.

Input: A hypergraph $H=(V,E)$ of arity $d$, volume parameter
$\delta\in(0,1/2]$, contant $C^{*}_{0}$, and an error parameter $t$.

1 Solve the following $R\overset{\rm def}{=}(t+2)$-round Lasserre relaxation
of  $\displaystyle\min$ $\displaystyle\frac{1}{\delta
W(V)}{\mathsf{E}}_{S\subseteq_{t}V_{G}}{\mathsf{E}}_{X_{S}\sim\mu_{S}}\sum_{e\in
E}w(e)\max_{i,j\in e}\Pr_{(X_{i},X_{j})\sim\mu_{ij}|X_{S}}\left[X_{i}\neq
X_{j}\right]$ $\displaystyle{\mathsf{E}}_{i\sim
V}W(i)\Pr_{X_{i}\sim\mu_{i}|X_{S}\leftarrow\alpha}\Big{[}X_{i}=1\Big{]}\leq
2\delta d\sum_{e\in E}w(e)$
$\displaystyle~{}\forall(R-1)\textnormal{-admissible}(S,\alpha)$
$\displaystyle|\mu_{i,1}-\mu_{j,1}|\leq\Pr_{\mu_{i,j|X_{S}\leftarrow\alpha}}\left[X_{i}\neq
X_{j}\right]$ $\displaystyle~{}\forall i,j\in e,~{}\forall e\in E$ Let
$\\{u_{S,\alpha}\\}$ be the optimal vector solution to the above, and let
$r\leq n^{O(R)}$ denote the dimension of these vectors;

2 Sample a uniformly random subset $S\subseteq V$ of size $t$ and an
assignment $X_{S}\leftarrow\alpha\sim\mu_{S}$;

3 Let $\\{u_{i}\\}_{i\in V}$ be the denote the set of vectors corresponding to
the degree-$2$ SoS psuedodistribution conditioned on $X_{S}\leftarrow\alpha$ ;

4 Let $\nu_{e}=\max_{i,j\in
e}\Pr_{\mu_{ij}|X_{S}\leftarrow\alpha}\left[X_{i}\neq X_{j}\right]$ be the
contribution from $e\in E$, and let $\nu^{*}\sum_{e\in
E}w(e)=\sum_{e}w(e)\nu_{e}$ denote the SDP objective value w.r.t. distribution
conditioned on $X_{S}\leftarrow\alpha$;

5 Delete all the hyperedges with $\nu_{e}\geq 1/10$ and consider them as cut
New Vector Solution.

6 Construct a new vector solution $\\{v^{\prime}_{i}\\}_{i\in V}$ as follows.
Let $u_{i}=\mu_{i}u_{\emptyset}+z_{i}$ where $u_{\emptyset}$ is the “one
vector” and $\langle u_{\emptyset},z_{i}\rangle=0$. For every $i\in V$, let
$v_{i}\overset{\rm def}{=}(1-2\mu_{i})u_{\emptyset}-2z_{i}$ ;

7 Let $\hat{z}$ be a unit vector orthogonal to
$u_{\emptyset},\\{z_{i}\\}_{i\in V}$, and let $\theta\leftarrow\delta^{12}$.
For every $i\in V$, define  $v^{\prime}_{i}\overset{\rm
def}{=}\frac{(1-2\mu_{i})u_{\emptyset}-2z_{i}-\theta\hat{z}}{\sqrt{1+\theta^{2}}}$
Shifted Hyperplane Rounding

8 Write $v^{\prime}_{i}=(1-2\mu^{\prime}_{i})u_{\emptyset}-2z^{\prime}_{i}$
where $\langle u_{\emptyset},z^{\prime}_{i}\rangle=0$;

9 Sample Gaussian $g\sim N(0,1)^{r}$ and for every $i\in V$, define
$\zeta_{i}=\langle g,\overline{z}^{\prime}_{i}\rangle$;

10 For every $i\in T$, assign
$y_{i}=\mathbbm{1}\left(\zeta\leq\Phi^{-1}(\mu^{\prime}_{i})\right)$;

Output subset $S={\rm supp}(y)$.

Algorithm 2 Approximation algorithm for Hypergraph small-set expansion

###  9.1 Analysis of Algorithm 2

Most of the claims and observations from the analysis of Algorithm 1 apply as
is to this setting as well. We highlight the key conclusions that hold as is
from proof of Theorem 1.1.

To begin with, we bound the shift in the total weight due to the shifted
biases. Let $\widehat{W}:V\to[0,1]$ denote the normalized weights defined as
$\hat{W}(i)=W(i)/d\sum_{e\in E}w(e)$. Then, we can again use Claim 4.3 to
bound the shift in the total bias as

$\left|`{\mathsf{E}}_{i\sim\widehat{W}}\mu_{i}-{\mathsf{E}}_{i\sim\widehat{W}}\mu^{\prime}_{i}\right|\leq\delta^{C^{*}_{0}}$

which implies that

$0.99\delta d\sum_{e\in E}w(e)\leq\sum_{e\in E}W(i)\mu^{\prime}_{i}\leq
1.01\delta d\sum_{e\in E}w(e)$

whenever $\delta$ is smaller than an absolute constant.

Now we analyze the conditioning step. As before, using Lemma 6.1, with
probability at least $0.9$ we have

$0.9\delta d\sum_{e\in E}w(e)\leq\sum_{i\in S}W(i)\leq 1.1\delta d\sum_{e\in
E}w(e)$

Again, for a random conditioning, using Markov’s inequality, we have that with
probability at least $0.9$,

$\sum_{e\in E}w(e)\max_{i,j\in e}\|v_{i}-v_{j}\|^{2}\leq 10\cdot{\sf Sdp}$

and consequently, using Claim 4.4,

$\sum_{e\in E}w(e)\max_{i,j\in e}\|v^{\prime}_{i}-v^{\prime}_{j}\|^{2}\leq
10\cdot{\sf Sdp}.$

In particular, the above conclusions hold simultaneously with probability at
least $0.8$.

#### Bounding the Expansion

The key technical tool, Lemma 7.1, carries over as is. For any hyperedge $e\in
E$, let $\hat{\alpha}_{e}\overset{\rm def}{=}\min_{i\in e}\mu_{i}$. Then,
analogous to Observation 7.4, using the $\ell_{1}$-constraints we have
$\hat{\alpha}_{e}\leq\alpha_{e}+\nu_{e}$ and therefore, repeating the steps
(42)-(42) from the previous analysis we can bound the probability of an edge
getting cut in the rounding step as

$\Pr_{{\sf Alg}}\Big{[}e\mbox{ is
cut}\Big{]}\lesssim\left(C^{*}_{0}\log(1/\delta)\right)\sqrt{\hat{\alpha}_{e}\nu_{e}\log(d)}+\tilde{O}(d)\nu_{e}(C^{*}_{0}\log(1/\delta)).$

We can then bound the expansion of the set $S$ as

$\displaystyle\frac{\sum_{e\in
E}\sqrt{\hat{\alpha}_{e}\nu_{e}\log(1/\delta)\log(d)}}{\sum_{v\in
S}W(v)}+\tilde{O}(d)(\log(1/\delta))^{2}\frac{\sum_{e\in
E}w(e)\nu_{e}}{\sum_{v\in S}W(v)}$ $\displaystyle\lesssim\frac{\sum_{e\in
E}\sqrt{\hat{\alpha}_{e}\nu_{e}\log(1/\delta)\log(d)}}{\sum_{v\in
S}W(v)}+\tilde{O}(d)\phi^{*}(\log(1/\delta))^{2}$

Define $\eta^{H}_{\rm max}$ as follows. For every hyperedge $e\in E$, let
$e^{\circ}\subseteq e$ be a choice of a non-empty subset of vertices. Then we
have

$\eta^{H}_{\rm max}=\min_{\\{e^{\circ}\\}}\max_{u\in V}\sum_{e:u\in
e^{\circ}}\frac{\log|e^{\circ}|}{|e^{\circ}|}$

Then towards bounding the first term, we can use the following observation
implicit in the proof of Theorem 6.3 [LM16]

###### Lemma 9.1

We can bound

$\frac{\sum_{e\in E}\sqrt{\hat{\alpha}_{e}\nu_{e}\log(d)}}{\sum_{v\in
V}W(v)}\leq\sqrt{\eta^{H}_{\rm max}\phi^{*}\log(d)}$

In particular, if $H$ is a $d$-uniform hypergraph with maximum degree $r$,
then $\eta^{H}_{\rm max}=(r\log_{2}(d))/d$.

Plugging in the bound from above lemma in place of the first term concludes
the proof.

### Acknowledgments

AL was supported in part by SERB Award ECR/2017/003296, a Pratiksha Trust
Young Investigator Award, and an IUSSTF virtual center on “Polynomials as an
Algorithmic Paradigm”.

## References

  * [ABG16] Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou.  Better balance by being biased: A 0.8776-approximation for max bisection.  ACM Transactions on Algorithms (TALG), 13(1):1–27, 2016.
  * [ABS15] Sanjeev Arora, Boaz Barak, and David Steurer.  Subexponential algorithms for unique games and related problems.  Journal of the ACM (JACM), 62(5):1–25, 2015.
  * [ALN08] Sanjeev Arora, James Lee, and Assaf Naor.  Euclidean distortion and the sparsest cut.  Journal of the American Mathematical Society, 21(1):1–21, 2008\.
  * [Alo86] Noga Alon.  Eigenvalues and expanders.  Combinatorica, 6(2):83–96, 1986.
  * [AP09] Reid Andersen and Yuval Peres.  Finding sparse cuts locally using evolving sets.  In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 235–244, 2009.
  * [ARV09] Sanjeev Arora, Satish Rao, and Umesh Vazirani.  Expander flows, geometric embeddings and graph partitioning.  Journal of the ACM (JACM), 56(2):1–37, 2009.
  * [AS65] Milton Abramowitz and Irene A Stegun.  Handbook of mathematical functions with formulas, graphs, and mathematical table.  In US Department of Commerce. National Bureau of Standards Applied Mathematics series 55, 1965.
  * [AS19] Per Austrin and Aleksa Stankovic.  Global cardinality constraints make approximating some max-2-csps harder.  arXiv preprint arXiv:1907.04165, 2019.
  * [AZBG+20] Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, and Mohit Singh.  Sticky brownian rounding and its applications to constraint satisfaction problems.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 854–873. SIAM, 2020.
  * [BFK+11] Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, and Roy Schwartz.  Min-max graph partitioning and small set expansion.  In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 17–26. IEEE, 2011.
  * [CLTZ18] T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang.  Spectral properties of hypergraph laplacian and approximation algorithms.  J. ACM, 65(3):15:1–15:48, 2018.
  * [CMM06] Moses Charikar, Konstantin Makarychev, and Yury Makarychev.  Near-optimal algorithms for unique games.  In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 205–214. ACM, 2006.
  * [Cov99] Thomas M Cover.  Elements of information theory.  John Wiley & Sons, 1999.
  * [FdV16] Fajwel Fogel, Alexandre d’Aspremont, and Milan Vojnovic.  Spectral ranking using seriation.  The Journal of Machine Learning Research, 17(1):3013–3057, 2016\.
  * [FG95] Uriel Feige and Michel Goemans.  Approximating the value of two power proof systems, with applications to max 2sat and max dicut.  In Proceedings Third Israel Symposium on the Theory of Computing and Systems, pages 182–189. IEEE, 1995.
  * [FHL08] Uriel Feige, MohammadTaghi Hajiaghayi, and James R Lee.  Improved approximation algorithms for minimum weight vertex separators.  SIAM Journal on Computing, 38(2):629–657, 2008.
  * [GL14] Venkatesan Guruswami and Euiwoong Lee.  Complexity of approximating CSP with balance / hard constraints.  In Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014, pages 439–448. ACM, 2014.
  * [GL20] Suprovat Ghoshal and Anand Louis.  Approximation algorithms and hardness for strong unique games.  CoRR, abs/2005.08918, 2020.
  * [GL21] Suprovat Ghoshal and Anand Louis.  Approximation algorithms and hardness for strong unique games.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 414–433. SIAM, 2021.
  * [GL23] Suprovat Ghoshal and Euiwoong Lee.  On lifting integrality gaps to sseh hardness for globally constrained csps.  arXiv preprint arXiv:2308.09667, 2023.
  * [GS11] Venkatesan Guruswami and Ali Kemal Sinop.  Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives.  In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 482–491. IEEE Computer Society, 2011.
  * [GW94] Michel X. Goemans and David P. Williamson.  .879-approximation algorithms for MAX CUT and MAX 2sat.  In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 422–431. ACM, 1994.
  * [Kho02] Subhash Khot.  On the power of unique 2-prover 1-round games.  In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 767–775, 2002.
  * [KLT22] Tsz Chiu Kwok, Lap Chi Lau, and Kam Chuen Tung.  Cheeger inequalities for vertex expansion and reweighted eigenvalues.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 366–377. IEEE, 2022.
  * [Kol10] Alexandra Kolla.  Spectral algorithms for unique games.  In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pages 122–130. IEEE Computer Society, 2010.
  * [KR08] Subhash Khot and Oded Regev.  Vertex cover might be hard to approximate to within 2- $\varepsilon$.  Journal of Computer and System Sciences, 74(3):335–349, 2008.
  * [KV05] Subhash Khot and Nisheeth K. Vishnoi.  The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l${}_{\mbox{1}}$.  In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 53–62, 2005.
  * [KVV04] Ravi Kannan, Santosh Vempala, and Adrian Vetta.  On clusterings: Good, bad and spectral.  Journal of the ACM (JACM), 51(3):497–515, 2004.
  * [Las01] Jean B Lasserre.  New positive semidefinite relaxations for nonconvex quadratic programs.  In Advances in Convex Analysis and Global Optimization, pages 319–331. Springer, 2001.
  * [Lau09] Monique Laurent.  Sums of squares, moment matrices and optimization over polynomials.  In Emerging applications of algebraic geometry, pages 157–270. Springer, 2009.
  * [LG22] Euiwoong Lee and Suprovat Ghoshal.  A characterization of approximability for biased csps.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 989–997, 2022.
  * [LGT14] James R Lee, Shayan Oveis Gharan, and Luca Trevisan.  Multiway spectral partitioning and higher-order cheeger inequalities.  Journal of the ACM (JACM), 61(6):1–30, 2014.
  * [LK99] László Lovász and Ravi Kannan.  Faster mixing via average conductance.  In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 282–287, 1999.
  * [LM16] Anand Louis and Yury Makarychev.  Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion.  Theory of Computing, 12(1):1–25, 2016.
  * [LR99] Tom Leighton and Satish Rao.  Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.  Journal of the ACM (JACM), 46(6):787–832, 1999.
  * [LRTV12] Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala.  Many sparse cuts via higher eigenvalues.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1131–1140, 2012.
  * [LRV13] Anand Louis, Prasad Raghavendra, and Santosh Vempala.  The complexity of approximating vertex expansion.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 360–369. IEEE, 2013.
  * [LTW23] Lap Chi Lau, Kam Chuen Tung, and Robert Wang.  Cheeger inequalities for directed graphs and hypergraphs using reweighted eigenvalues.  In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1834–1847. ACM, 2023.
  * [O’D14] Ryan O’Donnell.  Analysis of boolean functions.  Cambridge University Press, 2014.
  * [PY91] Christos H Papadimitriou and Mihalis Yannakakis.  Optimization, approximation, and complexity classes.  Journal of computer and system sciences, 43(3):425–440, 1991.
  * [RS09] Prasad Raghavendra and David Steurer.  How to round any CSP.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 586–594, 2009.
  * [RS10] Prasad Raghavendra and David Steurer.  Graph expansion and the unique games conjecture.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 755–764. ACM, 2010.
  * [RS13] Prasad Raghavendra and Tselil Schramm.  Gap amplification for small-set expansion via random walks.  arXiv preprint arXiv:1310.1493, 2013.
  * [RST10] Prasad Raghavendra, David Steurer, and Prasad Tetali.  Approximations for the isoperimetric and spectral profile of graphs and related parameters.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 631–640. ACM, 2010.
  * [RST12] Prasad Raghavendra, David Steurer, and Madhur Tulsiani.  Reductions between expansion problems.  In 2012 IEEE 27th Conference on Computational Complexity, pages 64–73. IEEE, 2012.
  * [RT11] Prasad Raghavendra and Ning Tan.  Approximating csps with global cardinality constraints using sdp hierarchies.  arXiv preprint arXiv:1110.1064, 2011.
  * [RT12] Prasad Raghavendra and Ning Tan.  Approximating csps with global cardinality constraints using sdp hierarchies.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 373–387. SIAM, 2012.
  * [Sho87] Naum Z Shor.  Quadratic optimization problems.  Soviet Journal of Computer and Systems Sciences, 25:1–11, 1987\.
  * [SW19] Thatchaphol Saranurak and Di Wang.  Expander decomposition and pruning: Faster, stronger, and simpler.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2616–2635. SIAM, 2019.

##  Appendix A Facts from Information Theory

As in [RT12], the proof of Lemma 6.1 uses elementary information theory. For
completeness, we introduce the (specific instantiations) of quantities and
related properties used in the proof. We again point out that all the
logarithms used in this section will be base $2$. Given a $0/1$ random
variable $X$ with bias $\mu$, the entropy of $X$, denoted by $H(X)$, is
defined as $H(X)=\mu\log(1/\mu)+(1-\mu)\log(1/(1-\mu))$. For a pair of random
variables $X,Y$, the mutual information between $X$ and $Y$ is denoted by
$I(X;Y)$ and is defined as $I(X;Y)=H(X)-H(X|Y)$ where $H(X|Y)$ is the
conditional entropy of $X$ given $Y$. We now list the facts used by the proof
of Lemma 6.1.

###### Fact A.1

For any $X\sim{\sf Bernoulli}(\mu)$ such that $\mu\leq 1/2$ we have

$H(X)\leq 2\mu\log\frac{1}{\mu}.$

  * Proof.

Using $\log(1+\mu)\leq\mu$ we get that

$\displaystyle H(X)=\mu\log\frac{1}{\mu}+(1-\mu)\log\frac{1}{1-\mu}$
$\displaystyle\leq$
$\displaystyle\mu\log\frac{1}{\mu}+(1-\mu)\log\left(1+\frac{\mu}{1-\mu}\right)$
$\displaystyle\leq$ $\displaystyle\mu\log\frac{1}{\mu}+\mu\leq
2\mu\log\frac{1}{\mu}.$

$\square$

###### Fact A.2

For any pair of boolean random variables $X,Y$ we have $I(X;Y)\leq 1$.

  * Proof.

Using the fact that the entropy of boolean random variable lies between
$[0,1]$ (for e.g., see Example 2.1.1 [Cov99]), we have $I(X;Y)=H(X)-H(X|Y)\leq
H(X)\leq 1$. $\square$

###### Fact A.3

For any pair of Gaussian random variables $(g_{i},g_{j})\sim N(0,\Sigma)$ we
have $I(g_{i};g_{j})=-\frac{1}{2}\log|\Sigma|$.

######  Lemma A.4 (Data Processing Inequality)

Let $(X,Y)$ and $(X^{\prime},Y")$ be pairs of random variables such that $X$
is completely determined by $X^{\prime}$ and $Y$ is completely determined by
$Y^{\prime}$. Then $I(X;Y)\leq I(X^{\prime};Y^{\prime})$

##  Appendix B Integrality Gap

Here we show that the integralilty gap of the lifted SDP is still $\Omega(d)$
for up to near-linear levels of SoS, as stated formally in the following
proposition.

[] For every $d\geq 2$, there exists a $\delta=\delta(d)$ such that for
$R=\Omega(n/\log(n))$, the $R$-level SoS lifting of the basic SDP for the
$\delta$-HSSE problem has integrality gap $\Omega(d)$.

  * Proof.

The gap instance is simple: it is just a $d$-uniform random hypegraph with a
linear number of hyperedges. Formally, our construction is as follows.

Construction. Given $d,n\geq 2$, set $\delta=1/d$, $k=\delta n$ and
$r=Cn\log(1/\delta)$ for some large constant $C$. Let $H=(V,E)$ be a random
hypergraph on $n$-vertices where $E=\\{e_{1},\ldots,e_{r}\\}$ such that each
$e_{i}$ is a uniformly random $d$-sized subset of $V$.

#### Soundness.

We first note that for any constant $c>0$, we have $(\delta
n-c)/(n-c)\leq\delta$. Fix a subset $S\subseteq V$ of size $k$. Then for any
fixed $i\in[r]$,

$\Pr_{H}\left[e_{i}\in\partial_{H}(S)\right]\geq
1-\delta^{d}-(1-\delta)^{d}\geq 1-e^{-1}-\delta^{d}\geq 1/4$

where the first inequality is using $d=1/\delta$. Therefore,
${\mathsf{E}}|\partial_{H}(S)|\geq r/4$. Therefore, using Chernoff bound over
the randomness of the choice of the hyperedges, we have that

$\Pr_{H}\left[|\partial_{H}(S)|\geq\frac{r}{8}\right]\geq 1-e^{-r/64}$

and hence taking a union bound over all $\binom{n}{\delta n}\leq
e^{n\log(1/\delta)}$ subsets of size $k$ we have that

$\Pr_{H}\left[~{}\forall\
S\in\binom{[n]}{k}:|\partial_{H}(S)|\geq\frac{r}{8}\right]\geq
1-\exp\left(n\log(1/\delta)-r/64\right)\geq 1-e^{-Cr/2}$

for large constant $C$.

#### Completeness.

Consider the distribution over subsets described by the following process

  * –

Choose a random $k=\delta n=n/d$ sized subset $S$ and set
$X_{i}=\mathbbm{1}(i\in S)$ for every $i\in V$.

The above is a mixture over integer solutions, and therefore admits a valid
degree $R$-pseudo-distribution. Fix a $R$-sized subset $S$, and let $E_{S}$
denote the set of hyperedges incident on $S$ i.e,

$E_{S}:=\left\\{e\in E|e\cap S\neq\emptyset\right\\}$

Now it is easy to see that

$\Pr_{e=(i_{1},\ldots,i_{d})\sim\binom{[n]}{d}}\left[e\in
E_{S}\right]\leq\sum_{j\in[d]}\Pr\left[i_{j}\in S\right]\leq\frac{dR}{n}$

and hence the expected number of hyperedges incident on $S$ is at most
$dRr/n\lesssim dR\log(1/\delta)$ (since $r=O(n\log(1/\delta))$ by our choice
of parameters). Hence using Chernoff bound we have that

$\Pr\left[|E_{S}|\geq dR\log(1/\delta)\sqrt{\log
n}\right]\leq\exp\left(-\frac{\log(n)\log(1/\delta)dR}{4}\right).$

Taking a union bound over all $\binom{n}{R}\leq e^{R\log n}$ choices of
$R$-sized subsets we get that

$\displaystyle\Pr\left[~{}\forall\ S\in\binom{n}{R}:|E_{S}|\leq
dR\log(1/\delta)\sqrt{\log(n)}\right]$ $\displaystyle\leq$
$\displaystyle\exp\left(R\log n-\frac{\log(n)\log(1/\delta)dR}{4}\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\log(n)\log(1/\delta)dR}{8}\right)$

Now choose an $R^{\prime}$-sized subset $T$ with $R^{\prime}\leq R-1$ and and
a conditioning $X_{T}\leftarrow\alpha$. Suppose the conditioning fixes
$r^{\prime}$ out of $R^{\prime}$ variables to $1$. Then then the degree
$R-R^{\prime}$ distribution on the variables $V\setminus T$ conditioned on
$X_{T}\leftarrow\alpha$ corresponds to the following.

  * –

Choose a uniformly random $(n/d-r^{\prime})$-sized subset $S$ from $V\setminus
T$ and set $X_{i}=\mathbbm{1}(i\in S)$.

In particular, for any $i\in V\setminus T$ we have that

$\Pr_{X_{i}\sim\mu_{i}|X_{T}\leftarrow\alpha}[X_{i}=1]=\frac{\frac{n}{d}-r^{\prime}}{n-R^{\prime}}\leq\frac{2}{d}$

as long as $R^{\prime}\leq n/2$. From the above, we can conclude that for any
pair of variables $i,j\in V\setminus T$

$\Pr_{\mu_{ij}|X_{T}\leftarrow\alpha}\left[X_{i}\neq
X_{j}\right]\leq\Pr_{\mu_{i}|X_{T}\leftarrow\alpha}\left[X_{i}=1\right]+\Pr_{\mu_{j}|X_{T}\leftarrow\alpha}\left[X_{j}=1\right]=\frac{4}{d}$
(46)

Therefore, in summary, for any $R$-sized subset $T$, and a conditioning of the
variables in $T$ we have the following.

  1. 1.

The number of hyperedges incident on $T$ is at most
$dR\log(1/\delta)\sqrt{\log(n)}$ for which the contribution to the objective
value is at most $1$.

  2. 2.

For any hyperedge not intersecting with $T$, from (46) we know that the
contribution to the objective is at most $4/d$.

Hence, the total value of the objective for any conditioning on any $R$-sized
subset is at most

$dR\log(1/\delta)\sqrt{\log(n)}+\frac{4r}{d}\leq\frac{8r}{d}$

which completes the soundness analysis. $\square$

##  Appendix C Reduction from SSVE to Hyper-SSE

We introduce some additional notation introduced in this section. For a graph
$G=(V,E)$, and a subset of vertices $S\subset V$, we define the symmetric
vertex boundary as $\partial^{\rm
sym}_{G}(S)=\partial^{V}_{G}(S)\cup\partial^{V}_{G}(S^{c})$. Furthermore, the
internal boundary of the set $S$ is defined as $\partial^{V}_{\rm
int}(S)=\partial^{V}_{G}(S^{c})$. The symmetric vertex expansion of $S$,
denoted by $\Phi^{V}_{G}$ is defined as

$\Phi^{V}_{G}(S)=\frac{w(\partial^{\rm sym}_{G}(S))}{w(S)}$

###### Lemma C.1

Given a vertex weighted graph $G=(V,E,w)$ with vertex weights
$w:V\to\mathbbm{R}_{\geq 0}$, there exists an efficient procedure to construct
a vertex weighted graph $G^{\prime}=(V^{\prime},E^{\prime},w^{\prime})$ for
which the following properties holds:

  * •

Completeness: If there exists a subset $S\subset V$ such that $w(S)=\delta$
and $\phi^{V}_{G}(S)\leq\varepsilon$, then there exist a set
$S^{\prime}\subset V^{\prime}$ such that $w^{\prime}(S^{\prime})=\delta$ and
$\Phi^{V^{\prime}}_{G^{\prime}}(S^{\prime})\leq 2\varepsilon$.

  * •

Soundness: If there exists a subset $S^{\prime}\subset V$ such that and
$w^{\prime}(S^{\prime})=\delta$ and $\Phi^{\rm
sym}_{G^{\prime}}(S)\leq\varepsilon$, then there exists a set $S\subset V$
such that $(1-\varepsilon)\delta\leq w(S)\leq\delta$ and
$\phi^{V}_{G}(S)\leq\varepsilon/(1-\varepsilon)$.

Furthermore, the maximum degree of the graph $G^{\prime}$ is exactly the
maximum degree of graph $G$.

  * Proof.

Given the graph $G=(V,E,w)$ we construct a new bipartite graph
$G^{\prime}=(V_{L},V_{R},w^{\prime})$ as follows. Here we assign $V_{L}=V$ and
$V_{R}=E$ i.e., the left vertex set is the set of vertices in $G$ and the
right vertex set is the edge-set in $E$. Furthermore, for every vertex set
$u\in V$ and every edge $e=(u,v)\in E$ we add an edge $(u,e)\in E$. For every
$u\in V_{L}$ we assign $w^{\prime}(u)=w(u)$ and for every vertex $e\in V_{R}$
we assign $w^{\prime}(0)$. This completes the description of the graph
$G^{\prime}$. For brevity, we shall denote $V^{\prime}=V_{L}\cup V_{R}$. Now
we analyze the completeness and soundness of the reduction.

Completeness. Suppose there exists a subset $S\subset V$ such that
$\phi^{V}_{G}(S)\leq\varepsilon$ and $w(S)=\delta$. Construct the set
$S^{\prime}$ by including all the vertices in $S$ and all the edges incident
on $S$ i.e.,

$S^{\prime}=S\cup\Big{\\{}(u,v)\in V_{R}\Big{|}u\in S\vee v\in S\\}$

Since the edge vertices $e\in V_{R}$ have weight $0$, we have
$w^{\prime}(S)=w(S)=\delta$. Now we bound the symmetric vertex expansion of
$S^{\prime}$. Fix a vertex $v\in\partial^{\rm sym}_{G^{\prime}}(S)$. Since if
$v\in V_{R}$, we have $w^{\prime}(v)=0$ so it does not contribute anything to
the weight of the symmetric boundary. Therefore we may assume that $v\in
V_{L}=V$. Then we claim that $v\notin S^{\prime}$. Otherwise if $v\in
S^{\prime}$, we must have $v\in S$ (since $S^{\prime}\cap V=S$). Furthermore,
if $v\in S$, then for every $e=(v,v^{\prime})\in E$ we have $e\in S^{\prime}$
(from the construction of $G^{\prime}$) and hence $N_{G^{\prime}}(v)\subset
S^{\prime}$ which contradicts $v\in\partial^{\rm sym}_{V^{\prime}}(S)$.
Therefore we must have $v^{\prime}\notin S$. But then there exists edge-vertex
$e=(u,v)\in S^{\prime}$ for some $u\in S^{\prime}$. This implies that
$v\in\partial^{V}_{G}(S)$. Hence, we have

$\Phi^{V^{\prime}}_{G^{\prime}}(S^{\prime})=\frac{w^{\prime}\left(\partial^{\rm
sym}_{G^{\prime}}(S^{\prime})\right)}{w^{\prime}(S^{\prime})}=\frac{w\left(\partial^{\rm
sym}_{G^{\prime}}(S^{\prime}\cap
V)\right)}{w(S)}\leq\frac{w\left(\partial^{V}_{G}(S)\right)}{w(S)}=\phi^{V}_{G}(S)\leq\varepsilon.$

Soundness. Fix a subset $S^{\prime}\subset V^{\prime}$ such that
$w^{\prime}(S^{\prime})=\delta$ and
$\Phi^{V^{\prime}}_{G^{\prime}}(S^{\prime})\leq\varepsilon$. Let
$S^{\prime\prime}\overset{\rm def}{=}S^{\prime}\setminus\partial^{\rm
int}_{G^{\prime}}(S^{\prime})$, and define $S=S^{\prime\prime}\cap V$. We
claim that $\partial^{V}(S)\subset\partial^{\rm
sym}_{G^{\prime}}(S^{\prime})$. To see this, fix a vertex
$v\in\partial^{V}_{G}(S)$. Then there exists $u\in S\cap N_{G}(v)$. Now since
$u\in S$ we also have $u\in S^{c}$. Now we consider the following cases. Now
for contradiction, suppose $v\notin\partial^{\rm
sym}_{G^{\prime}}(S^{\prime})$, then this combined with the fact that $v\notin
S$ implies that $v\notin S^{\prime}$. Now we consider two cases:

Case (i). Suppose $(u,v)\notin S^{\prime}$. Then $u\in\partial^{\rm
int}_{G^{\prime}}(S^{\prime})$ which contradicts the fact that $u\in S$.

Case (ii). Suppose $(u,v)\in S^{\prime}$. Then $v\in\partial^{\rm
sym}_{G^{\prime}}(S^{\prime})$, contradicting that $v\notin\partial^{\rm
sym}_{G^{\prime}}(S^{\prime})$.

Therefore, the above establishes that
$\partial^{V}_{G}(S)\subseteq\partial^{{\rm sym}}_{G^{\prime}}\cap V$.
Furthermore, note that we have

$w(S)=w^{\prime}(S^{\prime\prime})=w^{\prime}(S^{\prime})\setminus
w\left(\partial^{\rm int}_{G^{\prime}}(S^{\prime})\right)\geq
w^{\prime}(S^{\prime})-\varepsilon
w(S^{\prime})\geq(1-\varepsilon)w^{\prime}(S^{\prime})=(1-\varepsilon)w(S^{\prime})$

and since $S\subset S^{\prime}\cap V$ we have $w(S)\cap w(S^{\prime}\cap V)$.
Therefore, combining the above observations we get that

$\phi^{V}_{G}(S)=\frac{w\left(\partial^{V}_{G}(S)\right)}{w(S)}\leq\frac{w\left(\partial^{\rm
sym}_{G^{\prime}}(S^{\prime})\right)}{(1-\varepsilon)w^{\prime}(S^{\prime})}=\frac{\Phi^{\rm
sym}_{G}(S)}{1-\varepsilon}.$

$\square$

###### Lemma C.2

Given a vertex weighted graph $G=(V,E,w)$ of maximum degree $d$, there exists
an efficient procedure to construct a weighted hypergraph
$H=(V,E^{\prime},w^{\prime},W)$ on the same vertex set with edge weights given
by $w^{\prime}:E^{\prime}\to\mathbbm{R}_{\geq 0}$ and vertex weights given by
$W^{\prime}:V\to\mathbbm{R}_{\geq 0}$ such that the following holds. For every
subset $S\subset V$ we have $w(S)=W(S)$ and
$w^{\prime}\left(\partial^{E^{\prime}}_{H}(S)\right)=w\left(\partial^{\rm
sym}_{G}(S)\right)$. Consequently, we have $\phi^{E}_{H}(S)=\Phi^{V}_{G}(S)$
for every subset $S\subset V$.

  * Proof.

Given a graph $G=(V,E,w)$, we construct the hypergraph $H=(V,E,W,w^{\prime})$
on the vertex set $V$ as follows. For every vertex $v\in V$ we introduce a
hyperedge ${\mathcal{E}}(v)=\\{v\\}\cup N_{G}(v)$. Furthermore, for every
hyperedge ${\mathcal{E}}(v)$ we assign it weight
$w^{\prime}({\mathcal{E}}(v))=w(v)$, and assign the vertex weight $W(v)=w(v)$.
This concludes the construction of the hypergraph. From the construction, it
follows that the max-arity of the hypergraph $H$ is the same as the maximum
degree of $G$. Furthermore, for every $v\in V$ we have $w(v)=W(v)$ and hence
$w(S)=W(S)$ for every subset $S\subset V$. Finally, we observe the following.
Fix a vertex $v\in V$. Then,

$\displaystyle v\in\partial^{\rm sym}_{G}(S)$
$\displaystyle\Leftrightarrow\exists\ u\in N_{G}(u)\mbox{ s.t. }\big{\\{}u\in
S,v\in S^{c}\\}\vee\\{u\in S^{c},v\in S\\}$
$\displaystyle\Leftrightarrow{\mathcal{E}}(v)\in\partial^{E^{\prime}}_{H}(S)$

The above one-to-one correspondence directly implies for any subset $S\subset
V$ we have

$w^{\prime}\left(\partial^{E^{\prime}}_{H}(S)\right)=\sum_{v:{\mathcal{E}}(v)\in\partial^{E^{\prime}}_{H}(S)}w^{\prime}(e)=\sum_{v:v\in\partial^{V}_{G}(S)}w(e)=w\left(\partial^{V}_{G}(S)\right)$

The above claims taken together immediately imply that
$\phi^{E^{\prime}}_{H}(S)=\Phi^{V}_{G}(S)$ for every subset $S\subset V$.
$\square$