[name=Theorem,numberlike=theorem]rethm [name=Lemma,numberwithin=section]lem

# On Lifting Integrality Gaps to SSEH Hardness
for Globally Constrained CSPs

Suprovat Ghoshal
Northwestern University & TTIC
<EMAIL_ADDRESS>Euiwoong Lee
University of Michigan
<EMAIL_ADDRESS>
A $\mu$-constrained Boolean Max-CSP$(\psi)$ instance is a Boolean Max-CSP
instance on predicate $\psi:\\{0,1\\}^{r}\to\\{0,1\\}$ where the objective is
to find a labeling of relative weight exactly $\mu$ that maximizes the
fraction of satisfied constraints. In this work, we study the approximability
of constrained Boolean Max-CSPs via SDP hierarchies by relating the
integrality gap of Max-CSP$(\psi)$ to its $\mu$-dependent approximation curve.

Formally, assuming the Small-Set Expansion Hypothesis, we show that it is
$\mathsf{NP}$-hard to approximate $\mu$-constrained instances of Max-
CSP($\psi$) up to factor ${\sf Gap}_{\ell,\mu}(\psi)/\log(1/\mu)^{2}$
(ignoring factors depending on $r$) for any $\ell\geq\ell(\mu,r)$. Here, ${\sf
Gap}_{\ell,\mu}(\psi)$ is the optimal integrality gap of $\ell$-round Lasserre
relaxation for $\mu$-constrained Max-CSP($\psi$) instances.

Our results are derived by combining the framework of Raghavendra [STOC 2008]
along with more recent advances in rounding Lasserre relaxations and
reductions from the Small-Set Expansion (SSE) problem. A crucial component of
our reduction is a novel way of composing generic bias-dependent dictatorship
tests with SSE, which could be of independent interest.

###### Contents

  1. 1 Introduction
  2. 2 Overview and Techniques
  3. 3 Notation and Preliminaries
  4. 4 Small Average-Correlation via Pre-processing
  5. 5 The Reduction
  6. 6 Completeness
  7. 7 Soundness
  8. 8 Proof of Lemma 7.3
  9. 9 SSEH Decoding Lemmas
  10. 10 Proof of Lemma 7.7
  11. A Multivariate Gaussian CDF Bound
  12. B Miscellaneous Fourier Analysis Facts
  13. C Separating Example

##  1 Introduction

Maximum Constraint Satisfaction Problems (Max-CSPs) are some of the most
commonly studied optimization problems in theoretical computer science. An
instance $\Psi(H=(V,E),\\{\Pi\\}_{e})$ of a $r$-ary Boolean Max-CSP is
identified with a $r$-ary constraint (hyper)graph $H=(V,E)$, a constraint set
$\\{\Pi_{e}\\}_{e}$, where for every edge $e$, $\Pi_{e}\subseteq\\{0,1\\}^{r}$
defines the set of “accepting” assignments to the edge. The overall objective
of the Max-CSP problem is to find a Boolean labeling of the vertices that
maximizes the fraction of satisfied constraints. The generality of the
definition allows it to express a wide array of combinatorial optimization
problems such as Max-Cut, Max-SAT, Max-$3$-Lin, Label Cover, among many others
as special cases; each of these problems are of fundamental interest on their
own, and have their own dedicated line of works that explore its various
aspects (see [MM17] and references therein for a comprehensive overview of
such results).

An extensively studied question in the context of each of these problems, and
for Max-CSPs in general, is that of proving tight bounds for efficiently
achievable approximation guarantees. While in the beginning, individual
classes of CSPs seem to require their own problem-specific techniques for
algorithms and hardness, over a steady sequence of works, the shape of a more
unified framework for understanding CSPs began to emerge; upper bounds were
facilitated using advances in understanding the power of semidefinite
programming [GW94, KMS98, CMM06], whereas lower bounds were being facilitated
by dictatorship test-based gadget reductions [Hås01, KKMO07]). These
developments eventually culminated in the work of Raghavendra [Rag08], which
connected the two directions by showing that the limitations of SDP based
algorithms are fundamentally connected to the best efficiently achievable
approximation factors. Specifically, [Rag08] showed that assuming the Unique
Games Conjecture (UGC) [Kho02], for every Max-CSP there exists a canonical SDP
relaxation whose integrality gap matches the best possible hardness for the
problem under UGC. The soundness analysis of its reduction automatically
yielded the optimal rounding schemes for the SDP relaxation, thus further
strengthening the connection between SDPs and UGC-based hardness reductions.
Following [Rag08], there have been several subsequent works which establish
analogous connections for the settings of graph partitioning problems
[MNRS08], Ordering CSPs [GHM+11], Strict CSPs [KMTV11], and Tree CSPs [CM22].

Despite the ubiquity of [Rag08]’s framework, there are still several natural
classes of optimization problems for which an analogous unified theory of
optimal algorithms and hardness has remained elusive. A particularly well-
studied class of such problems are CSPs with global cardinality constraints.
Formally, given a predicate $\psi:\\{0,1\\}^{r}\to\\{0,1\\}$, a
$\mu$-constrained Max-CSP$(\psi)$ instance is a Boolean Max-CSP where the edge
constraints are identified by $\psi$, and the objective is to find an
assignment of relative weight exactly $\mu$ that satisfies the maximum
fraction of constraints. Such CSPs and its variants again express several
well-studied problems such as Densest-$k$-Subgraph, Max-Bisection, Max
$k$-Coverage, Small-Set Expansion, among many others.

While there is extensive literature that study algorithms and hardness for
these problems, these results often employ problem-specific techniques, and as
such, a general unified framework of these problems, as in [Rag08], is far
from being realized. In particular, in the quest to develop such a theory for
globally constrained CSPs, one is faced with following immediate challenges:

Question 1: What is a natural algorithmic framework that is amenable towards
deriving optimal approximation guarantees for globally constrained CSPs?

Question 2: Is there a way to lift lower bounds for the class of optimal
algorithms to (possibly conditional) $\mathsf{NP}$-hardness lower bounds?

Towards answering the above, it is useful to understand why the techniques of
[Rag08] don’t immediately apply to the setting of globally constrained CSPs.
The key observation here is that in the setting of Max-CSPs, one can usually
reduce the task of solving the CSP instance to that of solving a distribution
over constant sized ‘local’ instances. This viewpoint is especially useful in
the context of both algorithmic and hardness frameworks. In particular,
analyses of SDP based approximation algorithms often view the CSP as a
distribution over constraints, and derive the approximation guarantee by
reducing the task to that of analyzing the performance of the algorithm on
individual constraints. On other hand, for establishing hardness results, a
usual approach is to first construct a toy instance (aka a dictatorship test)
that models the conceptual difficulty of the problem, and then one can create
a large hard instance of the same by embedding copies of the smaller instance
along the edges of a hard CSP such as Unique Games. However, back in the
setting of globally constrained Max-CSPs, these local techniques often fail to
capture the additional complexity introduced due to the ‘global’
constraint(s), and yield bounds that are far from optimal.

Fortunately, it turns out that there are more recent advances in the theory of
approximation which can provide us with candidate guesses for the answers to
these questions. Firstly, there is promising evidence which suggests that
algorithmic frameworks based on higher-order SDP hierarchies (such as the Sum-
of-Squares (SoS) hierarchy) are better suited for addressing local and global
constraints simultaneously. In particular, the work of Raghavendra and Tan
[RT12] proposed a systematic SoS-based framework for solving constrained CSPs,
variations of which have been used to establish near-optimal approximation
guarantees for several problems such as Max/Min-Bisection, Balanced Separator
[RT12, ABG16], Max-$k$-VC, CC Max-Cut [AS19]. For the second question, a
candidate staging ground for proving hardness results for globally constrained
Boolean Max-CSPs is the Small Set Expansion Hypothesis (SSEH). Introduced in
the work of Raghavendra and Steurer [RS09], the Small-Set Expansion problem
has been useful in establishing tight bounds for several natural problems such
as Balanced Separator, Min-Bisection [RST12], Max-Biclique, Min-$k$-Cut
[Man18], Densest-$k$-SubHypergraph [GL22a].

In this work, we make progress towards bridging the gap between upper and
lower bounds for globally constrained CSPs. In particular, we extend the
techniques of [Rag08] and develop a systematic way of lifting SoS integrality
gaps to SSEH hardness. We detail the contributions of this work in the
remainder of this section.

###  1.1 Our Results

Let $\psi:\\{0,1\\}^{r}\to\\{0,1\\}$ be a $r$-ary Boolean predicate. Let
$G_{\rm gap}=(V_{\rm gap},E_{\rm gap},\tilde{w},w)$ be a weighted constraint
hypergraph (where the vertex and edge weights are given by $\tilde{w}$ and $w$
respectively) for the Max-CSP problem with predicate $\psi$. We will assume
that the edge weights (vertex weights) sum to one, and hence, they define a
distribution over the set of edges (vertices). We will use $i\sim G_{\rm gap}$
and $e\sim E_{\rm gap}$ to denote a draw of a vertex and an edge from the
corresponding distributions.

In this work, we deal with Lasserre SDP relaxations for the Max-CSP$(\psi)$
instance on $G_{\rm gap}$. Formally, the $\ell$-round Lasserre relaxation for
$G_{\rm gap}$ – denoted by ${\sf Lass}_{\mu,\ell}(G_{\rm gap})$ – is described
in the Figure 1. The convex relaxation described is the $\ell$-round Lasserre
lifting of the basic SDP. For every subset of variables $A$ of size at most
$\ell$ and any partial labeling $\alpha$ of the vertices in $A$, it introduces
a vector variable $v_{A,\alpha}$ which is meant to indicate whether the
vertices in $A$ are assigned the label $\alpha$. Furthermore, it also
introduces a local distribution $\theta_{A}$ over partial assignments to the
vertices in $A$, for every subset of $A$ of size at most $\ell$. Finally it
enforces inner product constraints which ensure that the $\ell^{th}$-order
moment matrix (defined using the local distributions) is well-defined and
positive semidefinite.

Maximize $\displaystyle{\mathsf{E}}_{e\sim E_{\rm
gap}}\Pr_{X_{e}\sim\theta_{e}}\left[\psi(X_{e})=1\right]$ Subject to
$\displaystyle{\mathsf{E}}_{i\sim G_{\rm
gap}}\Pr_{X_{i}\sim\theta_{i}}\left[X_{i}=1\right]=\mu$ $\displaystyle\langle
u_{A,\alpha},u_{B,\beta}\rangle=\Pr_{\theta_{A\cup
B}}\left[X_{A}=\alpha,X_{B}=\beta\right]$
$\displaystyle~{}\forall~{}A,B\subseteq[\ell]\textnormal{such that}$
$\displaystyle|A|,|B|\leq\ell/2,$
$\displaystyle\alpha\in\\{0,1\\}^{A},\beta\in\\{0,1\\}^{B}$ Figure 1: ${\sf
Lass}_{\mu,\ell}(G_{\rm gap})$

Our main result here is that integrality gaps for the above relaxation (with
$\ell\geq\ell(\mu,r)$) can be translated to almost matching Small-Set
Expansion hardness. In order to state our result, we need to formally define
the notion of a gap instance.

######  Definition 1.1 ($(\ell,\mu,c,s,\gamma)$-gap instance)

An $(\ell,\mu,c,s,\gamma)$-gap instance $(G_{\rm
gap},\theta:=\\{\theta_{S}\\}_{|S|\leq\ell})$ is characterized by a weighted
constraint hypergraph $G_{\rm gap}=(V_{\rm gap},E_{\rm gap},\tilde{w},w)$ and
a valid feasible solution $\theta=\\{\theta_{S}\\}_{S}$ to the $\ell$-round
Lasserre lifting ${\sf Lass}_{\mu,\ell}(G_{\rm gap})$ which satisfies the
following conditions:

  * •

Bias Constraint ${\mathsf{E}}_{i\sim G_{\rm
gap}}\Pr_{X_{i}\sim\theta}\left[X_{i}=1\right]=\mu$, where $i\sim G_{\rm gap}$
denotes the random draw of vertex according to the distribution induced by the
vertex weight function $\tilde{w}$.

  * •

Completeness. The set of local distributions satisfy

${\mathsf{E}}_{e\sim E_{\rm
gap}}\Pr_{X_{e}\sim\theta_{e}}\left[\psi(X_{e})=1\right]=c.$

  * •

Robust Soundness. The CSP $G_{\rm gap}$ satisfies ${\sf
Opt}_{\mu^{\prime}}(G_{\rm gap})\leq s$ for every
$\mu^{\prime}\in\mu(1\pm\sqrt{\gamma})$, where ${\sf
Opt}_{\mu^{\prime}}(G_{\rm gap})$ denotes the optimal
$\mu^{\prime}$-constrained value of the instance $G_{\rm gap}$.

In particular, a gap instance for a $\mu$-constrained Max-CSP$(\psi)$
corresponds to an instance with $\ell$-round Lasserre SDP value $c$ – which is
witnessed by a $\ell$-round Lasserre solution $\theta$ – and optimal
$\mu$-constrained value $s$. Equipped with the above definition, we are now
ready to state the main result of this work in the following theorem.

###### Theorem 1.2

The following holds assuming the SSEH. Fix a predicate
$\psi:\\{0,1\\}^{r}\to\\{0,1\\}$. Let $\mu\in(0,1/2)$. Suppose there exists a
$(\ell,\mu,c,s,\gamma)$-gap instance $(G_{\rm gap}=(V_{\rm gap},E_{\rm
gap},\tilde{w},w),\theta)$ for Max-CSP$(\psi)$ as in Definition 1.1 such that
$\ell\geq 1/\gamma^{8}+r$ and $\mu^{10r}\geq\gamma\geq|V_{\rm gap}|^{-1/C}$,
where $C>0$ is a large fixed constant. Then given a $\mu$-constrained Max-
CSP$(\psi)$ instance
$\mathcal{H}=(V_{\mathcal{H}},E_{\mathcal{H}},\tilde{w}_{\mathcal{H}},w_{\mathcal{H}})$,
it is $\mathsf{NP}$-hard to distinguish between the following two cases:

${\bf YES~{}Case}:~{}{\sf
Opt}_{\mu}(\mathcal{H})\gtrsim_{r}\frac{c}{\log(1/\mu)^{2}}\ \ \ \ \ \ \ \
\textnormal{and}\ \ \ \ \ \ \ \ {\bf NO~{}Case}:~{}{\sf
Opt}_{\mu}(\mathcal{H})\lesssim_{r}s.$

Here the $\lesssim_{r}$ and $\gtrsim_{r}$ notations hide multiplicative
factors that depend only on $r$.

The above theorem states that an $s/c$-integrality gap for $\ell(\mu,r)$-round
Lasserre relaxation can be translated to an
$\Omega_{r}((s/c)\cdot\log(1/\mu)^{2})$-factor SSEH hardness. At a high level,
this implies that hard-to-round instances for globally constrained CSPs
approximately translate to conditional $\mathsf{NP}$-hardness i.e., the
integrality gaps for higher-order convex relaxations imply fundamental
computational bottlenecks in approximating globally constrained CSPs. Whereas
previous works such as [RT12, ABG16, AZBG+20] illustrate the efficacy of
Lasserre based algorithms in approximating constrained Max-CSPs (albeit for
specific cases), we provide a connection in the other direction by lifting
Lasserre gaps to SSEH based hardness for every constrained Max-CSP. Theorem
1.2 illustrates the power of Lasserre hierarchy and SSEH in understanding the
approximability of problems with global constraints, where their basic
counterparts, namely SDPs and UGC, seem to provide relatively limited
insights.

######  Remark 1.3 (Lifting Degree-$2$ SoS gaps)

An obvious interesting question here is whether basic SDP integrality gaps can
be lifted to (conditional) $\mathsf{NP}$-hardness as well. We believe that an
optimal gaps-to-hardness lifting theorem (which does not lose any constants)
would require higher levels of SoS, since recent works on cardinality
constrained problems such as Max/Min-Bisection [RT12, ABG16], Balanced Max
$2$-SAT [ABG16], Max-$k$-VC [AS19] all crucially use properties of higher-
level SoS-relaxations. However, there are individual instances of globally
constrained problems such as Small-Set Expansion and Max-$k$-Coverage for
which SDP [RST10] and LP relaxations111For Max-$k$-Coverage, it is folklore
that independent rounding on LP relaxations yields a $(1-1/e)$-approximation
algorithm, which is tight [Fei98]. (for the latter) are known to be optimal,
and it is likely that the SDP gap instances of these problems themselves can
be losslessly lifted to $\mathsf{NP}$-hardness.

###  1.2 Related Work

Integrality Gaps and Hardness. The connection between SDP integrality gaps and
hardness was formally first established in the work of Austrin [Aus10], who
showed matching bounds for $2$-CSPs under certain assumption on the hardest-
to-round distributions. Following [Rag08], several works have extended this to
various settings such as Ordering CSPs [GHM+11], Strict CSPs [KMTV11], graph
partitioning problems [MNRS08], and Tree CSPs [CM22]. Khot and Saket [KS15]
showed that LP gaps for Max-CSPs can be lifted to Unique Games hardness while
losing a factor of $O(\log k)$, where $k$ is the label set size. There have
also been several works which lift previously known integrality gaps to
explicit Unique Games based lower bounds, for e.g. see [GSS15, Lee17, BHPZ21].

Lasserre Hierarchy. The Lasserre – aka Sum-of-Squares (SoS) – hierarchy has
been studied extensively in the context of approximation algorithms for CSPs,
and is widely believed to be a candidate meta-algorithm for refuting the
Unique Games Conjecture. Works such as [BRS11, GS11, AJT19] exhibit bounds
against the expansion profile of hard instances of Unique Games and related
CSPs by showing that instances with small threshold rank can be efficiently
solved using SoS. On the other hand, there have been several works [BBH+12,
OZ13, KOTZ14, BBK+21] which show that SoS can efficiently refute integrality
gap instances of several fundamental problems which fool the basic SDP
relaxation. We refer interested readers to [BS14, FKP+19] for an overview of
related results.

Globally Constrained CSPs. There have been several lines of works that study
specific globally constrained CSPs such as Densest-$k$-Subgraph problem [FS97,
BCC+10, Man17], Max-Bisection [RT12, ABG16], Max $k$-Vertex Coverage [RT12,
AS19]. [Gho22] studied the constrained variant of the Homogeneous Max-$3$-Lin
problem from the context of approximation resistance and established nearly-
tight bounds in several regimes. There have been several works which propose
general purpose algorithmic frameworks using Lasserre hierarchy in several
settings, for e.g. see [RT12, GS11, AZBG+20] and references therein.

Of particular relevance to the current work is that of Ghoshal and Lee [GL22a]
who studied Biased CSPs, where the objective is to find a labeling of relative
weight at most $\mu$ that satisfies the maximum number of constraints. They
established tight bounds for the bias-approximation curve of every Biased CSP
of constant arity by expressing it as a function of the bias-approximation
curves of the Densest-$k$-SubHypergraph problems. We point out that their
results do not apply to this setting due to the following reasons (i) in this
work we study CSPs with bounded weights (i.e., where the vertex weights at
most inverse polynomial in the instance size – say, bounded by $1/n^{1/100}$)
whereas [GL22a] studied CSPs where the vertex weights can be unbounded and
(ii) the feasible labelings are constrained to have relative weight exactly
$\mu$ as opposed to at most $\mu$. Due to these differences, there exist
predicates for which the approximation curve of the “equals” version studied
in this work is distinctly different from the curve for the version studied in
[GL22a]. For illustration, we provide such an example in Section C.

##  2 Overview and Techniques

Our approach towards establishing Theorem 1.2 is based on the following
principle: we want to use the “hard-to-round” integrality gap instance to
design a dictatorship test which, when combined with an appropriate outer
verifier, will yield a similar (conditional) hardness. This is a well-
understood process that can be distilled into two clear objectives:

  * (i)

Given a $(c,s)$-integrality gap instance, construct a “bias-dependent”
$(c,s)$-dictatorship test222A bias-dependent dictatorship test is a
dictatorship test where the completeness-soundness guarantees of the test only
apply when the input long code table $f$ has fixed relative weight, see Figure
3 for a more formal description of these properties. $\mathcal{T}_{\rm dict}$
for the same predicate.

  * (ii)

Compose $\mathcal{T}_{\rm dict}$ with SmallSetExpansion as the outer verifier.

There have been several works which use the above framework (for Max-CSPs) to
establish (often tight) connections between convex programming relaxations and
UGC based hardness. At a high level, Theorem 1.2 is based on [Rag08] (and in
part, [RT12]) – however extending their framework to the setting of globally
constrained CSPs is challenging and will require several new ideas.

###  2.1 [Rag08]’s approach

We first give a brief account of [Rag08]’s framework, which will be useful
towards highlighting the key bottlenecks that need to be addressed in the
setting of constrained CSPs. As mentioned above, [Rag08] also reduces the task
into establishing (i) and (ii). Towards establishing (i), [Rag08] considers
the following natural dictatorship test.333To keep the description simple and
consistent, here we describe [Rag08]’s construction for the setting of Boolean
CSPs – however, their setting and results are far more general, we refer
interested readers to [Rag08] for details.

Setting. Let $(G_{\rm gap}=(V_{\rm gap},E_{\rm gap},w),\theta)$ be a
$(c,s)$-gap instance444A $(c,s)$-gap instance refers to a gap instance for the
SDP relaxation corresponding to Max-CSP$(\psi)$. for Max-CSP$(\psi)$.
Input. An assignment555Typically, $r$ and $|V_{\rm gap}|$ are treated as
problem-specific constants, and then $R$ is chosen large enough as a function
of $r$ and $|V_{\rm gap}|$. $f:\\{0,1\\}^{R}\to\\{0,1\\}$.
Test. 1. Sample edge $e\sim E_{\rm gap}$ according to the distribution given
by the weight function $w$. 2. For each $j\in[R]$, independently sample
$(x_{1}(j),\ldots,x_{r}(j))\sim\theta_{e}$. 3. For each $i\in e$, sample
$x^{\prime}_{i}\underset{1-\eta}{\sim}x_{i}$ independently. 4. Accept if and
only if $\psi\Big{(}f(x^{\prime}_{1}),\ldots,f(x^{\prime}_{r})\Big{)}=1.$
Figure 2: Test $\mathcal{T}_{\rm UGC}$

Then they proceed to show that the above test has completeness $c$ and
soundness $s$. As is usual, arguing completeness is simple – one can show that
any dictator function $f=\chi_{i}$ passes the test with probability at least
$c-o(1)$. On the other hand, arguing that the soundness of the test is at most
$s:={\sf Opt}(G_{\rm gap})$ is the more challenging direction: this is
established by providing a rounding algorithm ${\sf Round}$ which shows that
non-influential functions can be used to round off solutions with value
matching the acceptance probability – this is stated formally in the following
theorem.

######  Theorem 2.1 ([Rag08])

There exists a randomized algorithm ${\sf Round}$ with the following property.
Given a non-influential long code assignment $f$, it can use $f$ to round off
a labeling $\sigma:={\sf Round}(f)$ such that

${\mathsf{E}}_{\sigma}\left[{\sf Val}_{\sigma}(G_{\rm
gap})\right]\approx\Pr\left[\mathcal{T}_{\rm UGC}\mbox{ Accepts }f\right],$

where ${\sf Val}_{\sigma}(G_{\rm gap})$ denotes the weight of edges in $G_{\rm
gap}$ satisfied by the labeling $\sigma$.

In particular, since ${\sf Val}_{\sigma}(G_{\rm gap})$ is always upper bounded
by ${\sf Opt}(G_{\rm gap})$, the above implies that

$\Pr\left[\mathcal{T}_{\rm UGC}\mbox{ accepts
}f\right]\approx{\mathsf{E}}_{\sigma}\left[{\sf Val}_{\sigma}(G_{\rm
gap})\right]\leq{\sf Opt}(G_{\rm gap})=s,$

thus establishing soundness, and consequently (i). Now given the dictatorship
test from (i), using Unique Games instances as the outer verifier, the
composition step (ii) follows almost immediately using standard techniques
[KKMO07].

[Rag08] for $\mu$-constrained CSPs?. In extending the above to the setting of
$\mu$-constrained CSPs, several immediate issues arise, some of which have
been addressed in previous works. To begin with, a first step is to understand
what kind of convex relaxations can be used to construct dictatorship tests
for $\mu$-constrained CSPs? Since the local distributions completely specify
the dictatorship test, the above is akin to asking what kind of properties of
local distributions would allow one to design algorithms that can round-off
non-influential functions to globally-feasible integral solutions. Towards
this, Raghavendra and Tan [RT12] showed that local distributions with small
average covariance suffice for this purpose; in particular they showed that
given a gap instance for a $\mu$-constrained CSP instance with completeness
and soundness parameters $c$ and $s$, such that the local distributions
witnessing $c$ have average covariance $o(1)$, there exists a bias-dependent
dictatorship test $\mathcal{T}_{\mu}$ (on some domain $\Omega^{R}$) with the
following properties (Figure 3):

• Completeness. If $f:\Omega^{R}\to[0,1]$ is a dictator, then $f$ passes the
test with probability at least $c-o(1)$, and the relative weight of $f$ w.r.t.
the distribution over the query indices in $\mathcal{T}_{\mu}$ is $\mu$. •
Soundness If $f:\Omega^{R}\to[0,1]$ has no influential coordinates, and has
relative weight $\mu$ under the test distribution $\mathcal{T}_{\mu}$, then
the test accepts with probability at most $s+o(1)$. Figure 3: Bias Dependent
Dictatorship Test

We point out to the readers the construction of $\mathcal{T}_{\mu}$ using the
local distributions itself is identical to that of [Rag08]. On the other hand,
its analysis requires additional work – in particular, in order to establish
an analogue of Theorem 2.1, [RT12] uses the small average-covariance guarantee
to show that the rounded solution would have relative weight close to $\mu$
with high probability, thus allowing the soundness analysis to relate the
acceptance probability to the optimal value of the $\mu$-constrained CSP.

Another key question here is to understand what choice of outer verifier would
be amenable to lifting local $\mu$-constrained dictatorship tests to
(conditional) $\mathsf{NP}$-hardness. As discussed before, for the setting of
globally constrained CSPs, we require outer verifiers with stronger mixing
properties. Specifically, we would want the mixing properties to ensure that
any globally feasible long code table is also locally feasible for most
instantiations of the local tests, so that one cannot create globally feasible
assignments in the reduction that can cheat in a significant fraction of the
local tests.

Mixing Properties for Bias Dependent Tests More formally, suppose we want to
compose the dictatorship test with an outer verifier $\Phi$. Then in the full
reduction, the space of assignments to the instance (say we denote it by
$\mathcal{H}$) usually consists of $f:=\\{f_{A}\\}_{A\in\Phi}$, where each
$f_{A}:\Omega^{R}\to\\{0,1\\}$ is the local assignment corresponding to a
vertex $A\in\Phi$. Now, as is usual in the dictatorship test style reductions,
one can reduce the analysis of the full reduction to that of analyzing the
local tests, i.e., ${\sf Val}_{\mathcal{H}}(f):=\Pr_{A}\Pr_{B\sim
M(A)}\left[\mathcal{T}_{\mu}~{}\textnormal{ accepts }~{}f_{B}\right],$ where
$M$ is a suitable averaging operator on the space of vertices of $\Phi$. Now
the main challenge here is to ensure that for most choices of $A$, the
averaged local assignment $\tilde{f}_{B}={\mathsf{E}}_{B\sim M(A)}f_{B}$
satisfies
${\mathsf{E}}_{x}\tilde{f}_{A}(x)\approx{\mathsf{E}}_{A}{\mathsf{E}}_{x}\tilde{f}_{A}(x)=\mu$,
so that we can leverage the completeness and soundness guarantees of the test
(Figure 3) to argue the completeness and soundness of the full reduction.
Figure 4:

While several constructions exist that provide various trade-offs between such
mixing properties and the PCP sizes (e.g., Mixing Label Cover[HK04], Quasi-
random PCP [Kho06], Birthday Repetition [MR17]), a relatively convenient
choice is the SmallSetExpansion problem, which is more well-suited for
dictatorship test-based reductions for deriving conditional
$\mathsf{NP}$-hardness results.

At this point, while it may appear that one has all the necessary ingredients
for proving Theorem 1.2, it turns out that one still needs to address several
key issues which we outline below:

Composition with SSE. Unfortunately, it turns out that one of the simplest
steps in [Rag08] i.e., composition, is also the trickiest step in this
framework due to our choice of SmallSetExpansion as the outer verifier. The
reason for this is, unlike Unique Games, there is an absence of generic
techniques that can compose dictatorship tests for CSPs with SmallSetExpansion
as is in a black-box way. This is evident in that only a handful of previous
works [RST12, LRV13, Man17, GL22a] have successfully used dictatorship-test-
gadget-based reductions for showing SSEH-based hardness results and in
particular, heavily rely on the techniques of [RST12] to derive the mixing
properties required for the soundness analysis of the full reduction.

Variance Blow-up in Soundness Analysis. A more subtle issue lies in the
analysis of [RT12]’s analogue of Theorem 2.1; in particular, it can only
guarantee that if the average covariance of the local distribution is $\eta$,
then the rounded solution has relative weight bounded in $\mu(1\pm
2^{O(R)}\eta)$, where $R$ is the dimension of the cube corresponding to the
long code table. Since the cube-dimension of long code typically depends
inversely on the volume parameter of the SmallSetExpansion instance, which is
often required to be an extremely small constant as a function of the other
reduction parameters, the weight bound becomes unusable in the context of the
reduction.

Handling the above issues are the key contributions of this work, we expand on
these issues and our techniques for handling them in the remaining sections.

###  2.2 Understanding Composition with SSE

For the purpose of illustration, we will describe a “SSE composable” test from
a gap instance for the Densest-$k$-SubHypergraph (${\sf D}k{\sf SH}$) problem.
Recall that in the ${\sf D}k{\sf SH}_{r}$ problem, we are given a hypergraph
$H=(V,E,w)$ of arity $r$, and the objective is to find a subset of $k$
vertices that induces the maximum weight of hyperedges. Equivalently, in the
terminology used in this work, we can phrase it as a $\mu=k/n$-constrained
Max-CSP instance with the ${\sf AND}$ predicate of arity $r$. Our first
attempt at a test for the ${\sf D}k{\sf SH}_{r}$ problem will be an adaptation
of the test in Figure 2 to the setting of [RST12]. The key difference between
the test from Figure 5 and the test employed in our reduction is the
following: similar to [RST12], in order to break the local gadget structure
and facilitate mixing, we will employ a “folding” operator that acts in a
lifted space. Specifically, instead of defining our long codes to be on the
intended probability space $L_{2}((\Omega^{R},\gamma^{R}))$ (for e.g.,
$(\Omega,\gamma)=\\{0,1\\}_{\mu}$ in Figure 2), we will define the long codes
to be on the lifted space
$L_{2}((\Omega^{R},\gamma^{R})\otimes\\{\bot,\top\\}^{R}_{\beta})$, where
$\\{\bot,\top\\}_{\beta}$ is the distribution on $\\{\bot,\top\\}$ which
assigns measure $\beta$ on ‘$\top$.’ This lifted space allows one to define a
family of stochastic folding operators
$\\{M_{z}\\}_{z\in\\{\bot,\top\\}^{R}}$, which are defined as follows.

######  Definition 2.2 (Noise operator with leakage [RST12])

For any probability space $L_{2}(\Omega^{R},\gamma^{R})$, and
$z\in\\{\bot,\top\\}^{R}$, we define the stochastic functional $M_{z}$ as
follows. For any $x\in\Omega^{R}$, we sample $x^{\prime}\sim M_{z}(x)$ as
follows. Do the following for every $j\in[R]$:

  * •

If $z(j)=\top$, then set $x^{\prime}(j)=x(j)$.

  * •

If $z(j)=\bot$, then sample $x^{\prime}(j)\sim\gamma$ independently.

The above noise operator has several interesting properties that are useful
for breaking the local gadget structure of the reduction. For instance,
observe that for a fixed choice of $z\in\\{\bot,\top\\}^{R}$, the operator
$M_{z}$ folds the probability space $(\Omega^{R},\gamma^{R})$ along the
coordinates where $z(i)=\bot$. Hence, for a randomly sampled
$z\sim\\{\bot,\top\\}^{R}_{\beta}$, the corresponding noise operator $M_{z}$
behaves like the $\beta$-correlated noise operator $T_{\beta}$ on
$(\Omega^{R},\gamma^{R})$ (which in turn ensures the mixing properties (Fig.
4). Then following [RST12], we incorporate these operators into [Rag08]’s test
which yields the following test (described in Figure 5):

Let $(G_{\rm gap},\theta,\tilde{w},w)$ be $(c,s,\ell,\mu,\gamma)$ gap instance
for ${\sf D}k{\sf SH}$.
Input. Long code $f:\\{0,1\\}^{R}\times\\{\bot,\top\\}^{R}\to\\{0,1\\}$
satisfying ${\mathsf{E}}_{i\sim G_{\rm
gap}}{\mathsf{E}}_{x\sim\\{0,1\\}^{R}_{\mu_{i}}}{\mathsf{E}}_{z\sim\\{\bot,\top\\}^{R}_{\beta}}\left[f(x,z)\right]=\mu.$
(1) Setup. For every edge $e$, and $i\in e$, $x_{i}$ and $z_{i}$ are
$\\{0,1\\}^{R}$ and $\\{\bot,\top\\}^{R}$-valued vector random variables.
Furthermore, let $\mathcal{D}^{R}_{e}$ be the joint distribution (to be
determined later) on variables $(x_{i},z_{i})_{i\in e}$.
Test. 1. Sample edge $e\sim E$. 2. Long code Step. • For every $j\in[R]$,
sample $(x_{i}(j),z_{i}(j))_{i\in e}$ from the joint distribution
$\mathcal{D}^{R}_{e}$. • For every $i\in e$, sample $(1-\eta)$-correlated
copies $(\tilde{x}_{i},z^{\prime}_{i})\underset{1-\eta}{\sim}(x_{i},z_{i})$.
3. Folding Step. • For every $i\in[r]$, sample $x^{\prime}_{i}\sim
M_{z^{\prime}_{i}}(\tilde{x}_{i})$. 4. Accept if and only if
$f(x^{\prime}_{i},z^{\prime}_{i})=1~{}~{}~{}~{}~{}~{}\forall i\in[R].$ Figure
5: Test Framework for SSEH Reduction

Informally, the test in Figure 5 first samples $(x_{i},z_{i})_{i\in e}$ from a
distribution which is intended to enforce the checks corresponding to the test
in Figure 2, following which it re-randomizes, and then folds each $x_{i}$
vector variables via the $M_{z_{i}}$ operator666In the actual reduction, the
folding step also folds along the space of vertices of the outer verifiers
(See Footnote 10).. Clearly, the main factor determining the properties of
this test is the family of joint distributions
$\\{\mathcal{D}^{R}_{e}\\}_{e\in E}$ on the $(x_{i},z_{i})$ variables, which
has to be designed carefully to ensure several properties which we briefly
describe below.

The key issue here is that while the choice of the distribution of the $x_{i}$
variables is clear, apriori, the distribution of the $z_{i}$ variables is not
immediate as these are auxiliary variables that are introduced to ensure the
mixing properties required for the reduction (Figure 4), and as such, are not
immediately relatable to the SDP solution of the gap instance. Ideally, we
would want to introduce the $z_{i}$ variables to the test in a way such that
they facilitate the mixing properties, and then we would like to carry out the
completeness and soundness analysis of the test as before just using the
properties of the distribution of the $x_{i}$ variables. Unfortunately, this
“modular” scenario is somewhat of a pipe dream as the $z_{i}$ variables end up
affecting the completeness and soundness properties in unexpectedly non-
trivial ways. To illustrate this, let us try out a couple of elementary
approaches and see why they fail. Fix an edge $e=[r]$, and let
$z_{1},\ldots,z_{r}$ be the corresponding variables from the test distribution
conditioned on the fixing of $e$.

  * •

Suppose $z_{1},\ldots,z_{r}$ are sampled completely independently. Then
because of the folding step, the resulting
$(\tilde{x}_{i},{z}^{\prime}_{i})$-variables will be almost independent for
different choices of $i\in[r]$. In that case, dictator functions would no
longer be able to exploit the correlations along a single coordinate, thus
resulting in poor completeness parameters.

  * •

On the other hand, let us consider the case where $z_{i}$’s are identical
random variables (i.e., completely correlated). Then it is possible to
construct long code assignments which depend only on the $z$-variable
component (i.e., $f(x,z)=h(z)$ for some function $h$) that does strictly
better than the intended soundness of the basic test, which actually relies on
the correlation structure of the $(x_{i})_{i}$-variables.

Another bottleneck is that the soundness analysis of [Rag08, RT12] – and
Theorem 2.1 in particular – crucially relies on the fact that under the test
distribution, the ensemble of $(x_{i})_{i}$ variables satisfy the following
property: the covariance structure of the variables along any coordinate
$j\in[R]$ is identical to that of the corresponding local variables
$(X_{i})_{i}$ under the SDP solution $\theta$. On the other hand, the
inclusion of the additional $(z_{i})_{i}$ variables in our setting makes the
correlation structure of the resulting set of variables $(x_{i},z_{i})_{i\in
V_{\rm gap}}$ incomparable of correlation structure of the vector solution,
and rules out the possibility of carrying out [Rag08]’s soundness analysis in
the lifted space as is.

###  2.3 Our Approach: Weak Coupling of $z$ Variables

Our approach towards addressing the above is that we devise a way of sampling
the $(x_{i},z_{i})$ variables in a coupled way such that the correlation
structure of the $z_{i}$ variables does not overwhelm the $x_{i}$ variables,
while still being correlated enough to guarantee that (i) the test has the
required completeness/soundness properties (up to some loss) under the
resulting distribution (Figure 3), and (ii) the corresponding folding
operators $\\{M_{z}\\}_{z}$ have the desired mixing properties (Figure 4). In
particular, our construction of the joint distribution will have the following
key property: if $f$ is non-influential, then we can decouple the
$(z_{i})_{i}$ variables and “average them out” so that the soundness analysis
reduces to the setting where the resulting function is just dependent on the
$x_{i}$ variables, thus enabling the use of [Rag08, RT12]’s rounding argument
to conclude the soundness analysis.

Towards stating our idea more formally, let us begin by defining the
collection of distributions $(\mathcal{D}^{R}_{e})_{e\in E_{\rm gap}}$:

######  Definition 2.3 (Distribution $\mathcal{D}^{R}_{e}$)

For any edge $e=(i_{1},\ldots,i_{r})\in E_{\rm gap}$, let
$\mathcal{D}^{R}_{e}$ be the following joint distribution over variables
$(x_{i},z_{i})_{i\in e}$. Firstly, $(x_{i_{1}},\ldots,x_{i_{r}})$ are jointly
distributed $R$-dimensional variables such that
$(x_{i_{1}}(j),\ldots,x_{i_{r}}(j))\sim\theta_{e}$ for every $j\in[R]$ (as in
Figure 2). Furthermore, $(z_{1},\ldots,z_{r})$ are $r$ vector-valued random
variables of dimension $R$, such that for every coordinate $j\in[R]$, the
variables $(z_{i}(j))_{i\in e}$ is distributed (independent of $(x_{i})_{i\in
e}$) as follows. Sample a common assignment
$z=(z(j))_{j\in[R]}\sim\\{\bot,\top\\}^{R}_{\beta}$, and then do the following
for every $j\in[R]$ independently:

  * •

W.p. $\rho$, set every variable $(z_{i}(j))_{i\in e}$ to $z(j)$.

  * •

W.p. $1-\rho$, we sample $z_{i}(j)\sim\\{\bot,\top\\}_{\beta}$ independently
for each $i\in e$.

The following lemma (stated for $e=[r]$) says that if $\rho$ is small enough
as a function of $\mu$ and $r$, and the functions
$f_{1}(x_{1},z_{1}),\ldots,f_{r}(x_{r},z_{r})$ have small influences, then
under the above distribution, the product of the functions $\prod_{i\in
e}f_{i}(x_{i},z_{i})$ would behave near-identically to the distribution where
$z_{i}$’s are fully independent.

######  Lemma 2.4 (Informal version of Lemma 7.3)

Let $r\geq 2$ and $\mu\in(0,1)$ be small enough. Let $f_{1},\ldots,f_{r}$ be
functions, such that $f_{i}\in
L_{2}((\\{0,1\\}_{\mu_{i}}\otimes\\{\bot,\top\\}_{\beta})^{R})$ has its
influences bounded by $\tau(\mu,r)$, where $\tau(\mu,r)$ depends only on $\mu$
and $r$. Furthermore, suppose $\rho\leq 1/(4r^{2}\log(1/\mu)^{2})$. Then,

${\mathsf{E}}_{(x_{i},z_{i})_{i\in[r]}\sim\mathcal{D}^{R}_{e}}\left[\prod_{i\in[r]}f_{i}(x_{i},z_{i})\right]\lesssim_{r}{\mathsf{E}}_{(x_{i})_{i\in[r]}\sim\theta^{R}_{e}}\left[\prod_{i\in[r]}{\mathsf{E}}_{z_{i}\sim\\{\bot,\top\\}^{R}_{\beta}}f_{i}(x_{i},z_{i})\right]+\mu^{r},$

where $\lesssim_{r}$ hides multiplicative factors which depend only on $r$.

The above lemma is a key component of our soundness analysis, and we sketch a
proof of the lemma later in this section. It implies that at the cost of
making $(z_{i})_{i}$ variables slightly correlated (due to which we get
slightly weaker completeness), we can average them out completely when the
functions $f_{1},\ldots,f_{r}$ all have small influences. We point out that
the (weaker) observation that products low-degree functions on slightly
correlated spaces behave almost similarly to the independent setting is not
new in the hardness literature, and has been used in several works [MNT16,
KS15, GL22a]. However, the above half-decoupling version (which retains the
correlation structure on the $x_{i}$ variables, while making the slightly
correlated $z_{i}$ variables completely independent) is new to the literature
to the best of our knowledge, and requires more ideas.

The above immediately provides a way of stitching together the $(x_{i})_{i}$
and $(z_{i})_{i}$ variables to derive the test distribution over the lifted
space $L_{2}(\Omega^{R})$. Our final test is the test from Figure 5 where for
every $e\in E_{\rm gap}$, the joint distribution over $(x_{i},z_{i})_{i\in e}$
variables is the distribution $\mathcal{D}^{R}_{e}$ from Definition 2.3. We
now briefly analyze this test, and then conclude this part by providing a
proof sketch of Lemma 2.4.

Completeness. Due to the introduction of the $z_{i}$-variables, the
completeness analysis is relatively more involved in SSE based reductions.
Here, the basic idea is to use the $z$-vector to identify the choice of the
dictator function. Let $j^{*}:\\{\bot,\top\\}^{R}\to[R]$ be the following map:
For $z\in\\{\bot,\top\\}^{R}$, if there exists a unique index
$j^{\prime}\in[R]$ such that $z(j^{\prime})=\top$, assign
$j^{*}(z)=j^{\prime}$, otherwise assign $j$ arbitrarily. Finally, for any $z$,
we define the map777Here we denote $f_{z}(x)=f(x,z)$ for every $x,z$.
$f_{z}(x)=x({j^{*}(z)})$.

To analyze this assignment, let us consider the test distribution for fixed
edge ${\sf e}=[r]$. Our first step is to observe that setting $R=1/r\beta$,
with probability at least $e^{-1}/r$ over the draw of
$z\sim\\{\bot,\top\\}^{R}_{\beta}$, we will have that there exists a unique
index $j^{\prime}\in[R]$ such that $z(j^{\prime})=\top$. Furthermore,
conditioned on this, we can argue that with probability at least
$\rho(1-(1-\rho)r\beta)^{1/r\beta}\gtrsim\rho\cdot e^{-1}$, we have that
$z_{1},\ldots,z_{r}$ also have $j^{\prime}$ as the unique index such that
$z_{i}(j^{\prime})=\top$. In other words, we will have
$j^{*}(z_{i})=j^{\prime}$ for every $i\in[r]$. This in turn implies that
$f_{z_{1}},\ldots,f_{z_{r}}=x(j^{\prime})$ i.e., they will be identical
dictator functions. Note that since $(x_{i})_{i}$ and $(z_{i})_{i}$ variables
are independent under the test distribution, conditioning on the above events
does not affect the distribution of $(x_{i})_{i}$. Therefore, conditioning on
the above, we can bound the probability of the test accepting as

$\Pr_{(x_{i})_{i\in[r]}}\left[~{}\forall_{i}~{}f_{z_{i}}(x_{i})=1\right]=\Pr_{(x_{i})_{i\in[r]}}\left[~{}\forall_{i}~{}x_{i}(j^{\prime})=1\right]=p_{\sf
e},$

where $p_{\sf e}=\Pr_{X_{\sf e}\sim\theta_{\sf e}}\left[X_{\sf e}=1_{\sf
e}\right]$ is the probability of the $\theta$ satisfying edge ${\sf e}$.
Therefore, for a fixed edge ${\sf e}$, the test accepts the assignment with
probability at least $(1/er)\rho\cdot e^{-1}\cdot p_{\sf e}$. Averaging over
the choice of ${\sf e}$, we have that the overall the test accepts with
probability $\Omega(\rho\cdot c/r)$. Furthermore, since $f_{z}$ is a dictator
function for every choice of $z$, overall $f$ is a feasible assignment888We
point out that the factor $\Omega(\rho)$ loss in the completeness of the
reduction is the main reason behind the SSEH hardness losing an additional
factor of $\Omega_{r}(\log(1/\mu)^{2})$..

Soundness. For the soundness analysis, as is usual, let
$f:\\{0,1\\}^{R}\times\\{\bot,\top\\}^{R}\to\\{0,1\\}$ be a feasible
assignment i.e, it satisfies the weight constraint

${\mathsf{E}}_{i\sim G_{\rm
gap}}{\mathsf{E}}_{x\sim\\{0,1\\}^{R}_{\mu_{i}}}{\mathsf{E}}_{z\sim\\{\bot,\top\\}^{R}_{\beta}}\left[f(x,z)\right]=\mu.$

Furthermore, for the soundness analysis, we will assume that $f$ has no
influential coordinates999In the actual argument, for any fixed edge $e\in
E_{\rm gap}$ the small influences condition needs to be defined with respect
to probability space $(\\{0,1\\}_{\mu_{i}}\otimes\\{\bot,\top\\}_{\beta})$ for
every vertex $i\in e$. Using influence decoding arguments, we will then be
able to show that this happens for most choices of $e$ in the soundness
analysis of the reduction.. Firstly, using the observation that the
dictatorship test for ${\sf D}k{\sf SH}$ simply performs AND checks, we can
arithmetize the probability of the test accepting as:

$\Pr\left[\mbox{Test Accepts
}\right]={\mathsf{E}}_{e}{\mathsf{E}}_{(x^{\prime}_{i},z^{\prime}_{i})_{i\in
e}}\left[\prod_{i\in e}f(x^{\prime}_{i},z^{\prime}_{i})\right].$

Next, by averaging over the action of $M_{z}$ operator and the
$(1-\eta)$-correlated noise operator, i.e.,
$\tilde{f}(x,z)={\mathsf{E}}_{(\tilde{x}_{i},z^{\prime}_{i})\sim\mathcal{T}_{1-\eta}(x,z)}{\mathsf{E}}_{x^{\prime}_{i}\sim
M_{z_{i}}(x_{i})}f(x^{\prime}_{i},z^{\prime}_{i})$, we may further re-write
the above RHS as:

${\mathsf{E}}_{e}{\mathsf{E}}_{(x^{\prime}_{i},z^{\prime}_{i})_{i\in
e}}\left[\prod_{i\in
e}f(x^{\prime}_{i},z^{\prime}_{i})\right]={\mathsf{E}}_{e}{\mathsf{E}}_{(x_{i},z_{i})_{i\in
e}\sim\mathcal{D}^{R}_{e}}\left[\prod_{i\in e}\tilde{f}(x_{i},z_{i})\right].$
(2)

We point out that while the above averaging step might seem superfluous in the
context of the (local) analysis of the dictatorship test on a single function,
it is a crucial step in the actual reduction where it leverages the mixing
properties of the $M_{z}$ operator to ensure that the globally feasible long
code table is also locally feasible for most local instantiations of the
test101010In particular, in the actual reduction, the full assignment consists
of assignments
$\\{f_{A}\\}_{A}:\\{0,1\\}^{R}\times\\{\bot,\top\\}^{R}\to\\{0,1\\}$ where
$f_{A}$ is the local assignment for a vertex $A$ in ($R$-powered) SSE
instance. The folding step (2) along with the spectral properties of the
$\\{M_{z}\\}$ operators would ensure that
${\mathsf{E}}_{(x,z)}\tilde{f}_{A}(x,z)\approx{\mathsf{E}}_{A}{\mathsf{E}}_{x,z}\tilde{f}_{A}(x,z)$
for most choices of $A$. We point the readers to Lemma 7.9 for a more formal
statement of this guarantee..

Now assuming $\tilde{f}$ has no large influences, using Lemma 2.4, we can
decouple the $z_{i}$ variables and average them out:

$\displaystyle{\mathsf{E}}_{e}{\mathsf{E}}_{(x_{i},z_{i})_{i\in
e}\sim\mathcal{D}^{R}_{e}}\left[\prod_{i\in e}\tilde{f}(x_{i},z_{i})\right]$
$\displaystyle\lesssim_{r}{\mathsf{E}}_{e}{\mathsf{E}}_{(x_{i})_{i\in
e}\sim\theta^{R}_{e}}\left[\prod_{i\in
e}{\mathsf{E}}_{z_{i}\sim\\{\bot,\top\\}^{R}_{\beta}}\tilde{f}(x_{i},z_{i})\right]+o(1)$
$\displaystyle={\mathsf{E}}_{e}{\mathsf{E}}_{(x_{i})_{i\in
e}\sim\theta^{R}_{e}}\left[\prod_{i\in e}\overline{f}(x_{i})\right]+o(1),$

where
$\overline{f}(x)={\mathsf{E}}_{z\sim\\{\bot,\top\\}^{R}_{\beta}}\left[\tilde{f}(x,z)\right]$.
Finally, note that the expression in the above RHS precisely corresponds to
accepting probability of the test $\mathcal{T}_{\rm UGC}$ (from Figure 2)
w.r.t. assignment $\overline{f}(\cdot)={\mathsf{E}}_{z}\tilde{f}(\cdot,z)$.
Therefore, again assuming that $\overline{f}$ has small influences111111Note
that now the influences of $\overline{f}$ have to be measured w.r.t. the
probability space $\\{0,1\\}^{R}_{\mu_{i}}$., we can invoke [RT12]’s soundness
analysis to show that

${\mathsf{E}}_{e}{\mathsf{E}}_{(x_{i})_{i\in
e}\sim\theta^{R}_{e}}\left[\prod_{i\in
e}\overline{f}(x_{i})\right]\lesssim{\sf Opt}_{\mu}(G),$

which concludes the soundness analysis.

###### Remark 2.5

The key difference between the distribution employed by the test in this work
and those of [RST12] is the following: here, the $(x_{i})_{i}$ and
$(z_{i})_{i}$ variables are sampled independent from each other, whereas in
[RST12] the variables $(x_{i_{1}},z_{i_{1}}),\ldots,(x_{i_{r}},z_{i_{r}})$ are
sampled as independent $\rho$-correlated copies of some common assignment
$(x,z)$, and in particular, $(x_{i})_{i}$ and $(z_{i})_{i}$ are not
independent. This is crucially used in their analysis as they can use Noise
Stability [MOO10] based arguments in the joint space of $(x_{i},z_{i})$
variables to argue soundness in one shot. However, executing a similar
correlated-sampling based composition for arbitrary bias dependent tests is
known to be challenging and might require newer tools for composition [RT12].

On the other hand, the independence of $(x_{i})_{i}$ and $(z_{i})_{i}$
variables, and the distribution on the $(z_{i})_{i}$ variables under our test
distribution allow us to de-couple and average out the effect of $z_{i}$
variables in the soundness analysis, thus effectively letting us run our
soundness analysis in the space of $(x_{i})_{i}$ variables.

###  2.4 Establishing Lemma 2.4

We sketch a proof of Lemma 2.4 here, since it is the key technical result that
drives our soundness analysis. Recall that in the setting of the lemma, we are
given $R$-variate functions $f_{1},\ldots,f_{r}:\Omega^{R}\to[0,1]$, where
$\Omega=\\{0,1\\}\times\\{\bot,\top\\}$, which satisfy the condition

$\max_{j\in[R]}{\sf Inf}_{(x_{i},z_{i})_{j}}\left[f_{i}\right]\leq\tau(\mu,r)$

for every $i\in[r]$. Our first step is to show that we can transfer the above
small-influences condition in the $R$-variate space (w.r.t. variables
$(x_{i},z_{i})_{1},\ldots,(x_{i},z_{i})_{R})$ to a small-influences condition
in the $2R$-variate space (w.r.t. variables
$(x_{i}(1),\ldots,x_{i}(R),z_{i}(1),\ldots,z_{i}(R))$, and show that121212We
point out that we can only assume that the function has small influences in
the $R$-variate space, since directly assuming the small influences condition
in the $2R$-variate space is insufficient for the influence decoding argument.

$\max\Big{\\{}{\sf Inf}_{x_{i}(j)}\left[f_{i}\right],{\sf
Inf}_{z_{i}(j)}\left[f_{i}\right]\Big{\\}}\leq{\sf
Inf}_{(x_{i},z_{i})_{j}}\left[f_{i}\right]\leq\tau.$

The above follows from the observation that since $f_{i}$’s are defined on the
probability space
$\Omega^{R}_{i}:=(\\{0,1\\}_{\mu}\otimes\\{\bot,\top\\}_{\beta})^{R}$, we can
use the Fourier characters for $\\{0,1\\}_{\mu_{i}}$ and
$\\{\bot,\top\\}_{\beta}$ to derive a basis for $\Omega^{R}_{i}$ (see Claim
8.3 for the formal proof of the above inequality). Then, using the Fourier
expansion of $f_{i}$ in $2R$-dimensional space, we can write it as a multi-
linear polynomial:

$f_{i}(x_{i},z_{i})=\sum_{S,T\subseteq[R]}\widehat{f_{i}}(S,T)\prod_{j\in
S}\phi^{(\mu_{i})}(x_{i}(j))\prod_{j^{\prime}\in
T}\phi^{(\beta)}(z_{i}(j^{\prime})),$ (3)

where $\phi^{(\mu_{i})}$ and $\phi^{(\beta)}$ are the non-trivial Fourier
characters in the $\mu_{i}$ and $\beta$-biased Boolean spaces. Then, as is
standard, we extend $f_{i}$ to a $2R$-variate multi-linear polynomial
$H_{i}:\mathbbm{R}^{2R}\to\mathbbm{R}$ as

$H_{i}(\mathcal{W}^{x}[i],\mathcal{W}^{z}[i])=\sum_{S,T\subseteq[R]}\widehat{h_{i}}(S,T)\prod_{j\in
S}\mathcal{W}^{x}_{j}[i]\prod_{j^{\prime}\in
T}\mathcal{W}^{z}_{j^{\prime}}[i],$

where under the distribution,
$\mathcal{W}^{x}_{j}[i]:=\phi^{(\mu_{i})}(x_{i}(j))$ and
$\mathcal{W}^{z}_{j}[i]:=\phi^{(\beta)}(z_{i}(j))$. Next, since the functions
$f_{1},\ldots,f_{r}$ (and consequently the polynomials $H_{1},\ldots,H_{r}$)
have small influences, using the Invariance principle (Theorem 3.5), we can
move the analysis from the Boolean space to the Gaussian space and show that

${\mathsf{E}}_{(x_{i},z_{i})_{i\in[r]}}\left[\prod_{i\in[r]}f_{i}(x_{i},z_{i})\right]={\mathsf{E}}_{\mathcal{W}}\left[\prod_{i\in[r]}H_{i}(\mathcal{W}^{x}[i],\mathcal{W}^{z}[i])\right]\approx{\mathsf{E}}_{\mathcal{G}}\left[\prod_{i\in[r]}H_{i}(g_{x,i},g_{z,i})\right]$
(4)

such that $\mathcal{G}:=(g_{x,i},g_{z,i})_{i\in[r]}$ is a collection of
$r\times R$ jointly distributed Gaussian random variables which matches the
covariance structure of $\mathcal{W}$. In particular, the matching covariance
structure will imply the following properties:

  * •

For every $i\in[r]$, $g_{x,i}$ and $g_{z,i}$ are marginally distributed as
$R$-dimensional standard Gaussian vectors.

  * •

$(g_{x,i})_{i\in[r]}$ and $(g_{z,i})_{i\in[r]}$ are independent from each
other – this is where we use the fact that under the test distribution
$\mathcal{D}^{R}_{[r]}$, the $(x_{i})_{i}$ and $(z_{i})_{i}$ variables are
independent of each other.

  * •

Furthermore, the covariance structure of the $(z_{i})_{i\in[r]}$ variables
implies that $g_{z,1},\ldots,g_{z,r}$ will be distributed as $r$ independent
$\sqrt{\rho}$-correlated copies of a standard Gaussian vector $g\sim
N(0_{R},I_{R})$.

The above properties allow us to re-write the RHS of (4) as:

${\mathsf{E}}_{\mathcal{G}}\left[\prod_{i\in[r]}H_{i}(g_{x,i},g_{z,i})\right]={\mathsf{E}}_{(g_{x,i})_{i\in[r]}}{\mathsf{E}}_{g_{z,1},\ldots,g_{z,r}\underset{\sqrt{\rho}}{\sim}g}\left[\prod_{i\in[r]}{H}_{i}(g_{x,i},g_{z,i})\right].$
(5)

Averaging out $(g_{z,i})^{r}_{i=1}$. The next step is the crucial part of the
proof. Consider for any fixing of $(g_{x,i})_{i\in[r]}$; note that this does
not affect the distribution of $g_{z,1},\ldots,g_{z,r}$. Then using the
Gaussian rearrangement from the multi-dimensional Borell’s Isoperimetric
Inequality (Theorem 3.6), we can upper bound the inner expectation from (5) as

${\mathsf{E}}_{g_{z,1},\ldots,g_{z,r}\underset{\sqrt{\rho}}{\sim}g}\left[\prod_{i\in[r]}{H}_{i}(g_{x,i},g_{z,i})\right]\leq\Lambda_{\sqrt{\rho}}\Big{(}{\mathsf{E}}_{g_{z,1}}{H}_{i}(g_{x,1},g_{z,1}),\ldots,{\mathsf{E}}_{g_{z,r}}{H}_{r}(g_{x,r},g_{z,r})\Big{)}.$

Here $\Lambda_{\sqrt{\rho}}(\delta_{1},\ldots,\delta_{r})$ is the $r$-ary
Gaussian noise stability131313Formally,
$\Lambda_{\rho}(\delta_{1},\ldots,\delta_{r})=\Pr_{g\sim
N(0,1)}\Pr_{g_{1},\ldots,g_{r}\underset{\rho}{\sim}g}\left[~{}\forall_{i}~{}g_{i}\leq\Phi^{-1}(\delta_{i})\right]$
where $\Phi(\cdot)$ is the Gaussian CDF function. for $\sqrt{\rho}$-correlated
Gaussians w.r.t. halfspaces of Gaussian volumes
$\delta_{1},\ldots,\delta_{r}$. Furthermore, using our choice of $\rho$ and
explicit bounds on the multivariate Gaussian CDF (Lemma 8.1), we can
bound141414In the actual analysis, we will lose the additive factor of
$\mu^{r}$ only when ${\mathsf{E}}_{g_{z,i}}H_{i}(g_{x,i},g_{z,i})\leq\mu^{r}$
for some $i\in[r]$.

$\Lambda_{\sqrt{\rho}}\Big{(}{\mathsf{E}}_{g_{z,1}}{H}_{i}(g_{x,1},g_{z,1}),\ldots,{\mathsf{E}}_{g_{z,r}}{H}_{r}(g_{x,r},g_{z,r})\Big{)}\lesssim_{r}\prod_{i\in[r]}{\mathsf{E}}_{g_{z,i}}\left[{H}_{i}(g_{x,i},g_{z,i})\right]+\mu^{r}.$

Applying the above sequence of arguments for each fixing of
$(g_{x,i})_{i\in[r]}$, we get that

${\mathsf{E}}_{(g_{x,i})_{i\in[r]}}{\mathsf{E}}_{g_{z,1},\ldots,g_{z,r}\underset{\rho}{\sim}g}\left[\prod_{i\in[r]}H_{i}(g_{x,i},g_{z,i})\right]\lesssim_{r}{\mathsf{E}}_{(g_{x,i})_{i\in[r]}}\left[\prod_{i\in[r]}{\mathsf{E}}_{g_{z,i}}H_{i}(g_{x,i},g_{z,i})\right]+\mu^{r}.$

Finally, again using the Invariance principle, we can transfer the analysis
back to the setting of $(x_{i},z_{i})$ variables and get that

${\mathsf{E}}_{(g_{x,i})_{i\in[r]}}\left[\prod_{i\in[r]}{\mathsf{E}}_{g_{z,i}}H_{i}(g_{x,i},g_{z,i})\right]\approx{\mathsf{E}}_{(\mathcal{W}^{x}[i])_{i\in[r]}}\left[\prod_{i\in[r]}{\mathsf{E}}_{\mathcal{W}^{z}[i]}H_{i}(\mathcal{W}^{x}[i],\mathcal{W}^{z}[i])\right]={\mathsf{E}}_{(x_{i})_{i\in[r]}}\left[\prod_{i\in[r]}{\mathsf{E}}_{z_{i}}f_{i}(x_{i},z_{i})\right].$

Putting the above inequalities together completes the proof.

###  2.5 Handling the Variance Blow-up

We conclude our discussion by briefly describing our approach to handling the
$2^{O(R)}$-blow-up in relative weight guarantee in [RT12]’s soundness
analysis. Roughly, in their analysis, the $2^{O(R)}$-blow up results from
trying to relate the covariance of the rounded values to covariance of the
corresponding local variables. The following proposition states their bound
from this step formally.

######  Proposition 2.6 (Implicit in [RT12])

Let $F:\mathbbm{R}^{R}\to[0,1]$ be an $R$-variate function. Let
$(X_{i},X_{j})$ be a pair of jointly distributed $\\{0,1\\}$-valued random
variables, and let $(g_{i},g_{j})$ be a pair of jointly distributed
$R$-dimensional Gaussian random variables such that
$(g_{i}(\ell),g_{j}(\ell))$ matches the covariance structure of
$(X_{i},X_{j})$ for every $\ell\in[R]$. Then,

$|{\mathsf{E}}F(g_{i})F(g_{j})-{\mathsf{E}}F(g_{i}){\mathsf{E}}F(g_{j})|\leq
2^{O(R)}|{\rm Cov}(X_{i},X_{j})|.$

Their analysis needs to use the above bound since the local-distributions used
to construct their test can only guarantee a bound on the average covariance.
This eventually results in an additional $2^{O(R)}$ multiplicative blow-up in
the variance of the weight of the rounded solution, which in turn shows up as
the multiplicative error term in the relative weight.

Our Fix. Towards addressing this, our first observation is that since $F$ is
$[0,1]$-valued, one can directly bound the covariance of the rounded values
using the correlation of the Gaussian vector variables i.e., using elementary
Hermite analysis one can show that

$|{\mathsf{E}}F(g_{i})F(g_{j})-{\mathsf{E}}F(g_{i}){\mathsf{E}}F(g_{j})|\leq|{\rm
Corr}(X_{i},X_{j})|,$

where ${\rm Corr}(X_{i},X_{j})$ is the correlation 151515Formally, ${\rm
Corr}(X_{i},X_{j})=\frac{{\mathsf{E}}\left[X_{i}X_{j}\right]-\mu_{i}\mu_{j}}{\sqrt{\mu_{i}(1-\mu_{i})}\sqrt{\mu_{j}(1-\mu_{j})}}$,
where $\mu_{i}={\mathsf{E}}[X_{i}],\mu_{j}={\mathsf{E}}[X_{j}]$. between
$X_{i}$ and $X_{j}$ under the local distribution. Hence, if we started with a
local distribution with small average-correlation, then we would be able to
get a $R$-independent bound on the variance of the rounded weight. However,
note that in general the correlation of a pair of random variable is
incomparable to its covariance, and hence a bound on the average covariance is
insufficient to exploit this observation. To get around this issue, we use the
observation that random conditionings of smoothened Lasserre solutions
directly yield local distributions with the stronger property of small average
correlation. Combining this with the above observation yields the improved
bound on the variance of the rounded solution. We refer the readers to
Sections 4 and 10 for more details on this.

##  3 Notation and Preliminaries

We introduce some frequently used notation in this work. Given a distribution
$\mathcal{D}$, we will use $x\sim\mathcal{D}$ to denote the draw of a random
variable $x$ from the distribution $\mathcal{D}$. We use
$x_{1},\ldots,x_{r}\sim\mathcal{D}$ to denote $r$-independent draws from the
distribution $\mathcal{D}$. If $x$ is vector-valued, then we use $x(j)$ to
denote the $j^{th}$ entry of the variable $x$. Furthermore if
$(x_{1},\ldots,x_{r})$ are jointly distributed as $\mathcal{D}$, then we use
$(x_{i})_{i\in[r]}\sim\mathcal{D}$ to denote a single draw of
$(x_{1},\ldots,x_{r})$ from $\mathcal{D}$, and it is not to be confused with
the notation $x_{1},\ldots,x_{r}\sim\mathcal{D}$ defined above. For $R\geq 1$,
for any positive semidefinite matrix $\Sigma\in\mathbbm{R}^{R\times R}$, we
use $N(0_{R},\Sigma)$ to denote the distribution over $R$-dimensional Gaussian
distribution with mean $0_{R}$ and covariance matrix $\Sigma$; here $0_{R}$
denotes the all-zeros vector of dimension $R$. We use $I_{R}$ to denote the
identity matrix of dimension $R\times R$. We will also use $\Pi_{[0,1]}$ to
denote the clipping function which is defined as

$\Pi_{[0,1]}(x)=\begin{cases}0&\mbox{ if }x<0,\\\ x&\mbox{ if }x\in[0,1],\\\
1&\mbox{ if }x>1.\end{cases}$ (6)

For any $R\in\mathbbm{N}$, we use $\mathbbm{S}_{R}$ to denote the set of
permutations on $R$ indices. For any $R$-dimensional vector $x$, and
permutation $\pi\in\mathbbm{S}_{R}$, we use $\pi(x)$ to denote permuted vector
$(x(\pi(1)),x(\pi(2)),\ldots,x(\pi(R)))$.

###  3.1 Fourier Analysis

A finite probability space $(\Omega,\mu)$ is characterized by a set $\Omega$
and a measure $\mu$ on the set. The vector space of all square integrable
functions on $\Omega$ w.r.t. measure $\mu$ is denoted as $L_{2}(\Omega,\mu)$.
For ease of notation, whenever the measure is clear from context, we will omit
the measure and simply write $L_{2}(\Omega)=L_{2}(\Omega,\mu)$. Given a
probability space $(\Omega,\mu)$ a Fourier basis for $L_{2}(\Omega,\mu)$ is an
orthornomal basis $\phi_{0}\equiv
1,\phi_{1},\ldots,\phi_{|\Omega|-1}:\Omega\to\mathbbm{R}$.

Using these Fourier bases, we can construct a basis for functions on the
product probability spaces. Formally, given a product probability space
$L_{2}(\prod_{i\in[R]}\Omega_{i},\prod_{i\in[R]}\mu_{i})$, let
$\phi_{i,0}\equiv 1,\ldots,\phi_{i,|\ell_{i}|-1}:\Omega_{i}\to\mathbbm{R}$
denote the Fourier basis for $L_{2}(\Omega_{i},\mu_{i})$, where
$\ell_{i}:=|\Omega_{i}|$. Given this basis, the elements of the Fourier basis
for $L_{2}(\prod_{i}\Omega_{i},\prod_{i}\mu_{i})$ are
$\\{\phi_{\alpha}\\}_{\alpha\in\prod_{i\in[r]}\mathbbm{Z}^{R}_{\leq\ell_{i}-1}}$
where

$\phi_{\alpha}(\omega)=\prod_{i\in[R]}\phi_{i,\alpha(i)}(\omega(i))\qquad\qquad~{}\forall~{}\omega\in\Omega^{R},\alpha\in\prod_{i\in[R]}\mathbbm{Z}_{\leq\ell_{i}-1}.$

Using this basis, any $f\in L_{2}(\Omega^{R})$ can be expressed as a multi-
linear polynomial in $\\{\phi_{i}\\}_{i\in|\Omega|-1}$ as

$f(\omega)=\sum_{\alpha\in\prod_{i\in[R]}\mathbbm{Z}_{\leq\ell_{i}-1}}\widehat{f}(\alpha)\prod_{i\in[R]}\phi_{\alpha(i)}(\omega(i))$

where $\widehat{f}(\alpha)$ is referred to as the Fourier coefficient
corresponding to multi-index $\alpha$.

Influences. Given a function $f\in
L_{2}(\prod^{R}_{i=1}\Omega_{i},\prod^{R}_{i=1}\mu_{i})$, the influence of a
coordinate $j\in[R]$ on function $f$ – denoted as ${\sf
Inf}^{(\mu_{j})}_{j}\left[f\right]$ – is defined as

${\sf
Inf}_{j}\big{[}f\big{]}={\mathsf{E}}_{(\omega(j^{\prime}))_{j^{\prime}\neq
j}\sim\prod_{j^{\prime}\neq j}\mu_{j^{\prime}}}\left[{\rm
Var}_{\omega(j)}\left[f(\omega(1),\ldots,\omega(j))\right]\right].$

It is well-known that the influences can be expressed in terms of the Fourier
coefficients of the function, as stated in the following fact.

###### Fact 3.1

Given a function $f\in
L_{2}(\prod_{i\in[r]}\Omega_{i},\prod_{i\in[r]}\mu_{i})$, for any fixed choice
of Fourier basis, we have

${\sf Inf}_{j}\big{[}f\big{]}=\sum_{\alpha:\alpha(j)\neq
0}\widehat{f}(\alpha)^{2}.$

Noise Operator Given a product probability space $L_{2}(\Omega^{R},\mu^{R})$,
and a $\omega\in\Omega^{R}$, for any $\rho\in[0,1]$, a $\rho$-correlated copy
of $\omega$ – denoted as $\omega^{\prime}\underset{\rho}{\sim}\omega$ is
sample as follows. For every $j\in[R]$, do the following independently:

  * •

W.p. $\rho$, set $\omega^{\prime}(j)=\omega(j)$.

  * •

W.p. $1-\rho$, sample $\omega^{\prime}(j)\sim\mu$ independently.

Then, the $\rho$-correlated noise operator in the space $(\Omega_{R},\mu^{R})$
is the stochastic operator $\mathcal{T}^{(\Omega)}_{\rho}$ defined as

$\mathcal{T}^{(\Omega)}_{\rho}f(\omega)={\mathsf{E}}_{\omega^{\prime}\underset{\rho}{\sim}\omega}\Big{[}f(\omega^{\prime})\Big{]},$

for every $f\in L_{2}(\Omega^{R},\mu^{R})$. The following are some well-known
properties of noise operators.

######  Fact 3.2 (Fourier Decay)

Let $f\in L_{2}(\\{0,1\\}^{R},\mu^{R})$ be a function satisfying
$\|f\|_{\infty}\leq 1$. Then for any $\eta\in(0,1)$ and $d\in\mathbbm{N}$ we
have

${\rm Var}\left[f^{>d}\right]\leq(1-\eta)^{d}$

Fourier basis for Biased Hypercube. Our hardness reduction and soundness
analysis will often involve the $p$-biased hypercubes. For any $p\in[0,1]$,
the $p$-biased cube – denoted by $\\{0,1\\}_{p}$ – is the cube equipped with
the ${\sf Bernoulli}(p)$ measure. We use $\phi^{(p)}$ to denote the unique
non-trivial Fourier character corresponding to the $p$-biased cube, where

$\phi^{(p)}(x)\overset{\rm def}{=}\frac{x-p}{\sqrt{p(1-p)}}.$ (7)

The following is well-known, and follows directly using the above definitions.

###### Fact 3.3

For any $p\in[0,1]$, the Fourier expansion of any $f\in
L_{2}(\\{0,1\\}^{R}_{p})$ is unique and can be expressed as

$f(x)=\sum_{S\subseteq[R]}\widehat{f}(S)\phi^{(p)}_{S}(x)=\sum_{S\subseteq[R]}\widehat{f}(S)\prod_{i\in
S}\phi^{(p)}_{i}(x(i)).$

Using the above, we can derive the following corollary.

###### Corollary 3.4

Let $f:\\{0,1\\}^{R}\to\mathbbm{R}$ be a function in
$L_{2}(\\{0,1\\}^{R}_{\mu})$ for some $\mu\in[0,1]$. Then the Fourier
expansion of $f(x)$ is a multilinear polynomial $H$ in the variables
$x(1),\ldots,x(R)$.

  * Proof.

Let $P:\mathbbm{R}^{R}\to\mathbbm{R}$ denote the multilinear polynomial

$P(a)\overset{\rm def}{=}\sum_{S\subseteq[R]}\widehat{f}(S)\prod_{i\in
S}a(i).$

Now from fact 3.3, it follows that there exists a linear transformation
$A:\mathbbm{R}^{R}\to\mathbbm{R}^{R}$ which satisfies the identity

$A\left(x\right)=\left(\phi^{(p)}(x(j))\right)^{R}_{j=[R]}$

Then, $H=P\circ A$ is a multilinear polynomial in $(x(j))^{r}_{j=1}$ which
satisfies the identity:

$H(x)=P\left(\left(\phi^{(p)}(x(j))\right)^{R}_{j=1}\right)=\sum_{S\subseteq[R]}\widehat{f}(S)\prod_{j\in
S}\phi^{(p)}(x(j)).$

$\square$

###  3.2 Ensembles, Polynomials, and Invariance Principle

Let us recall some notation and terminology from [IM12] which is required for
stating its invariance principle. To begin with, an ensemble
$\mathcal{X}_{j}=(\mathcal{X}_{j}[0]\equiv
1,\mathcal{X}_{j}[1],\ldots,\mathcal{X}_{j}[k])$ is just an ordered collection
of (possibly dependent) random variables. An independent sequence of random
variable ensembles
$\mathcal{X}:=(\mathcal{X}_{1},\mathcal{X}_{2},\ldots,\mathcal{X}_{n})$ is a
sequence of individual ensembles such that across $j\in[n]$,
$\mathcal{X}_{1},\ldots,\mathcal{X}_{n}$ are jointly independent. A pair of
independent ensemble sequences
$\mathcal{X}=(\mathcal{X}_{1},\ldots,\mathcal{X}_{n})$ and
$\mathcal{X}^{\prime}=(\mathcal{X}^{\prime}_{1},\ldots,\mathcal{X}^{\prime}_{n})$
are said to have matching covariance structure if for every $j\in[n]$, we have
$|\mathcal{X}_{j}|=|\mathcal{X}^{\prime}_{j}|$ and
${\mathsf{E}}_{\mathcal{X}}[\mathcal{X}_{j}\mathcal{X}^{\top}_{j}]={\mathsf{E}}_{\mathcal{X}^{\prime}}[\mathcal{X}^{\prime}_{j}\mathcal{X}^{\prime\top}_{j}]$.

Multi-linear Polynomial. A multi-index
$\sigma:=(\sigma_{1},\ldots,\sigma_{n})$ is a sequence of non-negative
integers. The degree of $\sigma$ is the number of non-zero entries. Given an
ensemble sequence $\mathcal{X}=(\mathcal{X}_{1},\ldots,\mathcal{X}_{n})$, a
multilinear polynomial $Q$ on $\mathcal{X}$ is a function of the form

$Q(\mathcal{X})=\sum_{\sigma\in\mathbbm{Z}^{n}_{\leq
k}}\widehat{Q}_{\sigma}\prod_{j\in[n]}\mathcal{X}_{j}[\sigma(j)],$

where $\mathbbm{Z}_{\leq k}:=\\{0,1,\ldots,k\\}$ i.e., every monomial contains
exactly one variables from every ensemble in the sequence. The degree of a
monomial corresponding to $\sigma$ is simply $|\sigma|$ i.e., the number of
non-zero entries in $\sigma$. Finally, we use $Q^{\leq d}(\mathcal{X})$ to
denote the truncation of $Q$ to monomials with degree at most $d$. Finally, we
can define the influence of the $j^{th}$-ensemble on $P$ as

${\sf
Inf}_{\mathcal{X}_{j}}\left[P\right]={\mathsf{E}}_{(\mathcal{X}_{j^{\prime}})_{j^{\prime}\neq
j}}\left[{\rm
Var}_{\mathcal{X}_{j}}\left[P(\mathcal{X})\Big{|}\left(\mathcal{X}_{j^{\prime}}\right)_{j^{\prime}\neq
j}\right]\right].$

Now we are ready to state the Invariance principle used in our applications

######  Theorem 3.5 (Theorem 3.6 [IM12])

Let $\mathcal{X}=(\mathcal{X}_{1},\ldots,\mathcal{X}_{n})$ be an independent
sequence of ensembles, such that
$\Pr\left[\mathcal{X}_{j}=x\right]\geq\alpha>0$ for all $j,x$. Fix
$\gamma,\tau\in(0,1)$ and let $Q=(Q_{1},\ldots,Q_{r})$ be a $r$-dimensional
multilinear polynomial on $\mathcal{X}$ such that ${\rm
Var}[Q_{i}(\mathcal{X})]\leq 1$, ${\rm
Var}\left[Q^{>d}_{i}(\mathcal{X})\right]\leq(1-\gamma)^{2d}$ and ${\sf
Inf}_{j}\left[Q^{\leq d}_{i}\right]\leq\tau$, where
$d=\frac{1}{18}\log\frac{1}{\tau}/\log\frac{1}{\alpha}$. Finally, let
$\Psi:\mathbbm{R}^{r}\to\mathbbm{R}$ be Lipschitz continuous with constant
$A$. Then,

$\left|{\mathsf{E}}\left[\Psi(Q(\mathcal{X}))\right]-{\mathsf{E}}\left[\Psi(Q(\mathcal{G}))\right]\right|\leq
C_{r}A\tau^{\frac{\gamma}{18}/\log\frac{1}{\alpha}},$

where $\mathcal{G}$ is an independent sequence of Gaussian ensembles with the
same covariance structure as $\mathcal{X}$, and $C_{r}$ is a constant
depending only on $r$.

###  3.3 Noise Stability Bounds

We shall need the following multi-dimensional version of Borell’s
isoperimetric inequality.

######  Theorem 3.6 (Theorem 1.2 [IM12])

The following holds for any $r\geq 2,d\in\mathbbm{N}$ and $\rho\in[0,1]$. Let
$(X_{1},\ldots,X_{r})$ be a set of jointly distributed Gaussian vector random
variables, such that $X_{i}\sim N(0_{d},I_{d})$ for every $i\in[r]$, and for
any $i\neq j$ we have ${\rm Cov}(X_{i},X_{j})=\rho I_{d}$. Then for any
$A_{1},\ldots,A_{r}\subseteq\mathbbm{R}^{d}$ we have

$\Pr_{X_{1},\ldots,X_{r}}\left[~{}\forall^{r}_{i=1}X_{i}\in
A_{i}\right]\leq\Pr_{X_{1},\ldots,X_{r}}\left[~{}\forall^{r}_{i=1}X_{i}(1)\leq\Phi^{-1}(\mu_{i})\right],$

where for every $i\in[r]$, $\mu_{i}:=\Pr_{X_{i}}\left[X_{i}\in A_{i}\right]$.

Next, we define the notion of sampling correlated Gaussians.

######  Definition 3.7 (Correlated Gaussians)

Fix $R\in\mathbbm{N}$ and $\rho\in[-1,1]$. Then given a Gaussian vector $g\sim
N(0_{R},I_{R})$, a $\rho$-correlated draw of a Gaussian $h$ from $g$, denoted
as $h\underset{\rho}{\sim}g$, is generated using the following process:
independently sample a Gaussian vector $\zeta\sim N(0_{R},I_{R})$, and let
$h=\rho\cdot g+\sqrt{1-\rho^{2}}\cdot\zeta$. It can be verifed that for every
$j\in[R]$,

$(g(j),h(j))\sim N\left(\begin{bmatrix}0\\\
0\end{bmatrix},\begin{bmatrix}1&\rho\\\ \rho&1\end{bmatrix}\right).$

$r$-ary Gaussian Stability. We define the $r$-ary Gaussian stability for
halfspaces with volumes $\delta_{1},\ldots,\delta_{r}$ as

$\Lambda_{\rho}(\delta_{1},\ldots,\delta_{r})\overset{\rm
def}{=}\Pr_{\begin{subarray}{c}g\sim N(0,1)\\\
g_{1},\ldots,g_{r}\underset{\rho}{\sim}g\end{subarray}}\left[~{}\forall_{i\in[r]}~{}g_{i}\leq\Phi^{-1}(\delta_{i})\right],$
(8)

where $\Phi(\cdot)$ is the Gaussian CDF function. We derive the following
elementary corollary which extends the above theorem to the setting of
$[0,1]$-valued functions.

###### Corollary 3.8

The following holds for any $r\geq 2,d\in\mathbbm{N}$ and $\rho\in[0,1]$. Let
$f_{1},\ldots,f_{r}:\mathbbm{R}^{d}\to[0,1]$ be arbitrary functions. Then,

${\mathsf{E}}_{g\sim
N(0,I_{d})}{\mathsf{E}}_{g_{1},\ldots,g_{r}\underset{\rho}{\sim}g}\left[\prod_{j\in[r]}f_{j}(g_{j})\right]\leq\Lambda_{\rho}(\mu_{1},\ldots,\mu_{r}),$
(9)

where $\mu_{i}:={\mathsf{E}}_{g\sim N(0,I_{d})}\left[f_{i}(g)\right]$ for
every $i\in[r]$ .

  * Proof.

Fix a choice of $\mu_{1},\ldots,\mu_{r}$, and consider the set $\mathcal{F}$
of functions $(f_{1},\ldots,f_{r}):\mathbbm{R}^{d}\to[0,1]^{r}$ such that
${\mathsf{E}}_{g\sim N(0,I_{d})}\left[f_{j}(g)\right]=\mu_{j}$ for every
$j\in[r]$. Then observe that the set of functions is convex. Furthermore,
fixing for any $j\in[r]$, and choices of functions
$\\{f_{j^{\prime}}\\}_{j^{\prime}\neq j}$, the mapping

$f_{j}\mapsto{\mathsf{E}}_{g_{1},\ldots,g_{r}}\left[\prod_{j^{\prime}\in[r]}f_{j^{\prime}}(g_{j^{\prime}})\right]$

is linear in $f_{j}$, and hence, it is maximized in $\mathcal{F}$ for some
choice of $f_{j}:\mathbbm{R}^{d}\to\\{0,1\\}$. Therefore, it follows that it
suffices to prove the inequality for $\\{0,1\\}$-valued choices of
$f_{1},\ldots,f_{r}$. To that end, fix such a choice of
$f_{1},\ldots,f_{r}:\mathbbm{R}^{d}\to\\{0,1\\}$, and let
$\mu_{j}:={\mathsf{E}}_{g}\left[f_{j}(g)\right]$, and $A_{j}={\rm
supp}(S_{j})$. Then,

$\displaystyle{\mathsf{E}}_{g\sim
N(0,1)^{r}}{\mathsf{E}}_{g_{1},\ldots,g_{r}\underset{\rho}{\sim}g}\left[\prod_{j\in[r]}f_{j}(g_{j})\right]$
$\displaystyle=\Pr_{\begin{subarray}{c}g\sim N(0,1)^{r}\\\
g_{1},\ldots,g_{r}\underset{\rho}{\sim}g\end{subarray}}\left[\mathop{~{}\forall}^{r}_{j=1}~{}g_{j}\in
A_{j}\right]$ $\displaystyle\leq\Pr_{\begin{subarray}{c}g\sim N(0,1)\\\
g_{1},\ldots,g_{r}\underset{\rho}{\sim}g\end{subarray}}\left[\mathop{~{}\forall}^{r}_{j=1}~{}g_{j}\leq\Phi^{-1}(\mu_{j})\right],$

where the last inequality follows from applying Theorem 3.6. $\square$

###  3.4 Small-Set Expansion Hypothesis

Given a $d$-regular graph $G=(V,E)$, and a subset $S\subseteq V$ of size at
most $|V|/2$, the expansion of $S$ in $G$ – denoted by $\phi_{G}(S)$ – is
defined as follows:

$\phi_{G}(S)\overset{\rm def}{=}\Pr_{(i,j)\sim E|i\in S}\left[j\in S\right].$

Our reductions are from the SmallSetExpansion problem which we define formally
below:

######  Definition 3.9 (SmallSetExpansion)

For any $\varepsilon,\delta\in(0,1)$ and $M\in\mathbbm{N}$, an instance of
$(\varepsilon,\delta,M)$-SmallSetExpansion problem is characterized by a
regular graph $G=(V,E)$. The objective here is to distinguish between the
following cases:

  * •

YES Case. There exists a set $S$ of volume $\delta$ such that
$\phi_{G}(S)\leq\varepsilon$.

  * •

NO Case. For every $S\subseteq V$ such that ${\sf
Vol}(S)\in\left[\frac{\delta}{M},M\delta\right]$ we have $\phi_{G}(S)\geq
1-\varepsilon$.

Our reduction uses the hard instances of SmallSetExpansion given by the
following theorem as the starting point.

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

There exists a constant $\varepsilon_{0}\in(0,1)$, such that the following
holds. For every $\varepsilon\in(0,\varepsilon_{0})$, and $M\leq
1/\sqrt{\varepsilon}$ there exists $\delta=\delta(\varepsilon,M)$ such that
$(\varepsilon,\delta,M)$-SmallSetExpansion is $\mathsf{NP}$-hard.

###  3.5 Lasserre Hierarchy, Pseudo-variables, and Vector Solution

The Lasserre (aka the Sum-of-Squares) hierarchy is a sequence of
strengthenings of a basic SDP relaxation. The $\ell$-round Lasserre relaxation
introduces local distributions on subsets of size at most $\ell$ that are
locally consistent, and whose $\ell^{th}$-order moment matrix is PSD. In
particular, the $\ell$-round Lasserre lifting of a basic SDP in Figure 1
optimizes over the space of “collections” of local distributions
$\theta:=\\{\theta_{S}\\}_{|S|\leq\ell}$, which for any subset $S\subseteq
V_{\rm gap}$ of size at most $\ell$, $\theta_{S}$ defines a local distribution
over partial assignments to vertices in $S$. It then enforces local
consistency constraints that ensure that for any pair of sets $A,B$, the
corresponding distributions $\theta_{A}$ and $\theta_{B}$ are consistent on
the support of the intersection $A\cap B$. In particular, this allows us to
define pseudo-variables $X_{1},\ldots,X_{n}$ which are not necessarily jointly
distributed but are locally consistent i.e., for every subset $S$ of size at
most $\ell$, the corresponding collection of variables $X_{S}=(X_{i})_{i\in
S}$ is distributed as $\theta_{S}$. Finally, it ensures that $\ell^{th}$-order
pseudo-covariance matrix is PSD. We describe the $\ell$-round Lasserre
relaxation in the figure below:

Maximize $\displaystyle{\mathsf{E}}_{e\sim
E}\Pr_{X_{e}\sim\theta_{e}}\Big{[}\psi(X_{e})=1\Big{]}$ (10) Subject to
$\displaystyle{\mathsf{E}}_{i\sim V_{\rm
gap}}\Pr_{X_{i}\sim\theta_{\\{}i\\}}\left[X_{i}=1\right]=\mu$ (11)
$\displaystyle\Pr_{\theta_{A}}\left[X_{A\cap
B}=\omega\right]=\Pr_{\theta_{B}}\left[X_{A\cap B}=\omega\right]$
$\displaystyle~{}\forall~{}|A\cup B|\leq\ell,\omega\in\\{0,1\\}^{A\cap B}$
(12) $\displaystyle M_{\ell}(\theta)\succeq 0,$ (13) Figure 6: Lasserre
Relaxation ${\sf Lass}_{\mu,\ell}(G_{\rm gap})$

In the above, $M_{\ell}(\theta)$ is the
${[n]\choose{\ell/2}}\times{[n]\choose{\ell/2}}$-size matrix whose rows and
columns are indexed by subsets of size at most $\ell/2$, and for any such pair
of row-column subset index $A,B$, the corresponding entry is defined as
$M_{\ell}(\theta)[A,B]={\mathsf{E}}_{\theta}\left[\prod_{i\in A\cup
B}X_{i}\right]$ – note that the RHS is well-defined due to the local
consistency constraints.

Covariance, Correlation. We will refer a ${\sf Lass}_{\mu,\ell}(G_{\rm gap})$
feasible solution $\theta=\\{\theta_{S}\\}_{|S|\leq\ell}$ as a degree-$\ell$
pseudo-distribution. The $\ell$-wise local consistency allows us to
consistently define various quantities involving subsets of at most
$\ell$-variables. In particular, for any pair of pseudo-variables
$X_{i},X_{j}$, we can define the covariance

${\sf
Cov}_{\theta}(X_{i},X_{j})={\mathsf{E}}_{\theta}\left[X_{i}X_{j}\right]-{\mathsf{E}}_{\theta}\left[X_{i}\right]{\mathsf{E}}_{\theta}\left[X_{j}\right].$

Analogously, we can also define the standard deviation of variable $X_{i}$ as
${\sf
stdev}_{\theta}(X_{i})=({\mathsf{E}}_{\theta}X^{2}_{i}-({\mathsf{E}}_{\theta}X_{i})^{2})^{1/2}$,
and the correlation between a pair of variables $X_{i},X_{j}$ is then defined
as

${\sf Corr}_{\theta}(X_{i},X_{j})=\frac{{\sf Cov}_{\theta}(X_{i},X_{j})}{{\sf
stdev}_{\theta}(X_{i})\cdot{\sf stdev}_{\theta}(X_{j})}.$

Degree-$2$ Solution. Given a degree-$\ell$ pseudo-distribution, one can
identify vectors $\\{u_{\emptyset}\\}\cup\\{u_{i}\\}_{i\in V_{\rm gap}}$ from
the Cholesky decomposition of the second order covariance matrix
$M_{2}(\theta)$. The following proposition lists some easy to verify
properties of these vectors.

###### Proposition 3.11

Let $\\{u_{\emptyset}\\}\cup\\{u_{i}\\}_{i\in V_{\rm gap}}$ be the vector
solution as defined above. For every $i\in V_{\rm gap}$ let
$u_{i}=\mu_{i}u_{\emptyset}+w_{i}$, where $w_{i}\perp u_{i}$. Then the
following properties hold:

  * •

For any $i\in V_{\rm gap}$,
$\mu_{i}=\Pr_{X_{i}\sim\theta}\left[X_{i}=1\right]$.

  * •

For any $i\in V_{\rm gap}$, $\|w_{i}\|={\sf stdev}_{\theta}(X_{i})$.

  * •

For any $i,j\in V_{\rm gap}$, $\langle w_{i},w_{j}\rangle={\sf
Cov}_{\theta}(X_{i},X_{j})$

  * •

For any $i,j\in V_{\rm gap}$. $\langle
u_{i},u_{j}\rangle=\Pr_{\theta}\left[X_{i}=1,X_{j}=1\right]$.

##  4 Small Average-Correlation via Pre-processing

Let $(G_{\rm gap},\theta)$ be a $(\ell,\mu,c,s,\gamma)$-gap instance as in
Definition 1.1 with $G_{\rm gap}=(V_{\rm gap},E_{\rm gap},\tilde{w},w)$ where
$\tilde{w}:V_{\rm gap}\to\mathbbm{R}_{\geq 0}$ and $w:E_{\rm
gap}\to\mathbbm{R}_{\geq 0}$ define the vertex and edge weights, and $\theta$
is a feasible solution to ${\sf Lass}_{\mu,\ell}\left(G_{\rm gap}\right)$
i.e., the $\mu$-constrained $\ell$-round Lasserre relaxation described in
Figure 7.

Maximize $\displaystyle{\mathsf{E}}_{e\sim
w}\Pr_{X_{e}\sim\theta_{e}}\left[\psi(X_{e})=1\right]$ Subject to
$\displaystyle{\mathsf{E}}_{i\sim G_{\rm
gap}}\Pr_{X_{i}\sim\theta_{i}}\left[X_{i}=1\right]=\mu$ $\displaystyle\langle
u_{A,\alpha},u_{B,\beta}\rangle=\Pr_{\theta_{A\cup
B}}\left[X_{A}=\alpha,X_{B}=\beta\right]$
$\displaystyle~{}\forall~{}A,B\subseteq[\ell]\textnormal{such that}$
$\displaystyle|A|,|B|\leq\ell/2,$
$\displaystyle\alpha\in\\{0,1\\}^{A},\beta\in\\{0,1\\}^{B}$ Figure 7: ${\sf
Lass}_{\mu,\ell}(G_{\rm gap})$

We introduce a definition that specifies some useful properties of a feasible
pseudo-distribution.

######  Definition 4.1 (Smooth and Independent Pseudo-distributions)

Let $\theta$ be a feasible solution ${\sf Lass}_{\mu,\ell}(G_{\rm gap})$. We
will say that $\theta$ is $\gamma$-smooth if for every edge $e$, and every
$\alpha\in\\{0,1\\}^{e}$, we have
$\Pr_{X_{e}\sim\theta_{e}}\left[X_{e}=\alpha\right]\geq\gamma$. Furthermore,
we will say that $\theta$ is $\gamma$-independent if

${\mathsf{E}}_{i,j\sim G_{\rm gap}}\left[|{\sf
Corr}_{\theta}(X_{i},X_{j})|\right]\leq\gamma,$

where ${\rm Corr}_{\theta}(X_{i},X_{j})$ is the correlation of the variables
corresponding to vertices $i,j\in V_{\rm gap}$ under the local distribution
$\theta$.

The following shows that given a $\ell$-round feasible Lasserre solution, we
can construct a $\ell-O(1/\gamma^{C})$-round Lasserre solution that is
$(\gamma\mu)^{r}$ smooth and $\gamma^{2}$ independent with almost matching
completeness.

###### Lemma 4.2

Let $\theta:=\\{\theta_{A}\\}_{|A|\leq\ell}$ be a feasible solution to ${\sf
Lass}_{\mu,\ell}(G_{\rm gap})$. Then there exists $t=t(\gamma)$ such that we
can construct $\theta^{\prime}=\\{\theta^{\prime}_{A}\\}_{|A|\leq\ell-t}$
which is a feasible solution to ${\sf Lass}_{\mu,\ell-t}(G_{\rm gap})$
satisfying the following properties:

  * •

Smoothness. There exists a subset of $S$ of size at most $O(1/\gamma^{4})$
such that for every subset $A\subseteq V_{\rm gap}\setminus S$ of size at most
$\ell-t$, and every assignment $\alpha_{A}\in\\{0,1\\}^{A}$ corresponding to
the variables in $A$ we have

$\Pr_{X_{A}\sim\theta^{\prime}_{A}}\left[X_{A}=\alpha_{A}\right]\geq(\gamma\mu)^{|A|}.$

  * •

Small Average Correlation.

${\mathsf{E}}_{i\sim G_{\rm gap}}\left[|{\rm
Corr}_{\theta^{\prime}}(X_{i},X_{j})|\right]\leq\gamma^{2}.$

  * •

Almost matching completeness.

${\mathsf{E}}_{e\sim E_{\rm
gap}}\Pr_{X_{e}\sim\theta^{\prime}_{e}}\left[\psi(X_{e})=1\right]\geq
c-2\gamma r,$

where $c$ denotes the SDP objective value w.r.t. $\theta$.

We shall use the following result from [RT12] to derive the above.

######  Theorem 4.3 ([RT12])

Let $\theta$ be a ${\sf Lass}_{\mu,\ell}(G_{\rm gap})$-feasible solution. Fix
$\gamma>0$. Then there exists a subset $S\subseteq V_{\rm gap}$ of size at
most $O(1/\gamma^{8})$, and a partial assignment $\alpha_{S}\in\\{0,1\\}^{S}$
to the variables in $S$ such that
$\tilde{\theta}=\theta|X_{S}\leftarrow\alpha$ satisfies

${\mathsf{E}}_{i,j\sim V_{\rm gap}}\left[|{\rm
Cov}_{\tilde{\theta}}(X_{i},X_{j})|\right]\leq\gamma^{4}$ (14)

and

${\mathsf{E}}_{e\sim E_{\rm
gap}}\Pr_{X_{e}\sim\tilde{\theta}_{e}}\left[\psi(X_{e})=1\right]\geq c-\gamma$
(15)

Now we prove the above lemma.

  * Proof.

We construct the new pseudo-distribution by first applying a natural
smoothening operator, and then apply Theorem 4.3 to find a conditioning under
which the resultant pseudo-distribution will satisfy the properties claimed in
the lemma.

Step 1. Given $\theta$, construct a ${\sf Lass}_{\mu,\ell}(G_{\rm gap})$
feasible solution $\hat{\theta}$ as follows. For every $A\subseteq V_{\rm
gap}$ of size at most $\ell$, we define the local distribution $\hat{\theta}$
as follows.

    * –

Sample $X_{A}\sim\theta_{A}$.

    * –

For every $i\in A$, do the following independently: w.p $1-\gamma$, set
$\hat{X}_{i}=X_{i}$, and w.p. $\gamma$, sample
$\hat{X}_{i}\sim\\{0,1\\}_{\mu}$.

Note that the resulting distribution is $\ell$-Lasserre feasible (Claim B.3).
Furthermore,

${\mathsf{E}}_{i\sim G_{\rm
gap}}\Pr_{\hat{X}_{i}\sim\hat{\theta}}\left[\hat{X}_{i}=1\right]=(1-\gamma){\mathsf{E}}_{i\sim
G_{\rm gap}}\Pr_{{X}_{i}\sim\theta}\left[{X}_{i}=1\right]+\gamma\mu=\mu.$ (16)

Finally, we have that

${\mathsf{E}}_{e\sim E_{\rm
gap}}\Pr_{\hat{X}_{e}\sim\hat{\theta_{e}}}\left[\psi(\hat{X}_{e})=1\right]\geq(1-\gamma)^{r}{\mathsf{E}}_{e\sim
E_{\rm gap}}\Pr_{{X}_{e}\sim{\theta_{e}}}\left[\psi({X}_{e})=1\right]\geq
c-\gamma r.$ (17)

Step 2. Apply Theorem 4.3 on $\hat{\theta}$ to find a ${\sf
Lass}_{\mu,\ell-t}(G_{\rm gap})$-feasible solution $\tilde{\theta}$ that
satisfies (14) and (15).

Analysis. Let $X_{S}\leftarrow\alpha_{S}$ be the conditioning identified by
Theorem 4.3 in step $2$. For the smoothness property, we observe that for any
subset $A\subseteq V_{\rm gap}\setminus S$, using the definition on the
conditioning we have

$\Pr_{\tilde{X}_{A}\sim\tilde{\theta}_{A}}\Big{[}\tilde{X}_{A}=\alpha_{A}\Big{]}=\frac{\Pr_{\hat{X}_{A\cup
S}\sim\hat{\theta}_{A\cup S}}\Big{[}\hat{X}_{A\cup S}=\alpha_{A\cup
S}\Big{]}}{\Pr_{\hat{X}_{S}\sim\hat{\theta}_{S}}\Big{[}\hat{X}_{S}=\alpha_{S}\Big{]}}.$
(18)

Further, note that for sampling $\hat{X}_{A\cup S}\sim\hat{\theta}_{A\cup S}$,
fixing $X_{A\cup S}\sim\theta_{A\cup S}$, we have that $\hat{X}_{A}$ and
$\hat{X}_{S}$ are independent. Using this observation, we can further simplify
and bound the above numerator as

$\displaystyle\Pr_{\hat{X}_{A\cup S}\sim\hat{\theta}_{A\cup
S}}\Big{[}\hat{X}_{A\cup S}=\alpha_{A\cup S}\Big{]}$
$\displaystyle={\mathsf{E}}_{\hat{X}_{A\cup S}\sim\hat{\theta}_{A\cup
S}}\Pr_{\hat{X}_{S}}\left[\hat{X}_{S}=\alpha_{S}\Big{|}X_{S}\right]\Pr_{\hat{X}_{A}}\left[\hat{X}_{A}=\alpha_{A}\Big{|}X_{A}\right]$
$\displaystyle\geq(\gamma\mu)^{|A|}{\mathsf{E}}_{\hat{X}_{A\cup
S}\sim\theta_{A\cup
S}}\Pr_{\hat{X}_{S}}\left[\tilde{X}_{S}=\alpha_{S}\Big{|}X_{S}\right]$
$\displaystyle=(\gamma\mu)^{|A|}\Pr_{\hat{X}_{S}\sim\hat{S}}\left[\hat{X}_{S}=\alpha_{S}\right],$

where in the first step, we use that in the construction of $\hat{\theta}$,
fixing $X_{S}$, $\hat{X}_{S}$ is sampled by re-randomizing each coordinate of
$S$ independently. This combined with (18) gives us that

$\Pr_{\tilde{X}_{A}\sim\tilde{\theta}_{A}}\Big{[}\tilde{X}_{A}=\alpha_{A}\Big{]}\geq(\gamma\mu)^{|A|}$

for every $A\subseteq V_{\rm gap}\setminus S$ of size at most $(\ell-t)$ –
this establishes the smoothness property. The almost matching completeness
property follows from (17) and (15).

To finish the proof, we establish the small-average-correlation property.
Towards that, denote $n=|V_{\rm gap}|$ and let $i\sim G_{\rm gap}\setminus S$
denote a draw of a random vertex conditioned on $i\notin S$. Then note that
since $|V_{\rm gap}|^{-1/C}\leq\gamma$ for a large constant $C$, we have

$\left|{\mathsf{E}}_{i,j\sim G_{\rm gap}\setminus S}|{\rm
Cov}_{\tilde{\theta}}(X_{i},X_{j})|-{\mathsf{E}}_{i,j\sim G_{\rm gap}}|{\rm
Cov}_{\tilde{\theta}}(X_{i},X_{j})|\right|\leq o_{n}(1)$

since $S$ of size at most $1/\gamma^{8}$. Note that for any $i\in V_{\rm
gap}\setminus S$, we have
$\Pr_{\tilde{X}_{i}}\left[\tilde{X}_{i}=1\right]\in[\gamma\mu,1-\gamma\mu]$
and hence ${\sf stdev}(\tilde{X}_{i})\geq\sqrt{\gamma\mu/2}$. Hence,

$\displaystyle{\mathsf{E}}_{i,j\sim G_{\rm gap}}\left[|{\sf
Corr}_{\tilde{\theta}}(\tilde{X}_{i},\tilde{X}_{j})|\right]$
$\displaystyle\leq{\mathsf{E}}_{i,j\sim G_{\rm gap}\setminus S}\left[|{\sf
Corr}_{\tilde{\theta}}(\tilde{X}_{i},\tilde{X}_{j})|\right]+o_{n}(1)$
$\displaystyle={\mathsf{E}}_{i,j\sim G_{\rm gap}\setminus S}\left[\frac{|{\sf
Cov}_{\tilde{\theta}}(\tilde{X}_{i},\tilde{X}_{j})|}{{\sf
stdev}_{\tilde{\theta}}(X_{i})\cdot{\sf
stdev}_{\tilde{\theta}}(X_{j})}\right]+o_{n}(1)$
$\displaystyle{\leq}{\mathsf{E}}_{i,j\sim G_{\rm gap}\setminus
S}\left[\frac{|{\sf
Cov}_{\tilde{\theta}}(\tilde{X}_{i},\tilde{X}_{j})|}{\sqrt{\gamma\mu/2}\cdot\sqrt{\gamma\mu/2}}\right]+o_{n}(1)$
$\displaystyle=\frac{2}{\gamma\mu}{\mathsf{E}}_{i,j\sim G_{\rm gap}\setminus
S}\left[|{\sf Cov}_{\tilde{\theta}}(X_{i},X_{j})|\right]+o_{n}(1)$
$\displaystyle=\frac{2}{\gamma\mu}{\mathsf{E}}_{i,j\sim G_{\rm gap}\setminus
S}\left[|{\sf Cov}_{\tilde{\theta}}(X_{i},X_{j})|\right]+o_{n}(1)$
$\displaystyle\leq\frac{1}{\gamma\mu}{\mathsf{E}}_{i,j\sim G_{\rm
gap}}\left[|{\sf
Cov}_{\tilde{\theta}}(X_{i},X_{j})|\right]+o_{n}(\gamma^{-2}\mu^{-2})$
$\displaystyle\leq\gamma^{2}.$

$\square$

##  5 The Reduction

Let $(G_{\rm gap},\theta^{\prime})$ be a $(c,s,\mu,\ell,\gamma)$-gap instance
as in Definition 1.1. Then using Lemma 4.2 on $(G_{\rm gap},\theta^{\prime})$,
we obtain a $\gamma^{2}$-independent $(c-O(r\gamma),s,\mu,\ell^{\prime})$-gap
instance $(G_{\rm gap},\theta)$ such that $\theta$ satisfies conditions
$1$-$3$ from Lemma 4.2.

Additional Noise Operators. We introduce some additional noise operators that
will be used in the construction of the reduction.

######  Definition 5.1 (Noise Random Walk Operator)

Given a regular graph $G=(V,E)$, for any $\eta\in(0,1)$, the $\eta$-noisy
random walk operator on $G$ – denoted by $G_{\eta}$ – is a stochastic operator
on $L_{2}(V)$ which is defined as follows. For any $A\in V$, we sample $B\sim
G_{\eta}(A)$ as follows:

  * •

W.p. $(1-\eta)$, sample $B$ as a uniformly random neighbor of $A$.

  * •

W.p. $\eta$, sample $B$ uniformly from $V$.

######  Definition 5.2 ($R$-dimensional noise operators with Leakage)

Given $z\in\\{\bot,\top\\}^{R}$, a regular graph $G=(V,E)$, and $\mu\in[0,1]$,
the operator $M^{(\mu)}_{z}$ is the following stochastic operator on
$L_{2}(V^{R}\otimes\\{0,1\\}^{R}_{\mu})$. Given $(A,x)\in
V^{R}\times\\{0,1\\}^{R}$, we sample $(A^{\prime},x^{\prime})\sim
M^{(\mu)}_{z}(A,x)$ by doing the following independently for every $i\in[R]$:

  * •

If $z(i)=\top$, then set $(A^{\prime}(i),x^{\prime}(i))=(A(i),x(i))$.

  * •

If $z(i)=\bot$, then sample $A^{\prime}(i)\sim V$ and
$x^{\prime}(i)\sim\\{0,1\\}_{\mu}$ independently.

###  5.1 Test Distribution

Given the gap instance $(G_{\rm gap},\theta)$ from above, we describe our
reduction as a dictatorship test in the following figure (Figure 8).

Let $G=(V,E)$ be a $(\varepsilon,\delta,M)$-SSE instance from Conjecture 3.10
where $\varepsilon,M$ are set later.
Let $\theta:=\\{\theta_{S}\\}_{|S|\leq\ell^{\prime}}$ be the corresponding
$\gamma^{2}$-independent $(\gamma\mu)^{r}$-smooth pseudo-distribution from
Lemma 4.2.
For every $i\in V_{\rm gap}$, let $\mu_{i}:=\Pr_{\theta}\left[X_{i}=1\right]$
be the probability of the $i^{th}$ variable being set to $1$ under $\theta$.
Set parameters $\beta:=\mu^{4r}|V_{\rm gap}|^{-4}$,
$\rho:=1/(4r^{2}\log(1/\mu))$ and $R:=1/(r\beta\delta)$.

Constraint Hypergraph $\mathcal{H}$: The vertex set of the hypergraph is
$V^{R}\times\\{0,1\\}^{R}\times\\{\bot,\top\\}^{R}$. For any $(A,x,z)\in
V^{R}\times\\{0,1\\}^{R}\times\\{\bot,\top\\}^{R}$, the weight of the vertex
$(A,x,z)$ is set as $\tilde{w}_{\mathcal{H}}(A,x,z)={\mathsf{E}}_{i\sim G_{\rm
gap}}\Pr_{A^{\prime}\sim
V^{R},x^{\prime}\sim\\{0,1\\}^{R}_{\mu_{i}},z^{\prime}\sim\\{\bot,\top\\}^{R}_{\beta}}\left[(A^{\prime},x^{\prime},z^{\prime})=(A,x,z)\right].$
The weights of the ordered edges in hypergraph $\mathcal{H}$ are defined
according to the following distribution:
1. Sample hyperedge $e=(i_{1},\ldots,i_{r})\sim E_{\rm gap}$, and let $\theta_{e}$ be the local distribution on edge $e$.
2. Sample $A\sim V^{R}$ and $B_{i_{1}},\ldots,B_{i_{r}}\sim G^{\otimes R}_{\eta}(A)$.
3. Sample $z=(z(j))_{j\in[R]}\sim\\{\bot,\top\\}^{R}_{\beta}$ and $\xi_{e}=(\xi_{e}(j))_{j\in[R]}\sim\\{0,1\\}^{R}_{\rho^{2}}$ independently.
4. For every $j\in[R]$ do the following independently: sample $(x_{i}(j),z_{i}(j))_{i\in e}$ as follows.
a. Sample $(x_{i_{1}}(j),x_{i_{2}}(j),\ldots,x_{i_{r}}(j))\sim\theta_{e}$.
b. If $\xi_{e}(j)=1$, set $z_{i}(j)=z(j)$ for every $i\in e$. If
$\xi_{e}(j)=0$, then for every $i\in e$ sample
$z_{i}(j)\sim\\{\bot,\top\\}_{\beta}$ independently.
5. For every $i\in e$, re-randomize $\tilde{x}_{i}\sim\mathcal{T}^{(\mu_{i})}_{1-\eta}(x_{i})$ and $z^{\prime}_{i}\sim\mathcal{T}^{(\beta)}_{1-\eta}(z_{i})$.
6. For every $i\in e$, sample $(B^{\prime}_{i},x^{\prime}_{i})\sim M^{(\mu_{i})}_{z^{\prime}_{i}}(B_{i},\tilde{x}_{i})$.
7. Sample permutations $\pi_{i_{1}},\ldots,\pi_{i_{r}}\sim\mathbbm{S}_{R}$.
8. Output ordered constraint hyperedge $\Big{\\{}\pi_{i_{1}}(B^{\prime}_{i_{1}},x^{\prime}_{i_{1}},z^{\prime}_{i_{1}}),\pi_{i_{2}}(B^{\prime}_{i_{2}},x^{\prime}_{i_{2}},z^{\prime}_{i_{2}}),\ldots,\pi_{i_{r}}(B^{\prime}_{i_{r}},x^{\prime}_{i_{r}},z^{\prime}_{i_{r}})\Big{\\}}$ Figure 8: SSEH to $\mu$-Constrained CSP Reduction

We instantiate the various parameters used in the above reduction and its
analysis:

  * •

$\beta=\mu^{4r}/|V_{\rm gap}|^{4}$.

  * •

$R=1/(r\beta\delta)$.

  * •

$\nu=s/10^{r}$.

  * •

$\gamma=2^{-10R}\nu^{2}$.

  * •

$\tau=(s\mu/r)^{100r^{2}\log(1/\gamma)/\eta\beta}$

  * •

$\eta=\min\\{\beta^{2}/r,\nu\\}$.

  * •

$\varepsilon=\frac{\beta^{2}\nu^{4}\eta^{4}\tau^{6}}{2^{24}r^{4}}$.

  * •

$M=1/\sqrt{\varepsilon}=\frac{2^{12}r^{2}}{\beta\nu^{2}\eta^{2}\tau^{3}}$.

  * •

$\kappa=\beta/\log(1/\gamma)$.

In the following sections, we analyze the completeness and soundness
guarantees of the above reduction.

##  6 Completeness

Suppose $G=(V,E)$ is a YES instance. Then from Definition 3.9, there exists a
subset $S\subseteq V$ satisfying ${\sf Vol}(S)=\delta$ and
$\phi_{G}(S)\leq\varepsilon$. We begin by defining a map
$i^{*}:V^{R}\times\\{\bot,\top\\}^{R}\to[R]$ using this choice of $S$, which
will be used to identify the dictator labeling. For every $(A,z)\in
V^{R}\times\\{\bot,\top\\}^{R}$, define the set

$\Pi(A,z):=\\{i\in[R]~{}|~{}(A(i),z(i))\in S\times\\{\top\\}\\}.$

Then we use the following process to construct the map $i^{*}$:

  * I

Firstly, consider the choices of $(A,z)\in
V^{R}\times\\{\bot,\top\\}^{R}_{\beta}$ satisfying $|\Pi(A,z)|=1$. For any
such $(A,z)$, we let $i^{*}(A,z)=i$ where $i$ is the unique element contained
in $\Pi(A,z)$. Note that by construction, we have
$i^{*}(\pi(A,z))=\pi(i^{*}(A,z))$, for every permutation $\pi$, for every
choice of $(A,z)$ satisfying $|\Pi(A,z)|=1$.

  * II

For the remaining choices of $(A,z)$ (i.e., $|\Pi(A,z)|\neq 1$), we assign
$i^{*}$ using the following process:

    * –

While there exists $(A,z)$ such $i^{*}(A,z)$ is unassigned, do the next step.

    * –

Pick any $(A,z)$ such that $i^{*}(A,z)$ is unassigned, and assign
$i^{*}(A,z)=1$. Furthermore, assign $i^{*}(\pi(A,z))=\pi(1)$ for every non-
identity permutation $\pi$.

In other words, we fix $i^{*}(A,z)$ for a given unassigned $(A,z)$ pair, and
then use that to determine the indices for the remaining pairs in the orbit of
$(A,z)$. Note that this construction ensures that
$i^{*}(\pi(A,z))=\pi(i^{*}(A,z))$ holds for every permutation $\pi$, for all
the pairs assigned in II.

Then for every $(A,z)\in V^{R}\times\\{\bot,\top\\}^{R}$, we assign the
dictator function $f_{A,z}:=\chi_{i^{*}(A,z)}$ i.e.,

$f_{A,z}(x)=x(i^{*}(A,z))\qquad\qquad~{}\forall~{}x\in\\{0,1\\}^{R}$

Finally, the full assignment for the instance
$f:V^{R}\times\\{0,1\\}^{R}\times\\{\bot,\top\\}^{R}\to\\{0,1\\}$ is defined
as $f(A,x,z):=f_{A,z}(x)=x(i^{*}(A,z))$, for every $(A,x,z)$.

###### Observation 6.1

By construction, the above assignment satisfies the property
$f(\pi(A,x,z))=f(A,x,z)$ for every permutation $\pi$ and every choice of
$(A,x,z)$.

Analysis of assignment. Now we analyze the assignment $f$. To begin with,
observe that the relative weight of the set indicated by $f$ is

$\displaystyle{\mathsf{E}}_{(A,x,z)\sim\mathcal{H}}\left[f(A,x,z)\right]$
$\displaystyle={\mathsf{E}}_{i\sim G_{\rm gap}}{\mathsf{E}}_{(A,z)\sim
V^{R}\times\\{\bot,\top\\}^{R}_{\beta}}{\mathsf{E}}_{x\sim\\{0,1\\}^{R}_{\mu_{i}}}\left[f(A,x,z)\right]$
$\displaystyle={\mathsf{E}}_{i\sim G_{\rm gap}}{\mathsf{E}}_{(A,z)\sim
V^{R}\times\\{\bot,\top\\}^{R}_{\beta}}{\mathsf{E}}_{x\sim\\{0,1\\}^{R}_{\mu_{i}}}\left[x(i^{*}(A,z))\right]$
$\displaystyle={\mathsf{E}}_{i\sim G_{\rm gap}}{\mathsf{E}}_{(A,z)\sim
V^{R}\times\\{\bot,\top\\}^{R}_{\beta}}\left[\mu_{i}\right]$
$\displaystyle=\mu,$

i.e., $f$ is a feasible assignment for the instance $\mathcal{H}$. Next, we
shall bound the weight of constraints satisfied by $f$. Towards that, we shall
need the following key lemma.

###### Lemma 6.2

For any fixed edge $e=(j_{1},\ldots,j_{r})\in E_{\rm gap}$, let
$p_{e}:=\Pr_{X_{e}\sim\theta_{e}}\left[\psi(X_{e})=1\right]$ denote the
probability of local distribution $\theta_{e}$ satisfying $e$. Then, under the
test distribution for the fixing of $e$ we have

$\Pr_{(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})_{j\in
e}}\left[\left(f(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})\right)_{j\in
e}\in\psi^{-1}(1)\right]\gtrsim\rho^{2}\cdot p_{e}-O(r\eta),$ (19)

where for a realization of
$(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})_{j\in e}$,
$\left(f(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})\right)_{j\in e}$
denotes the $r$-ary ordered tuple

$(f(B^{\prime}_{j_{1}},x^{\prime}_{j_{1}},z^{\prime}_{j_{1}}),f(B^{\prime}_{j_{2}},x^{\prime}_{j_{2}},z^{\prime}_{j_{2}}),\ldots,f(B^{\prime}_{j_{r}},x^{\prime}_{j_{r}},z^{\prime}_{j_{r}})).$

We defer the proof of Lemma 6.2 for now and continue with the completeness
analysis. We can bound the total weight of constraints satisfied by the
assignment $f$ as

$\displaystyle{\mathsf{E}}_{e\sim E_{\rm
gap}}\Pr_{(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})_{j\in
e}}\Pr_{\\{\pi_{j}\\}_{j\in
e}}\left[\left(f\Big{(}\pi_{j}(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})\Big{)}\right)_{j\in
e}\in\psi^{-1}(1)\right]$ $\displaystyle={\mathsf{E}}_{e\sim E_{\rm
gap}}\Pr_{(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})_{j\in
e}}\left[\left(f(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})\right)_{j\in
e}\in\psi^{-1}(1)\right]$ (Using Observation 6.1)
$\displaystyle\gtrsim{\mathsf{E}}_{e\sim E_{\rm
gap}}\left[\frac{\rho^{2}}{r}\cdot p_{e}-O(r\eta)\right]$ (Using Lemma 6.2)
$\displaystyle={\mathsf{E}}_{e\sim E_{\rm gap}}\big{[}\frac{\rho^{2}}{r}\cdot
p_{e}\big{]}-O(r\eta)$ $\displaystyle=\frac{\rho^{2}}{r}{\mathsf{E}}_{e\sim
E_{\rm gap}}\Pr_{X_{e}\sim\theta_{e}}\left[\psi(X_{e})=1\right]-O(r\eta)$
(Using definition of $p_{e}$) $\displaystyle\geq\frac{\rho^{2}}{r}\cdot
c-O(r\eta),$

where the last step uses the completeness value of the gap instance $(G_{\rm
gap},\theta)$.

###  6.1 Proof of Lemma 6.2

The proof of the above lemma follows along the lines of the completeness
analysis of D$k$SH (Section $9.2$) from [GL22b]. Without loss of generality,
assume $e=[r]$. We introduce some additional notations and definitions that
are used in the proof. Define the set $V_{\rm good}\subseteq
V^{R}\times\\{\bot,\top\\}^{R}$ as

$V_{\rm good}:=\Big{\\{}(\hat{A},\hat{z})\in
V^{R}\times\\{\bot,\top\\}^{R}~{}\Big{|}~{}|\Pi(\hat{A},\hat{z})|=1\Big{\\}}.$

In other words, $V_{\rm good}$ is the set of $(A,z)$ pairs for which
$i^{*}(A,z)$ was assigned in Step I in the definition of $i^{*}$. The
following useful observation follows directly from the definition.

###### Observation 6.3

Suppose $(\hat{A},\hat{z})\in V_{\rm good}$, and let
$\hat{i}=i^{*}(\hat{A},\hat{z})$. Then $\hat{A}(\hat{i})\in S$ and
$\hat{z}(\hat{i})=\top$.

  * Proof.

Since $(\hat{A},\hat{z})\in V_{\rm good}$, we have that
$\Pi(\hat{A},\hat{z})=\\{\hat{i}\\}$ for some $\hat{i}\in[R]$, and hence using
the definition of $i^{*}$ we must have $\hat{i}=i^{*}(\hat{A},\hat{z})$. The
claim now follows due to the definition of $\Pi(\hat{A},\hat{z})$. $\square$

We also define some events that will be useful in the analysis:

$\displaystyle{\mathcal{E}}_{\rm good}:=\Big{\\{}(A,z)\in V_{\rm
good}\Big{\\}},$
$\displaystyle{\mathcal{E}}_{1}:=\Big{\\{}\xi_{e}(i^{*}(A,z))=1\\}\wedge{\mathcal{E}}_{\rm
good},$ $\displaystyle{\mathcal{E}}_{2}:=\Big{\\{}~{}\forall
j\in[r],\Pi(B^{\prime}_{j},z^{\prime}_{j})=\Pi(A,z)\Big{\\}}.$

We shall use the above events to condition on and then bound the probability
of the event
$\left(f(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})\right)_{j\in[r]}\in\psi^{-1}(1)$.
To that end, we observe that

$\displaystyle\Pr_{\\{(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})\\}_{j\in[r]}}\left[\left(f(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})\right)_{j\in[r]}\in\psi^{-1}(1)\right]$
$\displaystyle\geq\Pr\left[{\mathcal{E}}_{1}\right]\Pr\left[{\mathcal{E}}_{2}\Big{|}{\mathcal{E}}_{1}\right]\Pr\left[\left(f(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})\right)_{j\in[r]}\in\psi^{-1}(1)\Big{|}~{}{\mathcal{E}}_{1}\wedge{\mathcal{E}}_{2}\right]$
(20)

We lower bound the probability of the various events in the above expression
one-by-one. To begin with, observe that

$\Pr\Big{[}{\mathcal{E}}_{\rm
good}\Big{]}=\sum_{i\in[R]}\Pr\left[\Pi(A,z)=\\{i\\}\right]=\sum_{i\in[R]}\beta\delta\left(1-\beta\delta\right)^{R-1}\geq\frac{e^{-1}}{r},$

where the last inequality uses $R=1/(\beta\delta r)$ from our choice of
parameters. Since $(A,z)$ and $\xi_{e}$ are independent, then using the above
bound and the fact that $\xi_{e}\sim\\{0,1\\}^{R}_{\rho^{2}}$, we get that

$\Pr\left[{\mathcal{E}}_{1}\right]=\Pr_{(A,z)}\left[{\mathcal{E}}_{\rm
good}\right]\Pr_{\xi_{e}}\left[\xi_{e}(i^{*}(A,z))=1\Big{|}(A,z)\right]\geq\frac{e^{-1}}{r}\cdot\rho^{2},$
(21)

For the second term of (20), we have the following lemma which is the main
technical component of the proof.

###### Lemma 6.4

Under the test distribution we have,

$\Pr_{(A,x,z),\\{(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})\\}^{r}_{j=1}}\left[~{}\forall
j\in[r],~{}\Pi(B^{\prime}_{j},z^{\prime}_{j})=\Pi(A,z)\Big{|}~{}{\mathcal{E}}_{1}\right]\geq
e^{-5}.$

  * Proof.

Let us denote $\mathcal{A}:=(A,z)$, and use $\mathcal{B}$ to denote the
collection of random variables
$\\{(B_{1},z^{\prime}_{1}),\ldots,(B_{r},z^{\prime}_{r})\\}$. To begin with,
observe that for every $j\in[r]$, we have
$\Pi(B^{\prime}_{j},z^{\prime}_{j})=\Pi(B_{j},z^{\prime}_{j})$ (for e.g., see
Claim 9.5 [GL22b]), and hence in the rest of the proof, we will simply bound
the probability of the event that $\Pi(B_{j},z^{\prime}_{j})=\Pi(A,z)$ holds
for every $j\in[r]$. To that end, for a fixing of $(A,z)\in
V^{R}\times\\{\bot,\top\\}^{R}$, let us define the sets
$Q_{0},Q_{1},Q_{2}\subseteq[R]$ as

$\displaystyle 1.$
$\displaystyle~{}Q_{0}:=\Big{\\{}i\in[R]\Big{|}~{}(A(i),z(i))\in
S\times\\{\bot\\}\\}$ $\displaystyle 2.$
$\displaystyle~{}Q_{1}:=\Big{\\{}i\in[R]\Big{|}~{}(A(i),z(i))\in
S^{c}\times\\{\top\\}\\}$ $\displaystyle 3.$
$\displaystyle~{}Q_{2}:=\Big{\\{}i\in[R]\Big{|}~{}(A(i),z(i))\in
S^{c}\times\\{\bot\\}\\}.$

By definition it follows that (without conditioning on ${\mathcal{E}}_{1}$) we
have

${\mathsf{E}}_{(A,z)}\left[|Q_{0}|\right]\leq R\cdot\delta=\frac{1}{r\beta}\ \
\ \ \ \ \textnormal{and}\ \ \ \ \ \
{\mathsf{E}}_{(A,z)}\left[|Q_{1}|\right]\leq R\cdot\beta=\frac{1}{r\delta}.$

Let ${\mathcal{E}}^{\prime}$ be the event that $\mathcal{Q}$ satisfies
$|Q_{0}|\leq 4/(r\beta)$ and $|Q_{1}|\leq 4/(r\delta)$. Then, using Chernoff
bound we have that

$\Pr_{(A,z)}\left[\neg{\mathcal{E}}^{\prime}\right]\leq\Pr_{(A,z)}\left[|Q_{0}|\geq\frac{4}{r\beta}\right]+\Pr_{(A,z)}\left[|Q_{1}|\geq\frac{4}{r\delta}\right]\leq
e^{-2/r\beta}+e^{-2/r\delta}\leq 2e^{-2/r\beta},$

where the last inequality follows due to $\delta\leq\varepsilon\ll\beta$.
Using the above bound and (21), we then have

$2e^{-2/(r\beta)}\geq\Pr_{(A,z)}\left[\neg{\mathcal{E}}^{\prime}\right]\geq\Pr_{(A,z)}\left[{\mathcal{E}}_{1}\right]\Pr_{(A,z)}\left[\neg{\mathcal{E}}^{\prime}\Big{|}~{}{\mathcal{E}}_{1}\right]\geq\frac{e^{-1}\rho^{2}}{r}\Pr_{(A,z)}\left[\neg{\mathcal{E}}^{\prime}\Big{|}~{}{\mathcal{E}}_{1}\right],$

which on rearranging gives us that

$\Pr_{(A,z)}\left[\neg{\mathcal{E}}^{\prime}\Big{|}~{}{\mathcal{E}}_{1}\right]\leq
e^{-1/(r\beta)}.$ (22)

Now we condition on the events ${\mathcal{E}}^{\prime}$ and
${\mathcal{E}}_{1}=\\{\xi_{e}(i^{*}(A,z))=1\\}\wedge{\mathcal{E}}_{\rm good}$,
and fix a realization of $\\{i^{*}(A,z),Q_{0},Q_{1},Q_{2}\\}$ satisfying
${\mathcal{E}}^{\prime}$ and ${\mathcal{E}}_{1}$. Note that conditioned on
these events, we have that $\Pi(A,z)=\\{i^{*}(A,z)\\}$ and furthermore, the
sets $Q_{0},Q_{1},Q_{2}$, and the index $i^{*}(A,z)$ together form a partition
of $[R]$. We denote this partition as
$\mathcal{Q}:=(\\{i^{*}\\},Q_{0},Q_{1},Q_{2})$. For every fixing of
$\mathcal{Q}$ satisfying ${\mathcal{E}}_{1}$ and ${\mathcal{E}}^{\prime}$, we
bound the probability of the event that $\Pi(B_{j},z^{\prime}_{j})=\Pi(A,z)$
holds for every $j\in[r]$. This entails lower bounding the probability of the
following events:

    * –

Denoting $i_{A}:=i^{*}(A,z)$, for every $j\in[r]$, we have
$(B_{j}(i_{A}),z^{\prime}_{j}(i_{A}))\in S\times\\{\top\\}$.

    * –

For every $\ell\in\\{0,1,2\\}$, for every $i\in Q_{\ell}$ and $j\in[r]$ , we
have $(B_{j}(i),z^{\prime}_{j}(i))\notin S\times\\{\top\\}$.

We handle these events one-by-one in the following claims.

###### Claim 6.5

For a fixed $\mathcal{Q}$ satisfying the events ${\mathcal{E}}_{1}$ and
${\mathcal{E}}^{\prime}$ we have

$\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall
j\in[r],(B_{j}(i_{A}),z^{\prime}_{j}(i_{A}))\in S\times\\{\top\\}\right]\geq
1-2r(\varepsilon+\eta).$

  * Proof.

Note that under the conditioning we have $(A,z)\in V_{\rm good}$, and hence
using Observation 6.3 we have that $z(i_{A})=\top$ (Observation 6.3).
Furthermore, conditioning on ${\mathcal{E}}_{1}$ implies that
$\xi_{e}(i_{A})=1$, which in turn implies that $z_{j}(i_{A})=z(i_{A})$ for
every $j\in[r]$ (from Step 4b. of Figure 8). Putting these together, we get
that

$\Pr_{(z_{j}(i_{A}))^{r}_{j=1}|z(i_{A})=\top}\left[~{}\forall
j\in[r],z_{j}(i_{A})=\top\right]=1.$

Furthermore, for every $j\in[r]$, observe that $z^{\prime}_{j}(i_{A})$ is an
independent $(1-\eta)$-correlated copy of $z_{j}(i_{A})$ and hence

$\Pr_{(z^{\prime}_{j}(i_{A}))^{r}_{j=1}|z(i_{A})}=\top\left[~{}\forall
j\in[r],~{}z^{\prime}_{j}(i_{A})=\top\right]\geq\Pr_{(z_{j}(i_{A}))^{r}_{j=1}|z(i_{A})}=\top\left[~{}\forall
j\in[r],~{}z_{j}(i_{A})=\top\right]-r\eta=1-r\eta.$ (23)

On the other hand, fixing $\mathcal{Q}$, $A(i_{A})$ is a uniformly random
vertex in $S$ and $B_{1}(i_{A}),\ldots,B_{r}(i_{A})$ are all sampled using
$1$-step random walks from $A(i_{A})$ in the graph $G_{\eta}$. Using these
observations we can bound:

$\displaystyle\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall
j\in[r],~{}(B_{j}(i_{A}),z^{\prime}_{j}(i_{A}))\in S\times\\{\top\\}\right]$
$\displaystyle=\Pr_{\\{B_{j}(i_{A})\\}_{j}\sim
G_{\eta}(A(i_{A}))}\left[~{}\forall j\in[r],~{}B_{j}(i_{A})\in
S\Big{|}A(i_{A})\in
S\right]\Pr_{z^{\prime}_{j}(i_{A})|z(i_{A})=\top}\left[~{}\forall
j\in[r],~{}z^{\prime}_{j}(i_{A})=\top\Big{|}z(i_{A})=\top\right]$
$\displaystyle\overset{1}{\geq}\left(1-r(\varepsilon+\eta)\right)\left(1-r\eta\right)$
$\displaystyle\geq 1-2r(\varepsilon+\eta),$

where in step $1$, the bound on the first term uses the fact that the
expansion of the set $S$ in the graph $G_{\eta}$ is at most
$\varepsilon+\eta$, and the second term uses the bound from (23). $\square$

###### Claim 6.6

For a fixed $\mathcal{Q}$ satisfying the events ${\mathcal{E}}_{1}$ and
${\mathcal{E}}^{\prime}$ we have

$\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall i\in
Q_{0},~{}\forall j\in[r],~{}(B_{j}(i),z^{\prime}_{j}(i))\notin
S\times\\{\top\\}\right]\geq e^{-4}.$

  * Proof.

Observe that for any fixed $i\in Q_{0}$ we have $z(i)=\bot$, and for
$j\in[r]$, fixing $z(i)$, marginally $z^{\prime}_{j}(i)$ is a
$\rho^{\prime}:=\rho^{2}(1-\eta)$ correlated copy of $z(i)$. Hence,

$\displaystyle\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall i\in
Q_{0},~{}\forall j\in[r],~{}(B_{j}(i),z^{\prime}_{j}(i))\notin
S\times\\{\top\\}\right]$
$\displaystyle\geq\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall
i\in Q_{0},~{}\forall j\in[r],~{}z^{\prime}_{j}(i)=\bot\right]$
$\displaystyle=\prod_{i\in
Q_{0}}\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall
j\in[r],~{}z^{\prime}_{j}(i)=\bot\right]$ $\displaystyle\geq\prod_{i\in
Q_{0}}\left(1-\sum_{j\in[r]}\Pr_{z^{\prime}_{j}(i)\underset{\rho^{\prime}}{\sim}z(i)}\left[z^{\prime}_{j}(i)=\top\Big{|}i\in
Q_{0}\right]\right)$ $\displaystyle\overset{1}{=}\prod_{i\in
Q_{0}}\left(1-\sum_{j\in[r]}\Pr_{z^{\prime}_{j}(i)\underset{\rho^{\prime}}{\sim}z(i)}\left[z^{\prime}_{j}(i)=\top\Big{|}z(i)=\bot\right]\right)$
$\displaystyle\overset{2}{=}\prod_{i\in
Q_{0}}\left(1-r(1-\rho^{\prime})\beta\right)$
$\displaystyle\overset{3}{\geq}(1-r(1-\rho^{\prime})\beta)^{4/r\beta}$
$\displaystyle\geq e^{-4}$

where step $1$ follows using the definition of $Q_{0}$, step $2$ follows from
the distribution of $z^{\prime}_{j}(i)$ conditioned on $z(i)=\bot$, and step
$3$ follows using that the bound $|Q_{0}|\leq 4/r\beta$ holds conditioned on
${\mathcal{E}}^{\prime}$. $\square$

###### Claim 6.7

For a fixed $\mathcal{Q}$ satisfying the events
${\mathcal{E}}_{1},{\mathcal{E}}^{\prime}$ we have

$\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall i\in
Q_{1},~{}\forall j\in[r],~{}(B_{j}(i),z^{\prime}_{j}(i))\notin
S\times\\{\top\\}\right]\geq 1-8(\varepsilon+\eta).$

  * Proof.

Here we observe that fixing $\mathcal{Q}$, for every $i\in Q_{1}$, $A(i)$ is a
uniformly random vertex in $S^{c}$. Hence we can proceed as follows:

$\displaystyle\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall i\in
Q_{1},~{}\forall j\in[r],~{}(B_{j}(i),z^{\prime}_{j}(i))\notin
S\times\\{\top\\}\right]$
$\displaystyle\geq\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall
i\in Q_{1},~{}\forall j\in[r],~{}B_{j}(i)\in S^{c}\right]$ $\displaystyle\geq
1-\sum_{i\in
Q_{1}}\sum_{j\in[r]}\Pr_{B_{j}(i){\sim}G_{\eta}(A(i))}\left[B_{j}(i)\in
S\Big{|}i\in Q_{1}\right]$ $\displaystyle\overset{1}{=}1-\sum_{i\in
Q_{1}}\sum_{j\in[r]}\Pr_{B_{j}(i){\sim}G_{\eta}(A(i))}\left[B_{j}(i)\in
S\Big{|}A(i)\in S^{c}\right]$ $\displaystyle\overset{2}{\geq}1-|Q_{1}|r\cdot
2(\eta+\varepsilon)\delta$
$\displaystyle\overset{3}{\geq}1-8(\eta+\varepsilon),$

where step $1$ again follows using the definition of $Q_{1}$. In step $2$, we
use that

$\Pr_{B_{j}(i)\sim G_{\eta}(A_{j}(i))}\left[B_{j}(i)\in S\Big{|}A_{j}(i)\in
S^{c}\right]\leq\frac{(\varepsilon+\eta)\delta}{(1-\delta)}\leq
2(\varepsilon+\eta)\delta,$

where the first inequality follows using the observation that the expansion of
$S$ in $G_{\eta}$ is at most $\varepsilon+\eta$. In step $3$, we use the bound
on $|Q_{1}|\leq 4/r\delta$ from the conditioning on the event
${\mathcal{E}}^{\prime}$. $\square$

###### Claim 6.8

For a fixed $\mathcal{Q}$ satisfying the events
${\mathcal{E}}_{1},{\mathcal{E}}^{\prime}$ we have

$\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall i\in
Q_{2},~{}\forall j\in[r],~{}(B_{j}(i),z^{\prime}_{j}(i))\notin
S\times\\{\top\\}\right]\geq 1-2(\varepsilon+\eta).$

  * Proof.

This case follows by combining the arguments for $Q_{0}$ and $Q_{1}$ indices:

$\displaystyle\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall i\in
Q_{2},~{}\forall j\in[r],~{}(B_{j}(i),z^{\prime}_{j}(i))\notin
S\times\\{\top\\}\right]$ $\displaystyle\geq 1-\sum_{i\in
Q_{2}}\sum_{j\in[r]}\Pr_{B_{j}(i){\sim}G_{\eta}(A(i))}\Pr_{z^{\prime}_{j}(i)\underset{\rho^{\prime}}{\sim}z(i)}\left[(B_{j}(i),z^{\prime}_{j}(i))\in
S\times\\{\top\\}\Big{|}i\in Q_{2}\right]$
$\displaystyle\overset{1}{=}1-\sum_{i\in
Q_{2}}\sum_{j\in[r]}\Pr_{B_{j}(i){\sim}G_{\eta}(A(i))}\left[B_{j}(i)\in
S\Big{|}A(i)\in
S^{c}\right]\cdot\Pr_{z^{\prime}_{j}(i)\underset{\rho^{\prime}}{\sim}z(i)}\left[z^{\prime}_{j}(i)=\top\Big{|}z(i)=\bot\right]$
$\displaystyle\overset{2}{\geq}1-|Q_{2}|r\cdot
2(\varepsilon+\eta)\delta\cdot(1-\rho^{\prime})\beta$
$\displaystyle\overset{3}{\geq}1-2(\eta+\varepsilon),$

where in step $1$, we use the definition of $Q_{2}$, as well as the fact that
for every $i$, $B_{j}(i)\sim G_{\eta}(A(i))$ and $z^{\prime}_{j}(i)\sim z(i)$
are drawn independent of each other. In step $2$, we bound the two probability
terms using the “step-$2$” arguments from the analysis of $Q_{0}$ and $Q_{1}$,
and step $3$ uses the elementary bound $|Q_{2}|\leq R=1/r\beta\delta$.
$\square$

Putting Things together. Now we put together the bounds for the probabilities
of the various events. For brevity, denote
${\mathcal{E}}^{\prime\prime}:={\mathcal{E}}^{\prime}\wedge{\mathcal{E}}_{1}$.
Then,

$\displaystyle\Pr_{\mathcal{A},\mathcal{B}}\left[~{}\forall
j\in[r],~{}\Pi(B_{j},z^{\prime}_{j})=\Pi(A,z)\Big{|}~{}{\mathcal{E}}_{1}\right]$
$\displaystyle\geq\Pr_{\mathcal{A},\mathcal{B}}\left[~{}\forall
j\in[r],~{}~{}\Pi(B_{j},z^{\prime}_{j})=\Pi(A,z)\Big{|}~{}{\mathcal{E}}^{\prime\prime}\right]-\Pr\left[\neg{\mathcal{E}}^{\prime}\Big{|}~{}{\mathcal{E}}_{1}\right]$
$\displaystyle\overset{1}{\geq}{\mathsf{E}}_{\mathcal{Q}|{\mathcal{E}}^{\prime\prime}}\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall
j\in[r],~{}~{}\Pi(B_{j},z^{\prime}_{j})=\Pi(A,z)\Big{|}~{}{\mathcal{E}}^{\prime\prime},\mathcal{Q}\right]-e^{-1/r\beta}$
$\displaystyle\overset{2}{=}{\mathsf{E}}_{\mathcal{Q}|{\mathcal{E}}^{\prime\prime}}\Bigg{[}\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall
j\in[r],(B_{j}(i_{A}),z^{\prime}_{j}(i_{A}))\in
S\times\\{\top\\}\Big{|}~{}{\mathcal{E}}^{\prime\prime},\mathcal{Q}\right]\cdot$
$\displaystyle\qquad\qquad\qquad\prod^{2}_{\ell=0}\Pr_{\mathcal{A},\mathcal{B}|\mathcal{Q}}\left[~{}\forall
i\in Q_{\ell},j\in[r],(B_{j}(i),z^{\prime}_{j}(i))\notin
S\times\\{\top\\}\right]\Bigg{]}-e^{-1/r\beta}$
$\displaystyle\overset{3}{\geq}(1-2r(\varepsilon+\eta))\cdot
e^{-4}\cdot(1-8(\varepsilon+\eta))\cdot(1-2(\varepsilon+\eta))-e^{-1/r\beta}$
$\displaystyle\overset{4}{\geq}e^{-5},$

where step $1$ follows using the bound from (22). In step $2$, we use the
following observation: for a fixing of $\mathcal{Q}$, the distribution of rows
across the sets $\\{i_{A}\\},Q_{0},Q_{1},Q_{2}$ are all independent. Step $3$
uses the bounds from Claims 6.5, 6.6, 6.7, and 6.8. Step $4$ follows from our
choices of parameters for $\beta,\eta$, and $\varepsilon$. This concludes the
proof of Lemma 6.4. $\square$

Continuing with the proof of Lemma 6.2, we now bound the third probability
term from (20). For brevity, we introduce another event
${\mathcal{E}}_{3}:={\mathcal{E}}_{1}\wedge{\mathcal{E}}_{2}$. Then,
randomizing over the choice of
$\mathcal{V}:=(A,z),(B^{\prime}_{1},x^{\prime}_{1},z^{\prime}_{1}),\ldots,(B^{\prime}_{r},x^{\prime}_{r},z^{\prime}_{r})$,
we have

$\displaystyle\Pr_{\mathcal{V}}\bigg{[}~{}\psi\Big{(}f(B^{\prime}_{1},x^{\prime}_{1},z^{\prime}_{1}),\ldots,f(B^{\prime}_{2},x^{\prime}_{2},z^{\prime}_{2})\Big{)}=1\Big{|}~{}{\mathcal{E}}_{1}\wedge{\mathcal{E}}_{2}\bigg{]}$
$\displaystyle\overset{1}{=}\Pr_{\mathcal{V}}\bigg{[}~{}\psi\Big{(}x^{\prime}_{1}(i^{*}(B^{\prime}_{1},z^{\prime}_{1})),\ldots,x^{\prime}_{r}(i^{*}(B^{\prime}_{r},z^{\prime}_{r}))\Big{)}=1\Big{|}~{}{\mathcal{E}}_{3}\bigg{]}$
$\displaystyle\overset{2}{=}\Pr_{\mathcal{V}}\bigg{[}~{}\psi\Big{(}x^{\prime}_{1}(i^{*}(A,z)),\ldots,x^{\prime}_{r}(i^{*}(A,z))\Big{)}=1\Big{|}~{}{\mathcal{E}}_{3}\bigg{]}$
$\displaystyle\overset{3}{=}\Pr_{\mathcal{V}}\bigg{[}~{}\psi\Big{(}\tilde{x}_{1}(i^{*}(A,z)),\ldots,\tilde{x}_{r}(i^{*}(A,z))\Big{)}=1\Big{|}~{}{\mathcal{E}}_{3}\bigg{]}$
$\displaystyle\overset{4}{\geq}\Pr_{\mathcal{V}}\bigg{[}~{}\psi\Big{(}{x}_{1}(i^{*}(A,z)),\ldots,{x}_{r}(i^{*}(A,z))\Big{)}=1\Big{|}~{}{\mathcal{E}}_{3}\bigg{]}-r\eta$
$\displaystyle\overset{5}{=}p_{e}-r\eta.$ (24)

We justify that each of the above steps hold conditioning on
${\mathcal{E}}_{3}={\mathcal{E}}_{1}\wedge{\mathcal{E}}_{2}$. For step $1$, we
use the definition of the assignment $f$. Step $2$ uses the following
argument: since we condition on ${\mathcal{E}}_{2}$, we have
$\Pi(B^{\prime}_{j},z^{\prime}_{j})=\Pi(A,z)$ for every $j\in[r]$. This
implies the following for every $j$:

  * (i)

Since $(A,z)\in V_{\rm good}$ (due to conditioning on ${\mathcal{E}}_{1}$), we
have $\Pi(B^{\prime}_{j},z^{\prime}_{j})=\Pi(A,z)=\\{i^{*}(A,z)\\}$, and hence
$(B^{\prime}_{j},z^{\prime}_{j})\in V_{\rm good}$.

  * (ii)

Again, since (i) implies that for every $j\in[r]$, we have
$|\pi(B^{\prime}_{j},z^{\prime}_{j})|=1$, we have
$i^{*}(B^{\prime}_{j},z^{\prime}_{j})=i^{*}(A,z)$.

For step $3$, we build upon the above observations and further note that for
every $j\in[r]$ we can argue the following:

  * (iii)

Since $(B^{\prime}_{j},z^{\prime}_{j})\in V_{\rm good}$ and
$i^{*}(B^{\prime}_{j},z^{\prime}_{j})=i^{*}(A,z)$, using Observation 6.3 we
have $z^{\prime}_{j}(i^{*}(A,z))=\top$.

  * (iv)

Since under the test distribution we have $(B^{\prime}_{j},x^{\prime}_{j})\sim
M^{(\mu_{j})}_{z^{\prime}_{j}}(B_{j},\tilde{x}_{j})$, this along with (iii)
implies that $x^{\prime}_{j}(i^{*}(A,z))=\tilde{x}_{j}(i^{*}(A,z))$ with
probability $1$.

Step $4$ follows by observing that for every $j\in[r]$, $\tilde{x}_{j}(i)$ is
a $(1-\eta)$-correlated copy of $x_{j}(i)$, and hence the event
$(\tilde{x}_{j}(i^{*}(A,z)))=x_{j}(i^{*}(A,z))$ holds for every $j\in[r]$ with
probability least $1-r\eta$. Finally, Step $5$ uses that since
$(x_{j}(i^{*}(A,z))_{j\in[r]}$ is sampled from $\theta_{[r]}$, it is an
accepting string with probability $p_{e}$.

Finishing the Proof. We plug in the bounds from (21), Lemma 6.4, and (24) into
(20), and get that

$\displaystyle\Pr_{\\{(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})\\}_{j\in[r]}}\left[\psi\Big{(}f(B^{\prime}_{1},x^{\prime}_{1},z^{\prime}_{1}),\ldots,f(B^{\prime}_{2},x^{\prime}_{2},z^{\prime}_{2})\Big{)}=1\right]$
$\displaystyle\geq\Pr\left[{\mathcal{E}}_{1}\right]\Pr\left[{\mathcal{E}}_{2}\Big{|}{\mathcal{E}}_{1}\right]\Pr\left[\left(f(B^{\prime}_{j},x^{\prime}_{j},z^{\prime}_{j})\right)_{j\in[r]}\in\psi^{-1}(1)\Big{|}~{}{\mathcal{E}}_{1}\wedge{\mathcal{E}}_{2}\right]$
(Using (20)) $\displaystyle\geq\frac{\rho^{2}}{e\cdot r}\cdot
e^{-5}\cdot(p_{e}-r\eta)$ (Using (21), Lemma 6.4, (24))
$\displaystyle\geq\frac{\rho^{2}p_{e}}{r}\cdot e^{-6}-O(r\eta),$

which concludes the proof of Lemma 6.2.

##  7 Soundness

We introduce some additional notation used in the soundness analysis.
Throughout the proof, we will be dealing with functions defined over various
probability spaces. We will always use $\Omega$ to denote the underlying
$4$-point set $\\{0,1\\}\times\\{\bot,\top\\}$, and for any $i\in V_{\rm
gap}$, we will use $\Omega_{i}$ to denote the probability space
$\\{0,1\\}_{\mu_{i}}\otimes\\{\bot,\top\\}_{\beta}$. Furthermore, our
expressions shall feature noise operators acting on various probability
spaces. To avoid ambiguity, we introduce the notation for each noise operator
used here. The following holds for any $\kappa\in(0,1)$:

  * •

$\mathcal{T}^{(\beta)}_{\kappa}$ is noise operator on
$L_{2}(\\{\bot,\top\\}^{R}_{\beta})$ acting on the $z_{i}$ variables.

  * •

For any $i\in V_{\rm Gap}$, we use $\mathcal{T}^{(\mu_{i})}_{\kappa}$ to
denote the noise operators on $L_{2}(\\{0,1\\}^{R}_{\mu_{i}})$ which acts on
the vector variable $x_{i}$.

  * •

For any $i\in V_{\rm gap}$, we use $\mathcal{T}^{(\Omega_{i})}_{\kappa}$ to
denote the noise operator
$\mathcal{T}^{(\mu_{i})}_{\kappa}\circ\mathcal{T}^{(\beta)}_{\kappa}$ on
$L_{2}(\\{0,1\\}^{R}_{\mu_{i}}\otimes\\{\bot,\top\\}^{R}_{\beta})$ which acts
on the vector variables $x_{i}$ and $z_{i}$ independently.

We extend the above notation and use ${\sf
Inf}^{(\Omega_{i})}_{j}\left[\cdot\right]$ and ${\sf
Inf}^{(\mu_{i})}_{j}\left[\cdot\right]$ to denote that the influence of a
function is being defined with respect to $\Omega^{R}_{i}$ and $\mu^{R}_{i}$
respectively.

######  Remark 7.1 (Definition of $\mathcal{T}^{(\Omega_{i})}_{1-\eta}$)

We point out that in the above convention,
$\mathcal{T}^{(\Omega_{i})}_{1-\eta}$ is not the $(1-\eta)$-correlated Bonami-
Beckner operator in the space $L_{2}(\Omega_{i})$. The $(1-\eta)$-correlation
Bonami-Beckner operator on $L_{2}(\Omega_{i})$ re-randomizes each
coordinate$(x,z)(i)$ with probability $(1-\eta)$, whereas in the above
definition of $\mathcal{T}^{(\Omega_{i})}_{1-\eta}$, for every $i\in[R]$, both
$x(i)$ and $z(i)$ are each chosen to be re-randomized with probability
$(1-\eta)$ independently. However, it still exhibits Fourier decay properties
similar to the Bonami-Beckner operator on $\Omega^{R}_{i}$ (see Fact B.1).

Finally, we will use $\mathcal{D}^{R}_{e}$ to denote the distribution on the
variables $(x_{i},z_{i})_{i\in e}$ under the test distribution conditioned on
the fixing of $e$.

###  7.1 First Steps

Suppose $G$ is a NO instance, and let
$f:V^{R}\times\\{0,1\\}^{R}\times\\{\bot,\top\\}^{R}\to\\{0,1\\}$ be a
feasible labeling of $\mathcal{H}$ i.e., it satisfies the global constraint:

${\mathsf{E}}_{i\sim G_{\rm gap}}{\mathsf{E}}_{A\sim
V^{R}}{\mathsf{E}}_{(x,z)\sim\\{0,1\\}^{R}_{\mu_{i}}\otimes\\{\bot,\top\\}^{R}_{\beta}}\left[f(A,x,z)\right]=\mu.$
(25)

Now, for every $A\in V^{R}$, and for every $i\in V_{\rm gap}$, we shall find
it useful to define the functions
$g_{A,i}:\left(\\{0,1\\}\times\\{\bot,\top\\}\right)^{R}\to[0,1]$as

$g_{A,i}(x,z)={\mathsf{E}}_{B\sim G^{\otimes
R}_{\eta}(A)}{\mathsf{E}}_{(B^{\prime},x^{\prime})\sim
M^{(\mu_{i})}_{z}(B,x)}{\mathsf{E}}_{\pi\sim\mathbbm{S}_{R}}\left[f(\pi(B^{\prime},x^{\prime},z))\right],$
(26)

i.e., $g_{A,i}$ is the restriction of $f$ to $A$ averaged over the noisy walk
on $G^{\otimes R}_{\eta}$, the $M^{(\mu_{i})}_{z^{\prime}_{i}}$ operators, and
the random permutation $\pi_{i}$. The following observation on the averaged
functions will be useful throughout the various steps of the soundness
analysis.

###### Observation 7.2

For every $i\in V_{\rm gap}$, the function $g_{A,i}$ is an $R$-variate
function in $L_{2}(\Omega^{R}_{i})$, where
$\Omega_{i}=\\{0,1\\}_{\mu_{i}}\otimes\\{\bot,\top\\}_{\beta}$. Consequently,
the influences of the function $g_{A,i}$ are defined with respect to the
Fourier basis corresponding to $\Omega^{R}_{i}$.

Let us introduce some additional notation that will be useful throughout the
soundness analysis. Let

$\psi(x)=\sum_{a\in\psi^{-1}(1)}\prod_{j\in S_{+}(a)}x_{j}\prod_{j\in
S_{-}(a)}(1-x_{j})$

be the multilinear representation of $\psi$, where for any
$a\in\\{0,1\\}^{r}$, $S_{+}(a)$ and $S_{-}(a)$ are subsets of $[r]$ consisting
of the indices with $a(i)=1$ and $a(i)=0$ respectively. Next, for any ordered
edge $e=(i_{1},\ldots,i_{r})\in E_{\rm gap},a\in\psi^{-1}(1)$, and for every
$i\in e$, define

$f^{(a,e,i)}=\begin{cases}f&\mbox{ if }i=i_{j},j\in S_{+}(a)\\\ 1-f&\mbox{ if
}i=i_{j},j\in S_{-}(a).\end{cases}$ (27)

Analogously, for every $e=(i_{1},\ldots,i_{r})\in E_{\rm gap}$, $i\in e$ and
$a\in\psi^{-1}(1)$ we define

$g^{(a,e,i)}_{A,i}=\begin{cases}g_{A,i}&\mbox{ if }i=i_{j},j\in S_{+}(a)\\\
1-g_{A,i}&\mbox{ if }i=i_{j},j\in S_{-}(a).\end{cases}$

As in Observation 7.2, note that for any $i\in V_{\rm gap}$, for any choices
of $A,a,e$, the function $g^{(a,e,i)}_{A,i}$ is in $L_{2}(\Omega^{R}_{i})$.

Arithmetization. We now proceed to arithmetize the fraction of constraints
satisfied by the assignment $f$. To that end, let us fix a choice of
$e=(i_{1},\ldots,i_{r})\in E_{\rm gap}$, and express the fraction of satisfied
constraints corresponding to the distribution conditioned on the choice of
edge $e$:

$\displaystyle\Pr\Big{[}\mbox{ Test Accepts for fixed }e\Big{]}$
$\displaystyle={\mathsf{E}}_{A\sim
V^{R}}{\mathsf{E}}_{(\tilde{x}_{i},z^{\prime}_{i})_{i\in
e}}{\mathsf{E}}_{(B_{i})_{i\in e}\sim G^{\otimes
R}_{\eta}(A)}{\mathsf{E}}_{\\{(B^{\prime}_{i},x^{\prime}_{i})\sim
M^{(\mu_{i})}_{z^{\prime}_{i}}(B_{i},\tilde{x}_{i})\\}_{i\in
e}}{\mathsf{E}}_{\\{\pi_{i}\\}_{i\in
e}\sim\mathbbm{S}_{R}}\left[\psi\Big{(}f(\pi_{i_{1}}(B^{\prime}_{i_{1}},x^{\prime}_{i_{1}},z^{\prime}_{i_{1}})),\ldots,f(\pi_{i_{r}}(B^{\prime}_{i_{r}},x^{\prime}_{i_{r}},z^{\prime}_{i_{r}}))\Big{)}\right]$
$\displaystyle={\mathsf{E}}_{A\sim
V^{R}}{\mathsf{E}}_{(\tilde{x}_{i},z^{\prime}_{i})_{i\in
e}}{\mathsf{E}}_{(B_{i})_{i\in e}\sim G^{\otimes
R}_{\eta}(A)}{\mathsf{E}}_{\\{(B^{\prime}_{i},x^{\prime}_{i})\sim
M^{(\mu_{i})}_{z^{\prime}_{i}}(B_{i},\tilde{x}_{i})\\}_{i\in
e}}{\mathsf{E}}_{\\{\pi_{i}\\}_{i\in e}\sim\mathbbm{S}_{R}}$
$\displaystyle\qquad\qquad\qquad\left[\sum_{a\in\psi^{-1}(1)}\prod_{i=i_{j}:a(j)=1}f(\pi_{i}(B^{\prime}_{i},x^{\prime}_{i},z^{\prime}_{i}))\prod_{i=i_{j}:a(j)=0}(1-f(\pi_{i}(B^{\prime}_{i},x^{\prime}_{i},z^{\prime}_{i})))\right]$
$\displaystyle=\sum_{a\in\psi^{-1}(1)}{\mathsf{E}}_{A\sim
V^{R}}{\mathsf{E}}_{(\tilde{x}_{i},z^{\prime}_{i})_{i\in
e}}{\mathsf{E}}_{(B_{i})_{i\in e}\sim G^{\otimes
R}_{\eta}(A)}{\mathsf{E}}_{\\{(B^{\prime}_{i},x^{\prime}_{i})\sim
M^{(\mu_{i})}_{z^{\prime}_{i}}(B_{i},\tilde{x}_{i})\\}_{i\in
e}}{\mathsf{E}}_{\\{\pi_{i}\\}_{i\in e}\sim\mathbbm{S}_{R}}\left[\prod_{i\in
e}f^{(a,e,i)}(\pi_{i}(B^{\prime}_{i},x^{\prime}_{i},z^{\prime}_{i}))\right]$
$\displaystyle\overset{1}{=}\sum_{a\in\psi^{-1}(1)}{\mathsf{E}}_{A\sim
V^{R}}{\mathsf{E}}_{({x}_{i},z_{i})_{i\in e}}\left[\prod_{i\in
e}{\mathsf{E}}_{\tilde{x}_{i}\underset{1-\eta}{\sim}x_{i}}{\mathsf{E}}_{z^{\prime}_{i}\underset{1-\eta}{\sim}z_{i}}{\mathsf{E}}_{B_{i}\sim
G^{\otimes R}_{\eta}(A)}{\mathsf{E}}_{(B^{\prime}_{i},x^{\prime}_{i})\sim
M^{(\mu_{i})}_{z^{\prime}_{i}}(B_{i},\tilde{x}_{i})}{\mathsf{E}}_{\pi_{i}\sim\mathbbm{S}_{R}}f^{(a,e,i)}(\pi_{i}(B^{\prime}_{i},x^{\prime}_{i},z^{\prime}_{i}))\right]$
$\displaystyle\overset{2}{=}\sum_{a\in\psi^{-1}(1)}{\mathsf{E}}_{A\sim
V^{R}}{\mathsf{E}}_{({x}_{i},z_{i})_{i\in e}}\left[\prod_{i\in
e}{\mathsf{E}}_{\tilde{x}_{i}\underset{1-\eta}{\sim}x_{i}}{\mathsf{E}}_{z^{\prime}_{i}\underset{1-\eta}{\sim}z_{i}}g^{(a,e,i)}_{A,i}(\tilde{x}_{i},z^{\prime}_{i})\right]$
$\displaystyle\overset{3}{=}\sum_{a\in\psi^{-1}(1)}{\mathsf{E}}_{A\sim
V^{R}}{\mathsf{E}}_{({x}_{i},z_{i})_{i\in e}}\left[\prod_{i\in
e}\mathcal{T}^{(\Omega_{i})}_{1-\eta}g^{(a,e,i)}_{A,i}(x_{i},z_{i})\right],$

where step $1$ uses the independence of the various averaging operators, step
$2$ follows using the definition of $g_{A,i}$ from (26) and step $3$ follows
from the definition of $\mathcal{T}^{(\Omega_{i})}_{1-\eta}$. Using the above,
the overall weight of constraints satisfied by the assignment indicated by
$f(\cdot)$ can be expressed as

$\Pr\Big{[}\mbox{ Test
Accepts}\Big{]}=\sum_{a\in\psi^{-1}(1)}{\mathsf{E}}_{e\sim E_{\rm
gap}}{\mathsf{E}}_{A\sim V^{R}}{\mathsf{E}}_{({x}_{i},z_{i})_{i\in
e}\sim\mathcal{D}^{R}_{e}}\left[\prod_{i\in
e}\mathcal{T}^{(\Omega_{i})}_{1-\eta}g^{(a,e,i)}_{A,i}(x_{i},z_{i})\right].$
(28)

Now we proceed with the soundness analysis in steps.

###  7.2 Averaging out the $z$-variables

Now in this step, we will decouple the $z_{i}$ variables and average them out.
Formally, we have the following key lemma which states that if for a fixed
edge, the corresponding functions have small influences, then for that term,
we can replace the correlated sampling of the $z_{i}$-variables with
independent sampling, while only losing small additive factors in the
soundness value.

###### Lemma 7.3

Fix an edge $e=(i_{1},\ldots,i_{r})\in E_{\rm gap}$, and let $(h_{i})_{i\in
e}:\Omega^{R}\to[0,1]^{e}$ be a collection of functions where for every $i\in
e$ we have $h_{i}\in L_{2}(\Omega^{R}_{i})$, and

$\max_{i\in e}\max_{j\in[R]}{\sf
Inf}^{(\Omega_{i})}_{j}\left[{h_{i}}\right]\leq\tau.$

Assume that $\theta_{e}$ is $(\gamma\mu)^{r}$-smooth as in the setting of the
reduction i.e., for any $\alpha\in\\{0,1\\}^{e}$ we have
$\Pr_{X_{e}\sim\theta_{e}}\left[X_{e}=\alpha\right]\geq(\gamma\mu)^{r}$.
Furthermore, suppose ${\rm Var}\big{[}h^{>d}_{i}\big{]}\leq(1-\eta)^{d}$ for
every $d\geq\frac{1}{18}\log\frac{1}{\tau}/\log\frac{1}{\eta^{r}\gamma^{r}}$.
Then,

${\mathsf{E}}_{(x_{i},z_{i})_{i\in e}\sim\mathcal{D}^{R}_{e}}\left[\prod_{i\in
e}h_{i}(x_{i},z_{i})\right]\leq 2^{r}\cdot{\mathsf{E}}_{(x_{i})_{i\in
e}\sim\theta^{R}_{e}}\left[\prod_{i\in[r]}\overline{h_{i}}(x_{i})\right]+\mu^{r}+C^{\prime}_{r}\cdot\sqrt{r}\tau^{C\eta\kappa/r^{2}},$

where for every $i\in e$, $\overline{h_{i}}:\\{0,1\\}^{R}\to[0,1]$ is the
function in $L_{2}(\\{0,1\\}^{R}_{\mu_{i}})$ defined as
$\overline{h_{i}}(x)\overset{\rm
def}{=}{\mathsf{E}}_{z\sim\\{\bot,\top\\}^{R}_{\beta}}\left[h_{i}(x,z)\right]$,
and $\kappa=\beta/\log(1/\gamma)$.

We defer the proof of the above lemma to Section 8 for now. Using the above
lemma, we will show that for most choices of $A\in V^{R}$, we can average out
the $z_{i}$-variables in the corresponding inner expectation term with
negligible losses. To that end, we define the set $V_{\rm nice}\subset V^{R}$
as

$V_{\rm nice}:=\left\\{A\in V^{R}\Big{|}\Pr_{e\sim E_{\rm
gap}}\left[\max_{i\in e}\max_{j\in[R]}{\sf
Inf}^{(\Omega_{i})}_{j}\left[\mathcal{T}^{(\Omega_{i})}_{1-\eta}g_{A,i}\right]>\tau\right]\leq\nu\right\\}$
(29)

In other words, $V_{\rm nice}$ is the set of vertices in $A\in V^{R}$ for
which almost all choices of edges $e$ have the property that all functions in
$\\{g_{A,i}\\}_{i\in e}$ have small influences w.r.t. their respective
probability spaces. The following lemma bounds the size of $|V_{\rm nice}|$.

###### Lemma 7.4

Since $G$ is a NO instance, we have

$\Pr_{A\sim V^{R}}\Big{[}A\in V_{\rm nice}\Big{]}\geq 1-\nu.$

The proof of the above lemma proceeds using the influence-decoding argument
for SmallSetExpansion [KKMO07, RST12]. We defer its proof to Section 9.1 for
now and continue with the soundness analysis. As a next step, we use Lemma 7.3
to derive the following bound on the inner expectation corresponding to the
vertices in $V_{\rm nice}$.

###### Corollary 7.5

For every $A\in V_{\rm nice}$ we have that

$\displaystyle\sum_{a\in\psi^{-1}(1)}{\mathsf{E}}_{e\sim E_{\rm