Let $\beta,\gamma$ and $\cF$ be such that  $0\le \beta < \gamma \le 1$ and $\kgyf \cap \kbnf = \emptyset$. Then there exists a non-negative vector $\veclambda = (\lambda_{f,i,\sigma})_{f\in\cF,i \in [k], \sigma\in [q]}$ and real numbers $\tau_Y > \tau_N$ such that

\[
\forall \vecmu \in \kgyf, ~~ \langle \veclambda,\vecmu \rangle \ge \tau_Y \text{~~and~~ } \forall \vecmu \in \kbnf, ~~ \langle \veclambda,\vecmu \rangle \le \tau_N \, .
\]

We will use the following form of the hyperplane separation theorem for convex bodies (see, e.g., <cit.>).

Let $K^Y$ and $K^N$ be two disjoint nonempty closed convex sets in $\R^{|\cF|\cdot kq}$ at least one of which is compact. Then there exists a nonzero vector $\veclambda = (\lambda_{f,t,\sigma})_{f\in\cF,t \in [k], \sigma\in [q]}$ and real numbers $\tau_Y > \tau_N$ such that

\[
\forall \vecmu \in K^Y, ~~ \langle \veclambda,\vecmu \rangle \ge \tau_Y \text{~~and~~ } \forall \vecmu \in K^N, ~~ \langle \veclambda,\vecmu \rangle \le \tau_N \, .
\]

The existence of a separating hyperplane follows from standard convexity (see, e.g., <cit.>). For us this implies there exists $\veclambda' \in \R^{|\cF| \times kq}$ and $\tau'_N < \tau'_Y$ such that

\[
\forall \vecmu \in \kgyf, ~~ \langle \veclambda',\vecmu \rangle \ge \tau'_Y \text{~~and~~ } \forall \vecmu \in \kbnf, ~~ \langle \veclambda',\vecmu \rangle \le \tau'_N \, .
\]

But $\veclambda'$ is not necessarily a positive vector. To remedy this we use the fact that $\kgyf\cup\kbnf$ is contained in a hyperplane whose coefficients are themselves positive. In particular we note that for every $\cD \in \Delta(\cF\times [q]^k)$ we have $\langle\mu(\cD),\mathbf{1}\rangle = k$ where $\mathbf{1} \in \R^{|\cF| \times kq}$ is the all ones vector, as verified below:

\[\langle\mu(\cD),\mathbf{1}\rangle = \sum_{f \in \cF, i \in [k], \sigma\in [q]} \mu_{f,i,\sigma} = \sum_{i \in [k]} \left(\sum_{f \in \cF, \sigma\in [q]} \mu_{f,i,\sigma}\right) = \sum_{i\in[k]} 1 = k. \]

Let $\lambda'_{\min} = \min_{f,t,\sigma } \lambda'_{f,t,\sigma}$. Now let $\veclambda$, $\tau_Y$ and $\tau_N$ be given by:

$$\lambda_{f,t,\sigma} = \lambda'_{f,t,\sigma}+|\lambda'_{\min}|\, , ~~ \tau_Y = \tau'_Y+ k\cdot|\lambda'_{\min}| \mbox{~~and~~} \tau_N=\tau'_N+ k\cdot|\lambda'_{\min}|\, .$$

Observe that $\veclambda$ is a non-negative vector and $\tau_Y>\tau_N$. We also have:

\[
\forall \vecmu \in \kgyf, ~~ \langle \veclambda,\vecmu \rangle =  \langle \veclambda',\vecmu \rangle + |\lambda'_{\mathrm{min}}| \ge \langle \mathbf{1},\vecmu \rangle \geq \tau'_Y + k|\lambda'_{\min}| = \tau_Y \]

as desired. Similarly also get
$\forall \vecmu \in \kbnf, ~~ \langle \veclambda,\vecmu \rangle \le \tau_N$, concluding the proof.

(1) Can skip the following discussion since its included in the proof. (2) Need to assert that $K_Y$ and $K_N$ are closed, convex and compact.

Edit: I think the sum of marginals is not 1. It must be $k$
Further, since $\vecmu(\cD) = (\mu_{f,i,\sigma})_{f\in\cF,i \in [k], \sigma\in [q]}$ is given by $\mu_{f,i,\sigma} = \Pr_{(g,\veca) \sim \cD} [ g = f \mbox{ and }a_i = \sigma]$, we have

\[
\forall \vecmu \in \kgyf, ~~ \langle \mathbf{1^{|\cF|\cdot kq}},\vecmu \rangle = k \text{~~and~~ } \forall \vecmu \in \kbnf, ~~ \langle \mathbf{1^{|\cF|\cdot kq}},\vecmu \rangle =  k \, ,
\]
we get the following stronger form of the above proposition.

For real numbers $0\le \beta < \gamma \le 1$ such that $\kgyf \cap \kbnf = \emptyset$, there exists a non-negative vector $\veclambda = (\lambda_{f,i,\sigma})_{f\in\cF,i \in [k], \sigma\in [q]}$ and real numbers $\tau_Y > \tau_N$ such that

\[
\forall \vecmu \in \kgyf, ~~ \langle \veclambda,\vecmu \rangle \ge \tau_Y \text{~~and~~ } \forall \vecmu \in \kbnf, ~~ \langle \veclambda,\vecmu \rangle \le \tau_N \, .
\]

By <ref>, there exists a non-zero vector $\veclambda$ and real numbers $\tau_Y>\tau_N$ such that

\[
\forall \vecmu \in \kgyf, ~~ \langle \veclambda,\vecmu \rangle \ge \tau_Y \text{~~and~~ } \forall \vecmu \in \kbnf, ~~ \langle \veclambda,\vecmu \rangle \le \tau_N \, .
\]
Let $\lambda_{\min} = \min_{f,t,\sigma } \lambda_{f,t,\sigma}$. Now consider the vector $\veclambda'\in \mathbb{R}^{|\cF|\cdot kq}$ such that $\lambda'_{f,t,\sigma} = \lambda_{f,t,\sigma}+|\lambda_{\min}|$. Observe that $\veclambda'$ is a non-negative vector and for $\tau_Y' = \tau_Y+ k\cdot|\lambda_{\min}|$ and $\tau_N'=\tau_N+ k\cdot|\lambda_{\min}|$, where $\tau_Y'>\tau_N'$, we have

\[
\forall \vecmu \in \kgyf, ~~ \langle \veclambda',\vecmu \rangle \ge \tau_Y' \text{~~and~~ } \forall \vecmu \in \kbnf, ~~ \langle \veclambda',\vecmu \rangle \le \tau_N' \, .
\]

To use the vector $\veclambda$ given by <ref> we introduce the notion of the bias matrix and the bias of a $\maxF$ instance $\Psi$.

For a non-negative vector $\veclambda = (\lambda_{f,i,\sigma})_{f\in\cF,i \in [k], \sigma\in [q]} \in \R^{|\cF|kq}$, and instance $\Psi = (C_1,\ldots,C_m;w_1,\ldots,w_m)$ of $\maxF$ where $C_i = (f_i,\vecj(i))$, where $f_i\in \cF$ and $\vecj(i)\in [n]^k$, we let the $\veclambda$-bias matrix of $\Psi$, denoted $\bias_{\veclambda}(\Psi)$, be the matrix in $\R^{n\times q}$ given by

\[
\bias_{\veclambda}(\Psi)_{\ell,\sigma} = \frac{1}W \cdot \sum_{i \in [m], t \in [k] : \vecj(i)_t = \ell} \lambda_{f_i,t,\sigma} \cdot w_i \, ,
\]

for $\ell \in [n]$ and $\sigma \in [q]$, where $W=\sum_{i\in [m]} w_i$. The $\veclambda$-bias of $\Psi$, denoted $B_{\veclambda}(\Psi)$, is defined as $B_{\veclambda}(\Psi) = \sum_{\ell=1}^n \max_{\sigma\in [q]} \bias_{\veclambda}(\Psi)_{\ell,\sigma}$.

Key to our algorithm for approximating $\maxF$ is the following algorithm to compute the $\ell_{1,\infty}$ norm of a matrix. Recall that for a matrix $M \in \R^{a \times b}$ the $\ell_{1,\infty}$ norm is the quantity $\|M\|_{1,\infty} = \sum_{i \in [a]} \{\max_{j \in {[b]}} \{|M_{ij}|\}\}$.

There exists a constant $c$ such that the $\ell_{1,\infty}$ norm of an $n \times q$ matrix $M$ can be estimated by a linear sketch to within a multiplicative error of $(1+\epsilon)$ in the turnstile streaming model with $O(\epsilon^{-c} \cdot q \cdot  \log^2 n)$ words (or with $O(\epsilon^{-c} \cdot q \cdot  \log^3 n)$ bits).

From our email

We note that Theorem 4.5 in [1] is much more general. <ref> is the special case corresponding to $X = \ell_{\infty}$ and $E_X$ being simply the identity function. $\alpha(\cdots)$ in this case turns out to be $O(\log n)$ leading to the bounds above [3].

Note that there is a slight distinction between the definitions of $B_{\veclambda}(\Psi)$ and $\|\bias_{\veclambda}(\Psi)\|_{1,\infty}$, but these quantities are equal since $\bias_{\veclambda}$ is a non-negative matrix (which in turn follows from the fact that $\veclambda$ is non-negative). We thus get the following corollary.

There exists a constant $c$ such that for every $k,q,\cF$ and $\epsilon > 0$, there exists a linear sketching streaming algorithm running in space $O(\epsilon^{-c} \cdot \log^3 n)$ that on input a stream $\sigma_1,\ldots,\sigma_\ell$ representing a $\maxF$ instance $\Psi = (C_1,\ldots,C_m;w_1,\ldots,w_m)$ on $n$ variables, outputs a $(1\pm\epsilon)$ approximation to $B_{\veclambda}(\Psi)$.

We need to cite algorithms for computing bias in the streaming model

Need lemma asserting that $\lambda$-bias can be computed in polylog space. Lemma will cite some result from the literature, which should be stated explicitly as a theorem. placeholders below.

Bias can be approximated to within $1+\epsilon$ in space $\poly(\epsilon^{-1} \log n)$ space.

Matrix norms can be approximated ...

We are now ready to describe our algorithm for $(\gamma,\beta)$-$\maxF$.

A streaming algorithm for $(\gamma,\beta)$-$\maxF$

[1]
A stream $\sigma_1,\ldots,\sigma_\ell$ representing an instance $\Psi$ of $\maxF$.
Let $\veclambda \in \R^{|\cF|kq},\tau_N$ and $\tau_Y$ be as given by <ref> separating $K_\gamma^Y(f)$ and $K_\beta^N(f)$, so $\veclambda$ is non-negative and $\tau_N < \tau_Y$.
Let $\epsilon = \frac{\tau_Y-\tau_N}{2(\tau_Y+\tau_N)}$.
Using <ref> compute a $(1\pm\epsilon)$ approximation $\tilde{B}$ to $B_{\veclambda}(\Psi)$, i.e.,

$$(1-\epsilon)B_{\veclambda}(\Psi) \leq \tilde{B} \leq (1+\epsilon)B_{\veclambda}(\Psi) \mbox{ with probability at least $2/3$}.$$

$\tilde{B} \leq \tau_N (1+\epsilon)$
Output: NO.
Output: YES.

Given <ref> it follows that the algorithm above uses space $O(\log^3 n)$ on instances on $n$ variables. In what follows we prove that the algorithm correctly solves $(\gamma,\beta)-\maxF$.

§.§ Analysis of the correctness of <ref>

<ref> correctly solves $(\gamma,\beta)$-$\maxF$, if $K_\gamma^Y(\cF)$ and $K_\beta^N(\cF)$ are disjoint.
Specifically, for every $\Psi$, let $\tau_Y,\tau_N,\epsilon,\veclambda,\tilde{B}$ be as given in <ref>, we have:

\begin{eqnarray*}
\val_\Psi \geq \gamma & \Rightarrow & B_{\veclambda}(\Psi) \geq \tau_Y \mbox{ and } \tilde{B} > \tau_N(1+\epsilon) \, , \\
\mbox{ and } \val_\Psi \leq \beta & \Rightarrow & B_{\veclambda}(\Psi) \leq \tau_N \mbox{ and } \tilde{B} \leq \tau_N(1+\epsilon) \, ,
\end{eqnarray*}

provided $(1-\epsilon)B_\lambda(\Psi) \leq \tilde{B} \leq (1+\epsilon)B_\lambda(\Psi)$.

In the rest of this section, we will prove <ref>.
The key to our analysis is a distribution $\cD(\Psi^\vecb) \in \Delta(\cF \times [q]^k)$ that we associate with every instance $\Psi$ and assignment $\vecb\in [q]^{n}$ to the variables of $\Psi$.
If $\Psi$ is $\gamma$-satisfied by assignment $\vecb$, we prove that $\vecmu(\cD(\Psi^\vecb)) \in K_\gamma^Y(\cF)$. On the other hand, if $\Psi$ is not $\beta$-satisfiable by any assignment, we prove that for every $\vecb$, $\vecmu(\cD(\Psi^\vecb)) \in K_\beta^N(\cF)$. Finally we also show that the bias $B_{\veclambda}(\Psi)$ relates to $\veclambda(\cD(\Psi^\vecb)) \triangleq \langle\vecmu(\cD(\Psi^\vecb), \veclambda \rangle$, where the latter quantity is exactly what needs to be computed (by <ref>) to distinguish the membership of $\vecmu(\cD(\Psi^\vecb))$ in $K_\gamma^Y(\cF)$ versus the membership in $K_\beta^N(\cF)$.

=0 We note that the analysis follows the same route as in [8]. The key step is the definition of these distributions that allows the remaining steps (esp. <ref>) to be extended, which we present now.

Given an instance $\Psi=(C_1,\ldots,C_m;w_1,\ldots,w_m)$ on $n$ variables with $C_i = (f_i,\vecj(i))$ and an assignment $\vecb \in [q]^{n}$, the distribution $\cD(\Psi^\vecb) \in \Delta(\cF \times [q]^k)$ is sampled as follows: Sample $i \in [m]$ with probability $w_i/W$ where $W=\sum_{i\in [m]} w_i$, and output $(f_i,\vecb\mid_{\vecj(i)})$.

We start by relating the bias $B_{\veclambda(\Psi)}$ to $\cD(\Psi)$.

For every vector $\vecb\in[q]^{n}$, we have $\veclambda(\cD(\Psi^\vecb)) = \sum_{\ell=1}^n \bias_{\veclambda}(\Psi)_{\ell,b_\ell} $. Consequently we have $B_{\veclambda}(\Psi) = \sum_{\ell=1}^n \max_{\sigma\in [q]} \bias_{\veclambda}(\Psi)_{\ell,\sigma} = \max_{\vecb\in [q]^{n}} \{ {\veclambda}(\cD(\Psi^\vecb)) \}$.

We start with the first equality. Fix $b\in [q]^n$. Given $f\in \cF$, $t\in [k]$, and $\sigma\in [q]$, we have
$\mu(\cD(\Psi^\vecb))_{f,t,\sigma} = \frac{1}{W} \sum_{i=1}^m w_i \cdot \mathbbm{1}[f_i=f, b_{j(i)_t}=\sigma]$. Hence,

\begin{align*}
\veclambda(\cD(\Psi^\vecb)) &= \sum_{f\in \cF,t\in[k],\sigma\in[q]} \mu(\cD(\Psi^\vecb))_{f,t,\sigma} \cdot  \lambda_{f,t,\sigma}\\
&= \frac{1}{W} \sum_{f\in\cF,t\in[k],\sigma\in[q]} \sum_{i\in [m]}w_i \cdot \mathbbm{1}[f_i=f, b_{j(i)_t}=\sigma] \cdot \lambda_{f,t,\sigma}\\
&= \frac{1}{W} \sum_{i\in[m],t\in[k],\sigma\in[q]:b_{j(i)_t}=\sigma} w_i \cdot \lambda_{f_i,t,\sigma}\\
&=  \sum_{\ell=1}^n \frac{1}{W} \sum_{i\in[m],t\in[k]:j(i)_t=l} w_i \cdot \lambda_{f_i,t,b_l}\\
&= \sum_{\ell=1}^n \bias_{\veclambda}(\Psi)_{\ell,b_\ell} \, . \\
\end{align*}

For the final equality, observe that

\[
B_{\veclambda}(\Psi) = \sum_{\ell=1}^n \max_{\sigma\in [q]} \bias_{\veclambda}(\Psi)_{\ell,\sigma} = \max_{\vecb\in [q]^{n}}\sum_{\ell=1}^n \bias_{\veclambda}(\Psi)_{\ell,b_\ell} = \max_{\vecb\in [q]^{n}} \{ {\veclambda}(\cD(\Psi^\vecb)) \} \, .
\]

The following lemmas relate $\val_\Psi$ to the properties of $\cD(\Psi^\veca)$.

For every $\Psi\in \maxF$ and $\vecb\in [q]^{n}$, if $\val_\Psi(\vecb) \geq \gamma$ then $\cD(\Psi^\vecb) \in S_\gamma^Y(\cF)$.

Follows from the fact that

\[
\Exp_{(f,\veca)\sim \cD(\Psi^\vecb)}[C(f,a)(\canon)] = \frac{1}{W}\sum_{i=1}^m w_i \cdot f_i(b\mid_{j(i)}) = \val_\Psi(\vecb) \ge \gamma,
\]

implying $\cD(\Psi^\vecb) \in S_\gamma^Y(\cF)$.

For every $\Psi\in \maxF$, if $\val_{\Psi} \leq \beta$, then for all $\vecb\in [q]^{n}$, we have $\cD(\Psi^\vecb) \in S_\beta^N(\cF)$.

We prove the contrapositive. We assume that $\exists \vecb\in [q]^n$ such that $\cD(\Psi^\vecb) \notin S_\beta^N(\cF)$ and show this implies $\val_{\Psi} > \beta$. Then there exists $(P_\sigma\in \Delta([q]))_{\sigma \in [q]}$ such that $\Exp_{(f,a)\sim \cD(\Psi^\vecb)} \left[\Exp_{\vecc, c_{i,\sigma} \sim \cP_\sigma} [\cC(f,\veca)(\vecc)]\right] > \beta$.

We thus have

\begin{eqnarray*}
\beta & < & \Exp_{(f,a)\sim \cD(\Psi^\vecb)} \left[\Exp_{\vecc, c_{i,\sigma} \sim \cP_\sigma} [\cC(f,\veca)(\vecc)]\right] \\
&= &\Exp_{\vecc, c_{i,\sigma} \sim \cP_\sigma} \left[\Exp_{(f,a)\sim \cD(\Psi^\vecb)} [\cC(f,\veca)(\vecc)]\right]\\
&= &\Exp_{\vecc, c_{i,\sigma} \sim \cP_\sigma} \left[\frac{1}{W} \sum_{i=1}^m w_i \cdot f_i((c_{t,b_{j(i)_t}})_{t\in[k]})\right]\\
&= &\frac{1}{W}\sum_{i=1}^m w_i \cdot \Exp_{\vecc, c_{i,\sigma} \sim \cP_\sigma} \left[ f_i((c_{t,b_{j(i)_t}})_{t\in[k]})\right]\\
&= &\frac{1}{W}\sum_{i=1}^m w_i \cdot \Exp_{\vecx, x_{\ell} \sim \cP_{b_{\ell}}}\left[ f_i((x_{j(i)_t})_{t\in[k]})\right]\\
&= &\Exp_{\vecx, x_{\ell} \sim \cP_{b_{\ell}}} \left[\frac{1}{W}\sum_{i=1}^m w_i \cdot f_i((x_{j(i)_t})_{t\in[k]})\right]\\
&= & \Exp_{\vecx, x_{\ell} \sim \cP_{b_{\ell}}}\left[\val_{\Psi}(\vecx)\right]\\
& \leq & \max_{\vecx \in [q]^n} \val_\Psi(\vecx) \\
& = & \val_\Psi\,
\end{eqnarray*}

which contradicts the assumption that $\val_\Psi\le \beta$. This concludes the proof of the claim and hence the lemma.

=0As in [8], the key step among the equalities above is the one asserting  $\frac{1}{W}\sum_{i=1}^m w_i \cdot \Exp_{\vecc, c_{i,\sigma} \sim \cP_\sigma} \left[ f_i((c_{t,b_{j(i)_t}})_{t\in[k]})\right] = \frac{1}{W}\sum_{i=1}^m w_i \cdot \Exp_{\vecx, x_{\ell} \sim \cP_{b_{\ell}}}\left[ f_i((x_{j(i)_t})_{t\in[k]})\right]$ which relies crucially on column symmetry of the distributions used in the definition of $\sbnf$ in <ref>.=1The key step among the equalities above is the one asserting  $\frac{1}{W}\sum_{i=1}^m w_i \cdot \Exp_{\vecc, c_{i,\sigma} \sim \cP_\sigma} \left[ f_i((c_{t,b_{j(i)_t}})_{t\in[k]})\right] = \frac{1}{W}\sum_{i=1}^m w_i \cdot \Exp_{\vecx, x_{\ell} \sim \cP_{b_{\ell}}}\left[ f_i((x_{j(i)_t})_{t\in[k]})\right]$ which relies crucially on column symmetry of the distributions used in the definition of $\sbnf$ in <ref>.Without this restriction, or even more stringent ones, this step of the rounding would fail.
And the reason we can't use a more stringent restriction will become clear in the proof of <ref> (and is specifically used in the proof of <ref>).
We also note that

this key  equality relies on the assumption that the variables in a single constraint are distinct. In particular the left hand side assumes $c_{i,\sigma}$s are drawn independently whereas the right side allows this only for the distinct variables $x_\ell$ in a constraint.

§ SKETCHING AND STREAMING SPACE LOWER BOUNDS FOR MAX-CSP(F)

In this section, we prove our two lower bound results, modulo a communication complexity lower bound which is proved in <ref>. We start by restating the results to be proved. Recall (from <ref>) the notion of a padded one-wise pair of distributions:  $(\cD_1,\cD_2)$ is a padded one-wise pair if there exist $\cD_0,\cD'_1,\cD'_2$ and $\tau \in [0,1]$ such that for every $i \in \{1,2\}, \cD'_i$ is one-wise independent, and $\cD_i = \tau \cD_0 + (1-\tau) \cD'_i$.

The first theorem we prove is the lower bound in the streaming setting for padded one-wise pairs of distributions. We restate the theorem below for convenience.

We also restate the lower bound against sketching algorithms from <ref> as a separate theorem below.

For every $q,k \in \N$, every family of functions $\cF \subseteq \{f:[q]^k \to \{0,1\}\}$ and for every $0 \leq \beta<\gamma \leq 1$, if $\kgyf \cap \kbnf \neq \emptyset$, then for every $\epsilon>0$, any sketching algorithm for the $(\gamma-\eps,\beta+\eps)$-$\maxF$ problem requires $\Omega(\sqrt{n})$ space.
Furthermore, if $\gamma = 1$, then any sketching algorithm for $(1,\beta+\epsilon)$-$\maxF$ requires $\Omega(\sqrt{n})$ space.

To prove both theorems, we introduce a new communication game we call the  Signal Detection (SD) in <ref>. In <ref> we state a lower bound on the communication complexity of this problem. This lower bound is established in <ref>. We then use this lower bound to prove <ref> in <ref> and to prove <ref> in <ref>.

The roadmap of our lower bounds. The top two rows describe the results of this section, while the remaining rows describe notions and results from <ref>.

§.§ The Signal Detection Problem and Results

In this section we introduce our communication game and state the lower bound for this game.
We start with the definition of a general one-way communication game.

Given two distributions $\cY$ and $\cN$, an instance of the two-player one-way communication game is a pair $(X,Y)$ either drawn from $\cY$ or from $\cN$. Two computationally unbounded parties, Alice and Bob, receive $X$ and $Y$, respectively. A protocol $\Pi = (\Pi_A,\Pi_B)$ is a pair of functions with $\Pi_A(X) \in \{0,1\}^c$ denoting Alice's message to Bob, and $\Pi_B(\Pi_A(X),Y)\in \{\yes,\no\}$ denoting the protocol's output. We denote this output by $\Pi(X,Y)$. The complexity of this protocol is the parameter $c$ specifying the maximum length of Alice's message $\Pi_A(X)$. The advantage of the protocol $\Pi$ is the quantity

\[
\left| \Pr_{(X,Y)\sim\cY} [ \Pi(X,Y) = \yes] - \Pr_{(X,Y)\sim \cN} [\Pi(X,Y) = \yes] \right| \,.
\]

We now define the specific game we are interested in.

Let $n,k,q\in\mathbb{N}, \alpha\in(0,1)$, where $k$, $q$ and $\alpha$ are constants with respect to $n$, and $\alpha n$ is an integer less than $n/k$. Let $\cF$ be a finite set.

For a pair $\cD_Y$ and $\cD_N$ of distributions over $\cF \times [q]^k$, we consider the following two-player one-way communication problem $(\cF,\cD_Y,\cD_N)$-.

* The generator samples the following objects:

* $\vecx^* \sim \textsf{Unif}([q]^n)$.

* $M \in \{0,1\}^{k\alpha n \times n}$ is chosen uniformly among all matrices with exactly one $1$ in each row and at most one $1$ in each column. We let $M = (M_1,\ldots,M_{\alpha n})$ where $M_i \in \{0,1\}^{k \times n}$ is the $i$-th block of rows of $M$, where each block has exactly $k$ rows.

* $\vecb = (\vecb(1),\ldots,\vecb(\alpha n))$ is sampled from one of the following distributions:

* () each $\vecb(i) = (f_i,\widetilde{\vecb}(i)) \in \cF \times [q]^k$ is sampled according to $\cD_Y$.

* () each $\vecb(i) = (f_i,\widetilde{\vecb}(i)) \in \cF \times [q]^k$ is sampled according to $\cD_N$.

* $\vecz = (\vecz(1),\ldots,\vecz(\alpha n))$
is determined from $M$, $\vecx^*$ and $\vecb= (\vecb(1),\dots,\vecb(\alpha n))$ as follows. Recall that $\vecb(i)=(f_i,\widetilde{\vecb}(i))$.
We let $\vecz(i) = (f_i,\widetilde{z}_i) \in \cF \times \{0,1\}$ where $\widetilde{z}_i = 1$ iff $M_i \vecx^* = \widetilde{\vecb}(i)$.

* Alice receives $\vecx^*$ as input.

* Bob receives $M$ and $\vecz$ as input.

In the special case when the set $\cF$ contains just one element, $|\cF|=1$, we call the corresponding communication problem  $(\cD_Y,\cD_N)$-.

We note that our communication game is slightly different from those in previous works: Specifically the problem studied in [12, 18] is called the Boolean Hidden Matching (BHM) problem from [12] and the works [19, 16] study a variant called the Implicit Hidden Partition problem. While these problems are similar, they are less expressive than our formulation, and specifically do not seem to capture the many different all $\maxf$ problems.

There are two main differences between the previous settings and our setting. The first difference is the way to encode the matching matrix $M$. In all the previous works, each edge (or hyperedge) is encoded by a single row in $M$ where the corresponding columns are assigned to $1$, so that $m = \alpha n$. However, it turns out that this encoding hides too much information and hence we do not know how to reduce the problem to general . We unfold the encoding by using $k$ rows to encode a single $k$-hyperedge (leading to the setting of $m = k\alpha n$ in our case). The second difference is that we allow the masking vector $\vecb$ to be sampled from a more general distribution. This is also for the purpose of establishing a reduction to general . Due to the above two differences, it is not clear how to derive communication lower bounds for general $\cD_Y$ and $\cD_N$ by reduction from the previous works.

[Communication lower bound for $(\cF, \cD_Y,\cD_N)$-]theoremreducermdtosd
For every $k,q$, every finite set $\cF$, every pair of distributions $\cD_Y,\cD_N \in \Delta(\cF\times[q]^k)$ with $\vecmu(\cD_Y) = \vecmu(\cD_N)$ there exists $\alpha_0 > 0$ such that for every $0<\alpha \leq \alpha_0$ and $\delta > 0$ there exists $\tau > 0$ such that the following holds: Every protocol for $(\cF, \cD_Y,\cD_N)$-SD achieving advantage $\delta$ on instances of length $n$ requires $\tau\sqrt{n}$ bits of communication.

<ref> are devoted to proving
<ref>. The specific proof can be found in <ref>.
In the rest of this section we assume this theorem to prove <ref>.

Can insert subsubsection with discussion on communication problems here .

PAsted the relevenat stuff from other paper here. Need to determine what needs to be said and where.

We note that our communication game is slightly different from those in previous works: Specifically the problem studied in [12, 18] is called the Boolean Hidden Matching (BHM) problem from [12] and the works [19, 16] study a variant called the Implicit Hidden Partition problem. While these problems are similar, they are less expressive than our formulation, and specifically do not seem to capture all $\maxf$ problems.

There are two main differences between the previous settings and our setting. The first difference is the way to encode the matching matrix $M$. In all the previous works, each edge (or hyperedge) is encoded by a single row in $M$ where the corresponding columns are assigned to $1$, so that $m = \alpha n$. However, it turns out that this encoding hides too much information and hence we do not know how to reduce the problem to general . We unfold the encoding by using $k$ rows to encode a single $k$-hyperedge (leading to the setting of $m = k\alpha n$ in our case). The second difference is that we allow the masking vector $\vecb$ to be sampled from a more general distribution. This is also for the purpose of establishing a reduction to general .
That being said, it is possible to describe some of the previous results in our language: all the papers consider the complexity of distinguishing the distribution $\cD_Y = \textsf{Unif}(\{(1,1),(-1,-1)\})$ from the distribution $\cD_N = \textsf{Unif}(\{-1,1\}^2)$. This problem is shown to have a communication lower bound of $\Omega(\sqrt{n})$ in [12]. And a variant of this problem (not captured by our formulation above) is shown to have an $\Omega(n)$ lower bound in [16].

Due to the above two differences, it is not clear how to derive communication lower bounds for general $\cD_Y$ and $\cD_N$ by reduction from the previous works.
The main technical contribution of this part of the paper is a communication lower bound for  for general $\cD_Y$ and $\cD_N$. We summarize the result in the following theorem.

§.§ The streaming lower bound

The hardness of  suggests a natural path for hardness of $\maxF$ problems in the streaming setting. Such a reduction would take two distributions $\cD_Y \in S_\gamma^Y$ and $\cD_N \in S_\beta^N$ with matching marginals, construct  distributions $\cY$ and $\cN$ of , and then interpret these distributions (in a natural way) as distributions over instances of $\maxf$ that are indistinguishable to small space algorithms. While the exact details of this “interpretation” need to be spelled out, every step in this path can be achieved. Unfortunately this does not mean any hardness for $\maxf$ since the CSPs generated by this reduction would consist of instances that have at most one constraint per variable, and such instances are easy to solve!

To go from the instance suggested by the   problem to hard CSP instances, we instead pick $T$ samples (somewhat) independently from the distributions $\cY$ and $\cN$ suggested by the  problem and concatenate these. With an appropriate implementation of this notion (see <ref>) it turns out it is possible to use the membership of the underlying distributions in $S^Y_\gamma$ and $S^N_\beta$ to argue that the resulting instances $\Psi$ do (almost always) have $\val_\Psi \geq \gamma$ or $\val_\Psi \leq \beta$. (We prove this after appropriate definitions in <ref>.) But now to one needs to connect the streaming problem generated from the $T$-fold sampled version to the SD problem.

To this end we formalize the $T$-fold streaming problem, which we call $(\cD_Y,\cD_N,T)$ problem, in <ref>. Unfortunately, we are not able to reduce the $(\cD_Y, \cD_N)$ problem to $(\cD_Y,\cD_N,T)$ problem for all
$\cD_Y$ and $\cD_N$. (Roughly this problem arises from the fact that the $T$ samples $(\vecx^{*}(t),M(t),\vecz(t))$ are not sampled independently from $\cY$ (or $\cN$ for $t \in [T]$). Instead they are sampled independently conditioned on $\vecx^*(1) = \cdots = \vecx^*(T)$. This hidden correlation in both the  and the  cases turns out to be a serious problem.) But in the setting where $\cD_Y$ and $\cD_N$ have uniform marginals then we are able to effect the reduction and thus show that the streaming problem requires large space. This is a special case of <ref> which we discuss next.

We are able to extend our reduction from  to  slightly beyond the uniform marginal case, to the case where $\cD_Y$ and $\cD_N$ form a padded one-wise pair, but both the streaming problem and the analysis of the resulting CSP value need to be altered to deal with this case, as elaborated next. Let $\tau \in [0,1]$ and $\cD_0, \cD'_Y, \cD'_N$ be such that for $i \in \{Y,N\}$ we have $\cD_i = \tau \cD_0+ (1-\tau)\cD'_i$ and $\cD'_i$ has uniform marginals. Our padded streaming problem, denoted $(\cD'_Y,\cD'_N,T,\cD_0,\tau)$ problem, includes an appropriately large number of constraints generated according to $\cD_0$, followed by $T$ samples chosen according to the $(\cD'_Y,\cD'_N,T)$ problem. See <ref> for a formal definition. In <ref> we show that the CSP value of the resulting streaming problem inherits the properties of $\cD_Y$ and $\cD_N$ (which is not as immediate for  as for ). We then show effectively that $(\cD'_Y,\cD'_N)$- reduces to $(\cD'_Y,\cD'_N,T,\cD_0,\tau)$. See <ref>. Putting these together leads to a proof of <ref>.

In this section we introduce two streaming problems, the $(\cF, \cD_Y,\cD_N,T)$- problem and the $(\cF, \cD_Y,\cD_N,T,\cD_0,\tau)$- problem in <ref>, where the new parameter $T$ is an integer (a large constant) that represents the number of “parts” in a stream. We then show how to reduce these problems to $\maxF$ problems so that membership of $\cD_Y \in \sgyf$ and $\cD_N \in \sbnf$ leads to a gap in the value of the instances produced by this reduction for large $T$. (See <ref>.) We then show that the lower bounds on the one-way communication complexity of $(\cF, \cD_Y,\cD_N)$- translate into lower bounds on the space complexity of
$(\cF, \cD_Y,\cD_N,T)$-. (See <ref>.) Combining these lemmas leads immediately to a proof of <ref> in <ref>.

§.§.§ The (Padded) Streaming SD Problem

For $k,q,T\in\mathbb{N}$, $\alpha\in(0,1/k]$, a finite set $\cF$ and distributions $\cD_Y,\cD_N$ over $\cF\times[q]^k$, the streaming problem $(\cF,\cD_Y,\cD_N,T; \alpha,k,q)$- is the task of distinguishing, for every $n$, $\vecsigma \sim \cY_{\strm,n}$ from $\vecsigma \sim \cN_{\strm,n}$ where for a given length parameter $n$, the distributions $\cY_\strm = \cY_{\strm,n}$ and $\cN_\strm=\cN_{\strm,n}$ are defined as follows:

* Let $\cY$ be the distribution over instances of length $n$, i.e., triples $(\vecx^*,M,\vecz)$, from the definition of $(\cF,\cD_Y,\cD_N)$-. For $\vecx \in [q]^n$, let $\cY|_\vecx$ denote the distribution $\cY$ conditioned on $\vecx^* = \vecx$. The stream $\vecsigma\sim\cY_\strm$ is sampled as follows: Sample $\vecx^*$ uniformly from $[q]^n$. Let $(M^{(1)},\vecz^{(1)}),\ldots,(M^{(T)},\vecz^{(T)})$ be sampled independently according to $\cY|_{\vecx^*}$. Let $\vecsigma^{(t)}$ be the pair $(M^{(t)},\vecz^{(t)})$ presented as a stream of edges with labels in $\cF\times\{0,1\}$, i.e., $\vecz^{(t)}=(f_i,\tilde{z}_i)$. Specifically for $t \in [T]$ and $i \in [\alpha n]$, let $\vecsigma^{(t)}(i) = (e^{(t)}(i),\vecz^{(t)}(i))$ where $e^{(t)}(i)$ is the $i$-th hyperedge of $M^{(t)}$, i.e., $e^{(t)}(i) = (j^{(t)}(k(i-1)+1),\ldots,j^{(t)}(k(i-1)+k)$ and $j^{(t)}(\ell)$ is the unique index $j$ such that $M^{(t)}_{j,\ell} = 1$. Finally we let $\vecsigma = \vecsigma^{(1)} \circ \cdots \circ \vecsigma^{(T)}$ be the concatenation of the $\vecsigma^{(t)}$s.

* $\vecsigma\sim\cN_\strm$ is sampled similarly except we now sample $(M^{(1)},\vecz^{(1)}),\ldots,(M^{(T)},\vecz^{(T)})$  independently according to $\cN|_{\vecx^*}$ where $\cN|_\vecx$ is the distribution $\cN$ condition on $\vecx^* = \vecx$.

Again when $\alpha,k,q$ are clear from context we suppress them and simply refer to the $(\cF,\cD_Y,\cD_N,T)$- problem.

We note that when $\cD_N = \cD_\cF\times\textsf{Unif}([q]^k)$ for some $\cD_\cF\in\Delta(\cF)$, then the distributions $\cN|_{\vecx^*}$ are identical for all $\vecx^*$ (and the variables
$\vecz^{(t)}(i)$ are distributed as $\cD_\cF\times\bern(q^{-k})$ independently for every $t,i$).

For technical reasons, we need the following padded version of  to extend our lower bound techniques in the streaming setting beyond the setting of one-wise independent distributions.

For $k,q,T\in\mathbb{N}$, $\alpha\in(0,1/k]$, $\tau\in[0,1)$, a finite set $\cF$, and distributions $\cD_Y,\cD_N,\cD_0$ over $\cF\times[q]^k$, the streaming problem $(\cF, \cD_Y,\cD_N,T,\cD_0,\tau; \alpha,k,q)$- is the task of distinguishing, for every $n$, $\vecsigma \sim \cY_{\pstrm,n}$ from $\vecsigma \sim \cN_{\pstrm,n}$ where for a given length parameter $n$, the distributions $\cY_\pstrm = \cY_{\pstrm,n}$ and $\cN_\pstrm=\cN_{\pstrm,n}$ are defined as follows: Sample $\vecx^*$ from $[q]^n$ uniformly. For each $i\in[\frac{\tau}{1-\tau}\alpha nT]$, uniformly sample a tuple $e^{(0)}(i)=(i_1,\dots,i_k)\in\binom{[n]}{k}$ and $(f_i,\vecb^{(0)}(i))\sim\cD_0$, let $\vecsigma^{(0)}(i)=(e^{(0)}(i),(f_i,\mathbf{1}_{\vecb^{(0)}(i)=\vecx^*|_{e^{(0)}(i)}}))$. Next, sample $\vecsigma^{(1)},\dots,\vecsigma^{(T)}$ according to the Yes and No distribution of $(\cF, \cD_Y,\cD_N,T)$- respectively. Finally, let $\vecsigma = \vecsigma^{(0)} \circ \cdots \circ \vecsigma^{(T)}$ be the concatenation of the $\vecsigma^{(t)}$s.

Again when $\alpha,k,q$ are clear from context we suppress them and simply refer to the $(\cF,\cD_Y,\cD_N,T,\cD_0,\tau)$- problem.
Note that when $\tau=0$, $(\cF,\cD_Y,\cD_N,T,\cD_0,\tau)$- is the same as $(\cF,\cD_Y,\cD_N,T)$-.

§.§.§ CSP value of

There is a natural way to convert instances of  to instances of a $\maxF$ problem. In this section we make this conversion explicit and show to use properties of the underlying distributions $\cD_0,\cD_Y,\cD_N$ to get bounds on the value of the instances produced.

Note that an instance $\vecsigma$ of  is simply a sequence $(\sigma(1),\ldots,\sigma(\ell))$
where each $\sigma(i) = (\vecj(i),\vecz(i))$ with $\vecj(i) \in [n]^k$ and $\vecz(i)=(f_i,\tilde{z}_i) \in \cF\times\{0,1\}$. This sequence is already syntactically very close to the description of a $\maxF$ instance.
Formally, we define an instance $\Psi(\vecsigma)$ of $\maxF$ as follows. For each $\sigma_i=(\vecj(i),\vecz(i))$ with $\vecz(i)=(f_i,\tilde{z}_i)$, if $\tilde{z}_i=1$ we add the constraint $f_i(\vecx|_{\vecj(i)})$ to $\Psi(\vecsigma)$; otherwise, we do not add any constraint to the formula.

In what follows we show that if $\cD_Y \in S_\gamma^Y$ then for all sufficiently large constant $T$, and sufficiently large $n$, if we draw $\vecsigma \sim \cY_{\pstrm,n}$, then with high probability, $\Psi(\vecsigma)$ has value at least $\gamma-o(1)$. Conversely if $\cD_N \in S_\beta^N$, then for all sufficiently large $n$, if we draw $\vecsigma \sim \cN_{\pstrm,n}$, then with high probability $\Psi(\vecsigma)$ has value at most $\beta+o(1)$.

For every $q,k\in\mathbb{N}$, $\cF \subseteq \{f:[q]^k \to \{0,1\}\}$,  $0 \leq \beta < \gamma \leq 1$, $\epsilon > 0$, $\tau=[0,1)$, and distributions $\cD_Y, \cD_N, \cD_0 \in \Delta(\{-1,1\}^k)$ there exists $\alpha_0$ such that for every $\alpha\in(0,\alpha_0]$ the following hold for every sufficiently large $T$:

* If $\tau\cD_0+(1-\tau)\cD_Y \in S_\gamma^Y$, then for every sufficiently large $n$, the $(\cF, \cD_Y,\cD_N,T,\cD_0,\tau)$-  instance $\vecsigma \sim \cY_{\pstrm,n}$ satisfies $\Pr[\val_{\Psi(\vecsigma)} < (\gamma-\epsilon)] \leq \exp(-n)$.[In this lemma and proof we use $\exp(-n)$ to denote functions of the form $c^{-n}$ for some $c>1$ that does not depend on $n$ or $T$, but may depend on all other parameters including $q,k,\cD_Y,\cD_N,\cD_0,\beta,\gamma,\epsilon$.]

* If $\tau\cD_0+(1-\tau)\cD_N \in S_\beta^N$, then for every sufficiently large $n$, the $(\cF, \cD_Y,\cD_N,T,\cD_0,\tau)$-  instance $\vecsigma \sim \cN_{\pstrm,n}$ satisfies $\Pr[\val_{\Psi(\vecsigma)} > (\beta+\epsilon)] \leq \exp(-n)$.

Furthermore, if $\gamma = 1$ then $\Pr_{\vecsigma\sim\cY_{\pstrm,n}}\left[\val_{\Psi(\vecsigma)}=1\right]=1$.

We assume $\eps \leq 1/2$ (and if not we prove the lemma for $\eps'=\frac12$ and this implies the lemma also for $\eps$).
We prove the lemma for $\alpha_0 = \frac{\epsilon}{20kq^k}$ and $T_0 = 1000/(\epsilon^2\alpha)$. In what follows we set $\eta = \frac{\epsilon}{20kq^k}$.

In what follows we let $N_0 = \frac{\tau \alpha n T}{1-\tau}$,  $N_t = \alpha n$ for $t \in [T]$ and $N = N_0 + TN_1$.
Recall that an instance of $(\cF, \cD_Y,\cD_N,T,\cD_0,\tau)$- consists of a stream $\vecsigma = \vecsigma^{(0)} \circ \cdots \circ \vecsigma^{(T)}$ where $\vecsigma^{(t)} = (\vecsigma^{(t)}(i) | i \in [N_t])$ and $\vecsigma^{(t)}(i)=(e^{(t)}(i),(f^{(t)}_{i},\tilde{z}^{(t)}(i))$ where $e^{(t)}(i)$ denotes a $k$-uniform hyperedge on $[n]$ and $f^{(t)}(i) \in \cF$ and $\tilde{z}^{(t)}(i) \in \{0,1\}$.
Finally recall that $\vecsigma^{(t)} \sim \cY|_{\vecx^*}$ in the  case and $\vecsigma^{(t)} \sim \cN|_{\vecx^*}$ in the  case independently for each $t$, where $\vecx^* \sim \textsf{Unif}([q]^n)$ is common across all $t$.
We use
$\cI = (\{0\} \times [T_0]) \cup ([T] \times [T_1])$ to denote the set of legal pairs of indices $(t,i)$.
We let $m$ denote the total number of constraints in $\Psi(\vecsigma)$ with $m_t$ denoting the number of constraints from $\vecsigma^{(t)}$ for $0 \leq t\leq T$. (Note that $m$ and the $m_t$'s are random variables.)

For $\eta>0$, define $\vecx^*$ to be $\eta$-good if for every $\sigma \in [q]$, we have $|\{i \in [n] ~|~ \vecx^*_i = \sigma\}| \in [(1-\eta)\cdot\frac{n}q,(1+\eta)\cdot\frac{n}q]$. A straightforward application of Chernoff bounds shows that for every $\eta>0$ the vector $\vecx^*$ is $\eta$-good with  probability $1-\exp(-n)$.

Below we condition on a good $\vecx^*$ and prove the following: (1) We show the expected value of $m$ is roughly $q^{-k}\cdot N$ and furthermore $m$ is sharply concentrated around its expectation. (2) In the  case we prove that the expected number of constraints satisfied by $\vecx^*$ is roughly at least $\gamma\cdot q^{-k} \cdot N$ and again this variable is sharply concentrated around its expectation. (3) In the  case we prove that the expected number of constraints satisfied by any assignment is roughly at most $\beta\cdot q^{-k} \cdot N$ and again this variable is sharply concentrated around its expectation. We note that the sharp concentration part is essentially the same in all cases and it is bounding the expectations that is different in each case. That being said the analysis of the  case does require sharper concentration since we need to take a union bound over all possible assignments.

Bounding the number of constraints.
We start with step (1). Fix an $\eta$-good $\vecx^*$. Note that $m_t = \sum_{i \in [N_t]} \tilde{z}^{(t)}(i)$ for every $0\leq t\leq T$.
We divide the analysis into two subparts. In step (1a) we bound $\mu \triangleq \Exp[\tilde{z}^{(t)}(i)]$ (in particular this expectation does not depend on $i$ or $t$). Note that $m = \sum_{t=0}^T \sum_{i \in [N_t]} \tilde{z}^{(t)}(i)$ and so bounding $\mu$ bounds $\Exp[m] = \mu\cdot N$.
Then in step (1b) we show that $m$ is concentrated around its expected value.

For step (1a), let $p_{\sigma}$ denote the fraction of occurrences of the letter $\sigma$ in $\vecx^*$, i.e., $p_{\sigma} = \frac1n|\{i \in [n] | \vecx^*_i = \sigma\}|$. Note that given a sequence $\widetilde{\vecb}^{(t)}(i)=\veca\in[q]^k$, the probability that $\tilde{z}^{(t)}(i)=1$ over a random choice of $e^{(t)}(i)$ depends on $\veca$ as well as the $p_\sigma$'s. (Specifically this probability is $\prod_{j=1}^k p_{\veca_j} \pm O(k^2/n)$, where the additive correction term accounts for the sampling without replacement in the choice of $e^{(t)}(i)$.) However if the vector $\vecx^*$ is good, this dependence has little quantitative effect. In particular, if $\vecx^*$ is $\eta$-good, we have $\mu \in (\frac1q \pm \eta)^k\pm O(k^2/n)$ and thus we get $q^{-k} - 2 k \eta \leq \mu \leq q^{-k}+2k\eta$ provided $\eta \leq 1/(4kq)$ and $n$ is sufficiently large. This simplifies further to $\mu \in (1\pm\frac{\eps}{10})q^{-k}$ using $\eta \leq q^{-k}\eps/(20k)$.  Summing up over $(t,i)\in\cI$ we get $\Exp[m] \in (1\pm\frac{\eps}{10})q^{-k}N$.

We now turn to step (1b), i.e., proving that $m$ is concentrated around its expectation. (In this part we work a little harder than necessary to prove that the failure probability is $\exp(-nT)$ rather than $\exp(-n)$. This is not necessary, but will be needed for the similar step in step (3).)
Let $\tilde{Z}$ denote the set of random variables $\{\tilde{z}^{(t)}(i) | (t,i)\in \cI\}$ and for $(t,i)\in \cI$, let $\tilde{Z}_{-(t,i)} = \tilde{Z} \setminus \{\tilde{z}^{(t)}(i)\}$. We first show that for every $(t,i) \in \cI$ we have $\Exp[\tilde{z}^{(t)}(i)~|~\tilde{Z}_{-(t,i)}] \in (1\pm\frac\eps{10})\Exp[\tilde{z}^{(t)}(i)]$.
Let $B_t$ denote the $t$-th block of variables, i.e., $B_t = \{\tilde{z}^{(t)}(i) | i \in [N_t]\}$. Now note that the only dependence among the $\tilde{z}^{(t)}(i)$'s is among the variables within a block while the blocks themselves are independent. Furthermore the variables in the block $B_0$ are independent of each other. Thus for $i\in[N_0]$ we have $\Exp[\tilde{z}^{(0)}(i)| Z_{-(0,i)}] = \Exp[\tilde{z}^{(0)}(i)]$.
For $t>0$, we have the variables from block $B_t$ may depend on each other due to the constraint that the underlying set of hyperedges are vertex disjoint. Fix $(t,i)\in \cI$ with $t>0$ and let $S$ be the set of variables touched by the hyperedges from block $B_t$, excluding $e^{(t)}(i)$.
Now consider picking a hyperedge uniformly from $[n]$ and let $\psi$ be the probability that this hyperedge touches $S$. We clearly have $\psi \leq k|S|/n \leq k\alpha$. On the other hand, $\psi$ also upper bounds the difference between $\Exp[\tilde{z}^{(t)}(i)~|~\tilde{Z}_{-(t,i)}]$ and
$\Exp[\tilde{z}^{(t)}(i)]$, so we have:

$$| \Exp[\tilde{z}^{(t)}(i)~|~\tilde{Z}_{-(t,i)}] - \Exp[\tilde{z}^{(t)}(i)] | \leq \psi \leq k \alpha \leq \frac{\eps q^{-k}}{20}\leq \frac{\eps}{10}\Exp[\tilde{z}^{(t)}(i)].$$

Applying <ref> to the variables of $\tilde{Z}$ (arranged in some arbitrary order) we have
$\Pr[m \not \in ((q^{-k} \cdot (1\pm\eps/10)^3] \leq \exp(-nT)$. Using $(1\pm\eps/10)^3 \subseteq (1\pm\eps/2)$ for $\eps <1$ we get:

\begin{equation}
\Pr[m \not \in (1\pm\eps/2)\cdot q^{-k}N ] \leq \exp(-nT) \label{eqn:csp value m}
\end{equation}

Lower bounding the number of satisfied constraints in the  case.
Let $Z^{(t)}(i)$ be the indicator variable for the event that the $i$-th element of $\vecsigma^{(t)}$ produces a constraint that is satisfied by $\vecx^*$, i.e.,  $Z^{(t)}(i) = \tilde{z}^{(t)}(i)\cdot f_i(\vecx^*|_{\vecj^{(t)}(i)})$. Note that the number of constraints satisfied by $\vecx^*$ is $\sum_{(t,i)\in\cI} Z^{(t)}(i)$. Note further that $Z^{(0)}(i)$'s are identically distributed across $i\in [N_0]$, and $Z^{(t)}(i)$ are also identically distributed across $t \in [T]$ and $i \in [N_0]$. By construction (see <ref>) we have $\Exp[Z^{(0)}(i)] = \Exp_{(f,\vecb)\sim \cD_0}[f(\vecb)\cdot \Exp_{\vecj}[\One(\vecx^*|_\vecj = \vecb)]]$. By the $\eta$-goodness of $\vecx^*$, we have that for every $\vecb \in [q]^k$, $\Exp_{\vecj}[\One(\vecx^*|_\vecj = \vecb)] \geq (1-\frac\eps{10})q^{-k}$. Thus we get $\Exp[Z^{(0)}(i)] \geq (1-\frac\eps{10})q^{-k}\cdot \Exp_{(f,\vecb)\sim \cD_0}[f(\vecb)]$. Similarly for $t>0$ we have $\Exp[Z^{(t)}(i)] = \Exp_{(f,\vecb)\sim \cD_Y}[f(\vecb)\cdot \Exp_{\vecj}[\One(\vecx^*|_\vecj = \vecb)]] \geq (1-\frac\eps{10})q^{-k}\cdot \Exp_{(f,\vecb)\sim \cD_Y}[f(\vecb)]$. Using linearity of expectations we now get

\begin{align*}
\Exp\left[ \sum_{(t,i) \in \cI} Z^{(t)}(i) \right] & = N_0 \Exp[Z^{(0)}(1)] + T N_T  \Exp[Z^{(1)}(1)]\\
& = N (\tau \Exp[Z^{(0)}(1)] + (1-\tau)  \Exp[Z^{(1)}(1)])\\
& \geq \left(1-\frac{\eps}{10}\right) q^{-k} N \cdot (\tau \Exp_{(f,\vecb)\sim \cD_0}[f(\vecb)]
+ (1-\tau) \Exp_{(f,\vecb)\sim \cD_Y}[f(\vecb)])\\
& = \left(1-\frac{\eps}{10}\right) q^{-k} N \cdot \Exp_{(f,\vecb)\sim \tau\cD_0 + (1-\tau)\cD_Y}[f(\vecb)] \\
& \geq \gamma \cdot \left(1-\frac{\eps}{10}\right) q^{-k} N,
\end{align*}

where the final inequality uses $\tau\cD_0 + (1-\tau)\cD_Y \in \sgyf$.
The concentration can be analyzed exactly as in step (1b). In particular if we let $Z$ denote all variables $Z^{(t)}(i)$'s, then we have
$\Exp[Z^{(t)}(i) | Z \setminus \{Z^{(t)}(i)\}] \geq \Exp[Z^{(t)}(i)] - \frac{\eps}{10}q^{-k}$.

\begin{equation}
\Pr\left[\sum_{(t,i) \in \cI} Z^{(t)}(i) \leq (\gamma - \frac{3\eps}{10})\cdot  q^{-k} N \leq  \gamma\cdot (1-\frac{\eps}{10}) q^{-k} N - \frac{\eps}5 q^{-k} N \right] \leq \exp(-nT).
\label{eqn:csp value yes}
\end{equation}

Upper bounding the number of satisfiable constraints in the  case.
Fix an assignment $\vecnu \in [q]^k$ and consider the expected number of constraints satisfied by $\vecnu$. (We will later take a union bound over all $\vecnu$.)
Let $W^{(t)}(i)$ be the indicator variable for the event that the $i$-th element of $\vecsigma^{(t)}$ produces a constraint that is satisfied by $\vecnu$, i.e.,  $W^{(t)}(i) = \tilde{z}^{(t)}(i)\cdot f_i(\vecnu|_{\vecj^{(t)}(i)})$. Note once again that $W^{(0)}(i)$'s are identically distributed across $i$ and $W^{(t)}(i)$ are identical across $t >0$ and $i$. Let $\mu_0 = \Exp[W^{(0)}(1)]$ and $\mu_N = \Exp[W^{(1)}(1)]$. Note that the expected number of satisfied constraints is $\Exp[\sum_{(t,i) \in \cI} W^{(t)}(i)] = N \cdot (\tau \mu_0 + (1-\tau) \mu_N)$, so we bound $\mu_0$ and $\mu_N$. By construction we have

$$\mu_0 = \Exp_{(f,\vecb)\sim \cD_0, \vecj}[f(\vecnu|_\vecj)\cdot \One(\vecx^*|_\vecj = \vecb)] = \Exp_{(f,\vecb)\sim \cD_0, \vecj}[\One(\vecx^*|_\vecj = \vecb)]\cdot  \Exp_{(f,\vecb)\sim \cD_0, \vecj}[f(\vecnu|_\vecj) ~|~ \One(\vecx^*|_\vecj = \vecb)]$$

where $\vecj$ is a uniform random sequence of $k$ distinct elements of $[n]$.
As argued earlier for every $\vecb$ we have $\Exp_{\vecj}[\One(\vecx^*|\vecj=b)] \leq (1+\frac{\eps}{10})q^{-k}$ for $\eta$-good $\vecx^*$. So we turn to bounding the second term.

For $\sigma,\rho \in [q]$ let $\cP_{\sigma}(\rho)$ be the fraction of coordinates in $\vecnu$ that take the value $\rho$ among those coordinates where $\vecx^*$ is $\sigma$, i.e., $\cP_{\sigma}(\rho) = \frac{|\{i\in[n] | \vecnu_i = \rho ~\& ~ \vecx^*_i = \sigma\}|}{|\{i\in[n] | \vecx^*_i = \sigma\}|}$. Note that for every $\sigma$, $\cP_{\sigma}$ is a probability distribution in $\Delta(q)$.
Furthermore, conditioning on $\vecx^*|_\vecj(\ell) = \vecb(\ell)$, the distribution of $\vecnu|_\vecj(\ell)$ is given by $\cP_{\vecb(\ell)}$. Thus the joint distribution of $\vecnu|_\vecj$ is $O(k^2/n)$-close in total variation distance to $\cP_{\vecb(1)} \times \cdots \times \cP_{\vecb(k)}$.
We thus have

\begin{align*}
\Exp_{(f,\vecb)\sim \cD_0, \vecj}[f(\vecnu|_\vecj) ~|~ \One(\vecx^*|_\vecj = \vecb)]
&\leq \Exp_{(f,\veca)\sim \cD_0}[\Exp_{\vecc, c_\ell \sim \cP_{a_\ell}}[f(\vecc)]]+O(k^2/n) \\
& = \Exp_{(f,\veca)\sim \cD_0}[\Exp_{\vecd, d_{\ell,\sigma} \sim \cP_{\sigma}}[\cC(f,\veca)(\vecd)]]+O(k^2/n),
\end{align*}

where $\vecc \in [q]^k$ and $\vecd \in [q]^{k \times q}$. Note that the final expression is simply a change of notation applied to the middle expression above to make the expression syntactically closer to the notation in the definition of $\sbnf$.
Combining with the bound on $\Exp_{\vecj}[\One(\vecx^*|\vecj=b)]$ above we get

$$\mu_0 \leq  (1+\frac{\eps}{10}) q^{-k} \cdot (\Exp_{(f,\veca)\sim \cD_0}[\Exp_{\vecd, d_{\ell,\sigma} \sim \cP_{\sigma}}[\cC(f,\veca)(\vecd)]]) + O(k/n).$$

Similarly we get

$$\mu_N \leq  (1+\frac{\eps}{10}) q^{-k}  \cdot (\Exp_{(f,\veca)\sim \cD_N}[\Exp_{\vecd, d_{\ell,\sigma} \sim \cP_{\sigma}}[\cC(f,\veca)(\vecd)]]) + O(k/n).$$

Now combining the two conditions above we get

\begin{align*}
(\tau \mu_0 + (1-\tau) \mu_N)
&\leq (1+\frac{\eps}{10}) q^{-k} \cdot \left(\Exp_{(f,\veca)\sim \tau \cD_0+(1-\tau)\cD_N}[\Exp_{\vecd, d_{\ell,\sigma} \sim \cP_{\sigma}}[\cC(f,\veca)(\vecd)]] \right)  +O(k^2/n)\\
& \leq \beta \cdot (1+\frac{\eps}{10}) q^{-k} + O(k^2/n) \\
& \leq \beta \cdot (1+\frac{\eps}{9}) q^{-k},
\end{align*}

where the final inequality uses the fact that $n$ is sufficiently large.
We thus conclude the the expected number of constraints satisfied by $\vecnu$ is at most $\beta \cdot (1+\frac{\eps}{9})q^{-k} N$.
Concentration around the mean is now similar to before. In particular if we let $W$ denote the set of all $W^{(t)}(i)$'s then we still have If we  $\Exp[W^{(t)}(i) | W \setminus \{W^{(t)}(i)\}] \leq \Exp[W^{(t)}(i)]+k\alpha \leq \Exp[W^{(t)}(i)] + \frac{\eps}{10}q^{-k}N$, and so by <ref> we get

$$\Pr\left[\sum_{(t,i) \in \cI} W^{(t)}(i) \geq  (\beta+\frac{2\eps}9)\cdot q^{-k} N \geq \beta(1+\eps/9) q^{-k}N + \frac{\eps}{9} q^{-k}N\right] \leq \exp(-nT).$$

In particular by using $T$ sufficiently large, we get that the probability that  more than $(\beta+\frac{2\eps}9)\cdot q^{-k} N$ constraints are satisfied by $\vecnu$ is at most $c^{-n}$ for some $c > q$.
So by a union bound over all possible $\vecnu$'s we get the following:

\begin{equation}
\label{eqn:csp value no}
\Pr\left[\exists \vecnu\in [q]^k \mbox{ s.t. }\vecnu \mbox{ satisfies more than } (\beta+\frac{2\eps}9)\cdot q^{-k} N \mbox{ constraints}\right] \leq \exp(-nT).
\end{equation}

Putting it together.
Putting the above together we get that in the  case with probability $1 - \exp(-n)$ we have that $\vecx^*$ is good and the number of constraints is at most $(1+\frac\eps2)q^{-k}N$ (by <ref>) while the number of satisfied constraints is at least $(\gamma - \frac{3\eps}{10})\cdot  q^{-k} N$ (by <ref>).
Taking ratios we get

$$\val_{\Psi(\vecsigma)} \geq
\frac{\gamma - \frac{3\eps}{10}}{1+\frac\eps2} \geq \gamma - \eps.

Similarly in the  case we have with probability at least $1-\exp(-n)$ we have that $\vecx^*$ is good, and the number of constraints is at least $(1-\frac\eps2)q^{-k}N$ (by <ref>) while the number of satisfied constraints is at most $(\beta+\frac{2\eps}9)\cdot q^{-k} N$ (by <ref>).
Taking ratios we get

$$\val_{\Psi(\vecsigma)} \leq \frac{\beta+\frac{2\eps}9}{1-\frac\eps2}\leq \beta+\eps.$$

This proves the main part of the lemma.

The furthermore part follows from the fact that if $\gamma=1$ then every constraint in the  case is satisfied by $\vecx^*$.

I slightly change the proof strategy and currently only prove the Yes case. If it looks good, I'll complete the No case afterward.

We prove the lemma for $\alpha_0 = \epsilon/(100k^2)$ and $T_0 = 1000/(\epsilon^2\alpha)$.To update.
Roughly our proof uses the fact that the definition of $S^Y_\gamma$ is setup so that $\Psi(\vecsigma)$ achieves value $\gamma$ under the “planted” assignment $\vecx^*$.
Similarly $S^N_\beta$ is setup so that for every assignment, the expected value is not more than $\beta$.
I looked at the proof and I am not sure what the strategy is, so here is my suggestion. I would suggest sticking to the same strategy as before with minor changes as follows: Let $m' = \alpha n  T/(1-\tau)$. And let $m$ be actual number of clauses etc. Previous analysis shows  expected value and concentration of expected value of number of satisfied clauses around $\gamma q^{-k} m'$. We add to that expectation and concentration of $m$ around $q^{-k} m'$ and this handles the YES case. NO case similarly would use expectation and concentration of number of sat clauses being at most $\beta q^{-k} m'$ - which follows from previous analysis. If this approach will not work - can you explain why? Right now I don't see the overall strategy and what I see seems more complex and less modular than I would expect.
In short, there's a subtle difference between RMD and SD here (let me explain in the Yes case): when we let the assignment to be $\vecx^*$, in RMD the $\vecx^*$ will cancel out with each other (i.e., something like $Z=f(\vecb\odot\vecx^*\odot\vecx^*)$) but in SD $\vecx^*$ will stay in both $\tilde{z}$ and $f$ (i.e., $Z=\tilde{z}\cdot f(\vecx^*)=\mathbf{1}_{M\vecx^*=\vecb}\cdot f(\vecx^*)$). So this cause extra complication in the calculation of $\Exp[Z_i | Z_{<i}]$ because now $Z_i$ depends on $\vecx^*$ and hence potentially correlates with $Z_{<i}$.

The current way to fix it is to condition on $\vecx^*$ first so that $Z_i$ won't be correlated. Also, w.h.p. $\vecx^*$ will be quite uniform (i.e., roughly the same fraction of elements in $[q]$) and hence the expectation is as expected. I can elaborate more if needed.
Thanks for the detailed explanation. Let me digest ... but this does seem important and worth checking.
Let us start with estimating the number of constraints in $\Psi(\vecsigma)$. Let $m$ denote the total number of constraints, $m_0$ denote the number of constraints from $\sigma(i)$ with $i\leq\frac{\tau}{1-\tau}\alpha nT$ and, $m_t$ denote the number of constraints from $\sigma(i)$ with $\frac{\tau}{1-\tau}\alpha nT+\alpha n(t-1)+1\leq t\leq\frac{\tau}{1-\tau}\alpha nT+\alpha nt$ for all $t\in[T]$. Note that when $\vecx^*$ is fixed, $m_0,\dots,m_1,\dots,m_T$ are mutually independent. Moreover, the following claim shows that with high probability over the choice of $\vecx^*$, the expected values of $m_0,\dots,m_1,\dots,m_T$ are concentrated as expected.

TODO: prove this claim.
When $\alpha<XXX$, with probability $\exp(-\Omega(n))$ over the choice of $\vecx^*$, we have

\[
\Exp[m_0]=(1\pm o(1))q^{-k}\frac{\tau}{1-\tau}\alpha nT\ \ \ \text{ and }\ \ \ \Exp[m_1]=\cdots=\Exp[m_T]=(1\pm o(1))q^{-k}\alpha nT \, .
\]

In particular, $\Exp[m]=(1\pm o(1))q^{-k}\frac{\alpha nT}{1-\tau}$.

We recall that the condition $\tau\cD_0+(1-\tau)\cD_Y \in S_\gamma^Y$ implies that $\Exp_{(f,\veca)\sim\tau\cD_0+(1-\tau)\cD_Y}[f(\veca)] \geq \gamma$. Now consider a random  instance $\vecsigma \sim \cY_{\pstrm,n}$ of $(\cD_Y,\cD_N,T,\cD_0,\tau)$- and let $\vecx^*$ denote the underlying vector corresponding to this draw. We show that for $\Psi = \Psi(\vecsigma)$ we have $\val_\Psi(\vecx^*) \geq \gamma-\epsilon$ with high probability.
We consider the constraints given by $\sigma(i)$ one at a time. Let $m = \frac{\tau}{1-\tau}\alpha n T+\alpha n T=\frac{\alpha n T}{1-\tau}$ denote the total number of tuples of $\vecsigma$. Previously $m$ is the number of constraints in $\Psi$ but now such number is random so I want to handle it differently. Let $Z_i = \tilde{z}_i\cdot f_i(\vecx^*|_{\vecj(i)})$ denote the indicator of the event that the $i$-th tuple produces a constraint and it is satisfied by $\vecx^*$.
By construction of $\vecz(i)$ (from <ref> and passed through <ref>), we have $\tilde{z}_i$ imply $\vecx^*|_{\vecj(i)}=\vecb(i)$ where $(f_i,\vecb(i))$ is sampled from $\tau\cD_0+(1-\tau)\cD_Y$ independently of all other choices. We thus have
$Z_i = \tilde{z}_i\cdot f_i(\vecx^*|_{\vecj(i)}) = \tilde{z}_i\cdot f_i(\vecb(i))$ and

\begin{equation*}
\Exp[Z_i | Z_1,\ldots,Z_{i-1}] =
\begin{cases}
\Exp[\tilde{z}_i | Z_1,\dots,Z_{i-1}]\cdot\Exp_{(f,\vecb) \sim \cD_0} [f(\vecb)] \text{, if }i\leq\frac{\tau}{1-\tau}\alpha n T\\
\Exp[\tilde{z}_i | Z_1,\dots,Z_{i-1}]\cdot\Exp_{(f,\vecb) \sim \cD_Y} [f(\vecb)] \text{, otherwise.}
\end{cases}
\end{equation*}

In particular,

\begin{align*}
\Exp\left[\sum_{i=1}^mZ_i\right] &= \Exp\left[\sum_{i=1}^{\frac{\tau}{1-\tau}\alpha nT}\tilde{z_i}\right]\cdot\Exp_{(f,\vecb) \sim \cD_0} [f(\vecb)]+\sum_{t=1}^T\Exp\left[\sum_{i=\frac{\tau}{1-\tau}\alpha nT+\alpha n(t-1)+1}^{\frac{\tau}{1-\tau}\alpha nT+\alpha nt}\tilde{z}_i\right]\cdot\Exp_{(f,\vecb) \sim \cD_Y} [f(\vecb)]\\
&=\Exp[m_0]\cdot\Exp_{(f,\vecb) \sim \cD_0} [f(\vecb)] + \sum_{t=1}^T\Exp[m_t]\cdot\Exp_{(f,\vecb) \sim \cD_Y} [f(\vecb)] \, .
\intertext{By~\cref{claim:csp value number of constraints}, with probability $\exp(-\Omega(n))$ over the choice of $\vecx^*$, we have}
&= q^{-k}\frac{\tau}{1-\tau}\alpha nT\cdot\Exp_{\vecb \sim \cD_0} [f(\vecb)] + q^{-k}\alpha n T\cdot \Exp_{\vecb \sim \cD_Y} [f(\vecb)] \pm o\left(\frac{q^{-k}\alpha nT}{1-\tau}\right)\\
&= q^{-k}\frac{\alpha n T}{1-\tau}\cdot \Exp_{\vecb \sim \tau\cD_0+(1-\tau)\cD_Y} [f(\vecb)] \pm o\left(\frac{q^{-k}\alpha nT}{1-\tau}\right) \\
&\geq q^{-k}\frac{\alpha nT}{1-\tau}\cdot\gamma - o\left(\frac{q^{-k}\alpha nT}{1-\tau}\right) ~ \geq ~ (\gamma-o(1)) \cdot m\, .
\end{align*}

We prove the lemma for $\alpha_0 = \epsilon/(100k^2)$ and $T_0 = 1000/(\epsilon^2\alpha)$.
Roughly our proof uses the fact that the definition of $S^Y_\gamma$ is setup so that $\Psi(\vecsigma)$ achieves value $\gamma$ under the “planted” assignment $\vecx^*$.
Similarly $S^N_\beta$ is setup so that for every assignment, the expected value is not more than $\beta$.

We recall that the condition $\tau\cD_0+(1-\tau)\cD_Y \in S_\gamma^Y$ implies that $\Exp_{\veca\sim\tau\cD_0+(1-\tau)\cD_Y}[f(\veca)] \geq \gamma$. Now consider a random  instance $\vecsigma \sim \cY_{\pstrm,n}$ of $(\cD_Y,\cD_N,T,\cD_0,\tau)$- and let $\vecx^*$ denote the underlying vector corresponding to this draw. We show that for $\Psi = \Psi(\vecsigma)$ we have $\val_\Psi(\vecx^*) \geq \gamma-\epsilon$ with high probability.
We consider the constraints given by $\sigma(i)$ one at a time. Let $m = \frac{\tau}{1-\tau}\alpha n T+\alpha n T=\frac{\alpha n T}{1-\tau}$ denote the total number of constraints of $\Psi$. Let $Z_i = C_i(\vecx^*) = f(\vecz(i)\odot\vecx^*|_{\vecj(i)})$ denote the indicator of the event that the $i$th constraint is satisfied by $\vecx^*$.
By construction of $\vecz(i)$ (from <ref> and passed through <ref>), we have $\vecz(i) = \vecb(i) \odot \vecx^*|_{\vecj(i)}$ where $\vecb(i) \sim \cD_Y$ independently of all other choices. We thus have
$Z_i = f(\vecb(i) \odot \vecx^*|_{\vecj(i)} \odot\vecx^*|_{\vecj(i)}) = f(\vecb(i))$. Thus $Z_i$ is a random variable,  chosen independent of $Z_{1},\ldots,Z_{i-1}$, with expectation $\Exp[Z_i | Z_1,\ldots,Z_{i-1}] = \Exp_{\vecb \sim \cD_0} [f(\vecb)]$ when $i\leq\frac{\tau}{1-\tau}\alpha n T$ and $\Exp[Z_i | Z_1,\ldots,Z_{i-1}] = \Exp_{\vecb \sim \cD_Y} [f(\vecb)]$ otherwise. In particular,

\begin{align*}
\Exp\left[\sum_{i=1}^mZ_i\right] &= \frac{\tau}{1-\tau}\alpha nT\cdot\Exp_{\vecb \sim \cD_0} [f(\vecb)] + \alpha n T\cdot \Exp_{\vecb \sim \cD_Y} [f(\vecb)]\\
&= \frac{\alpha n T}{1-\tau}\cdot \Exp_{\vecb \sim \tau\cD_0+(1-\tau)\cD_Y} [f(\vecb)] \\
&\geq\frac{\alpha nT}{1-\tau}\cdot\gamma ~ = ~ \gamma \cdot m\, .
\end{align*}

By applying a concentration bound (<ref> suffices, though even simpler Chernoff bounds would suffice) we get that $\Pr_{\vecsigma\sim\cY_{\strm,n}}[\val_{\Psi(\vecsigma)} = \frac1m{\sum_{i=1}^m Z_i} < (\gamma-\epsilon)] \leq \exp(-\epsilon^2 m) = \exp(-\epsilon^2 \alpha T n)$. This yields Part (1) of the lemma.

Note that, if $\gamma = 1$, then $Z_i = 1$ deterministically for every $i$, and so we get $\val_\Psi = 1$ with probability $1$, yielding the furthermore part of the lemma.

We now turn to the analysis of the  case. By the condition $\tau\cD_0+(1-\tau)\cD_N \in S_\beta^N$ we have that for every $p \in [0,1]$, we have

\begin{equation}\label{eqn:no-cond}
\Exp_{\vecb\sim \tau\cD_0+(1-\tau)\cD_N}\Exp_{\veca \sim \bern(p)^k}[f(\vecb \odot \veca)]\leq \beta.
\end{equation}

Now consider any fixed assignment $\vecnu \in \{-1,1\}^n$. In what follows we show
that for a random
instance $\vecsigma \sim \cN_{\pstrm,n}$ of $(\cD_Y,\cD_N,T,\cD_0,\tau)$- if we let $\Psi = \Psi(\vecsigma)$, then $\Pr[\val_{\Psi}(\vecnu) > (\beta + \epsilon)] \le c^{-n}$ for $c > 2$. This allows us to take a union bound over the $2^n$ possible $\vecnu$'s to claim $\Pr[\val_{\Psi} > (\beta + \epsilon)] \le 2^n\cdot c^{-n} = o(1)$.

We thus turn to analyzing $\val_{\Psi}(\vecnu)$. Recall that $\vecsigma$ is chosen by picking $\vecx^* \in \{-1,1\}^n$ uniformly and then picking $\sigma(i)$'s based on this choice — but our analysis will work for every choice of $\vecx^*\in \{-1,1\}^n$. Fix such a choice and let $\vecnu^* = \vecnu \odot \vecx^*$. Now  for $i \in [m]$ (where $m=\frac{\alpha n T}{1-\tau}$) let $Z_i$ denote the indicator of the event that $\vecnu$ satisfies $C_i$. We have $Z_i = f(\vecb(i) \odot \vecx^*_{\vecj(i)} \odot \vecnu_{\vecj(i)}) = f(\vecb(i) \odot \vecnu^*|_{\vecj(i)})$. Our goal is to prove that $\Pr[\sum_{i=1}^m Z_i > (\beta + \epsilon) \cdot m] \leq c^{-n}$.
To this end,  let $\eta_i = \Exp[Z_i]$. Below we prove the following: (1) $\sum_{i=1}^m \eta_i \leq  \beta\cdot m$, and (2) For every $i$, and $Z_1,\ldots,Z_{i-1}$,
$\Exp[Z_i | Z_1,\ldots,Z_{i-1}] \leq \eta_i + \epsilon/2$. With (1) and (2) in hand, a straightforward application of Azuma's inequality yields that $\Pr[\sum_i Z_i > (\beta+\epsilon)\cdot m] \leq c_1^{-m}$ for some $c_1 > 1$. Picking $T$ large enough now ensures this is at most $c^{-n}$ for some $c > 2$.

We start by analyzing the $\eta_i$'s. Let $m_0 = \tau\cdot m$ and let $m_1 = \alpha n$ so that $m = m_0 + m_1 \cdot T$.
Let $p$ be the fraction $1$'s in $\vecnu^*$.
When $i \leq m_0$
we have
$\eta_i = \Exp_{\vecb(i)\sim\cD_0} \Exp_{\veca \sim \bern(p)^k} [f(\vecb(i) \odot \veca)]$.
When $i > m_0$ we have
$\eta_i = \Exp_{\vecb(i)\sim\cD_N} \Exp_{\veca \sim \bern(p)^k} [f(\vecb(i) \odot \veca)]$.
By linearity of expectations we now get

\begin{eqnarray*}
\sum_{i=1}^m \eta_i & = & \tau\cdot m \cdot \Exp_{\vecb(i)\sim\cD_0} \Exp_{\veca \sim \bern(p)^k} [f(\vecb(i) \odot \veca)]
+ (1-\tau)\cdot m \cdot \Exp_{\vecb(i)\sim\cD_N} \Exp_{\veca \sim \bern(p)^k} [f(\vecb(i) \odot \veca)] \\
& = & m \cdot \Exp_{\vecb(i)\sim\tau\cD_0 + (1-\tau)\cD_N} \Exp_{\veca \sim \bern(p)^k} [f(\vecb(i) \odot \veca)]
\\
& \leq & \beta \cdot m .  \mbox{~~~ (By \cref{eqn:no-cond})}
\end{eqnarray*}

This yields (1).

Turning to part (2) we need to understand how the $Z_i$'s depend on each other.
For the case $i \leq m_0$, note that $Z_1,\ldots,Z_{m_0}$ are independent by construction (<ref>).
So we have
$\Exp[Z_i\, |\, Z_1,\ldots,Z_{i-1}] = \eta_i$ in this case.
We now consider $i>m_0$.  For $t \in [T]$, let us partition the variables $Z_{m_0+1},\ldots,Z_{m}$ into $T$ block $B_1,\ldots,B_T$ with $B_t = (Z_{m_0+(t-1)m_1 + 1},\ldots,Z_{m_0+t m_1})$ for $t \in [T$]. By construction (<ref> via <ref>) we have that the blocks $B_1,\ldots,B_T$ are identically distributed and independent conditioned on $Z_1,\ldots,Z_{m_0}$. Thus the only dependence between the $Z_i$'s is within the $Z_i$'s in the same block. Within a block two $Z_i$'s may depend on each other due to the restriction that the underlying set of variables are disjoint. Thus, in particular when choosing the variables of $\vecsigma^{(t)}(i')$ (corresponding to $Z_{m_0+(t-1)m_1+i'}$, some subset $S \subseteq [n]$ of the variables may already be involved in constraints of the $t$-th block. Let $S$ be the set of variables not assigned to constraints in the $t$-th block at this time, and let $p_S$ denote the fraction in $\vecnu^*|_S$. (Note both $S$ and $p_S$ are random variables.) Since $|S| \geq n - k\alpha n$ and $\alpha \leq \epsilon/(100k^2)$ we have $|S|\geq (1 - \epsilon/(100k))n$ and so $|p - p_S| \leq \epsilon/(100k)$. In turn this implies that $\|\bern(p)^k - \bern(p_S)^k\|_{tvd} \leq \epsilon/100$. Using these bounds we now have:

\begin{align*}
\Exp[Z_i | Z_1,\ldots,Z_{i-1}] & = \Exp[Z_i | S]  \\
& =
\Exp_{\vecj(i),\vecb(i)} [f(\vecb(i) \odot \vecnu^*|_{\vecj(i)})]\\
&\leq \Exp_{\vecb(i)\sim\cD_N} \Exp_{\veca \sim \bern(p_S)^k} [f(\vecb(i) \odot \veca)] + \frac{k^2}{|S|}\\
&\leq \Exp_{\vecb(i)\sim\cD_N} \Exp_{\veca \sim \bern(p)^k} [f(\vecb(i) \odot \veca)] + \frac{\epsilon}{100} + \frac{k^2}{|S|}\\
&\leq \Exp_{\vecb(i)\sim\cD_N} \Exp_{\veca \sim \bern(p)^k} [f(\vecb(i) \odot \veca)] + \frac{\epsilon}{2} \\
&= \eta_i + \frac{\epsilon}{2}.
\end{align*}

(In the second equality above $\vecj(i)$ denotes a random sequence of distinct variables from $S$. The next inequality comes from the difference between sampling $k$ elements from $S$ with repetition and without. The following inequality is the key one, using $\|\bern(p)^k - \bern(p_S)^k\|_{tvd} \leq \epsilon/100$. The final inequality uses the fact that $n$ and hence $|S|$ are large enough, and the final equality uses the value of $\eta_i$ from Part (1).)
This concludes Part (2).

Finally we use a version of a concentration bound for submartingales to combine (1) and (2) to get the desired bound on $\Pr[\val_{\Psi}(\vecnu) > (\beta + \epsilon)] \le c^{-n}$. Specifically, we apply <ref> with $N=m$, $p_i = \eta_i$ for $i \in [N]$ and $\Delta = (\epsilon/2)N$ to conclude that $\Pr[\val_{\Psi}(\vecnu) > (\beta + \epsilon)] = \Pr[\sum_i Z_i > (\beta + \epsilon)\cdot m] \leq \exp(-O(\epsilon^2 \alpha n T))$. Given $c$ we can choose $T$ to be large enough so that this is at most $c^{-n}$.
This concludes the analysis of the  case, and thus the lemma.

§.§.§ Reduction from one-way (DY,DN)-SD) to padded-streaming-SD

We start by reducing  to  in the special case where $\cD_N$ is “uniform on the variables” in the sense defined next.
We say a distribution $\cD \in \Delta(\cD \times [q]^k)$ is uniform on the variables if there exists a distribution $\cD_f \in \Delta(\cF)$ such that $\cD = \cD_f \times \textsf{Unif}([q]^k)$.
The following lemma implies that in this special case  is hard. Since this holds for all one-wise independent distributions $\cD_Y$, by applying the lemma twice we get that  is hard for all one-wsie independent $\cD_Y$ and $\cD_N$.

Let $\cF$ be a finite set, $T,q,k\in\mathbb{N}$, $\alpha \in (0,\alpha_0(k)]$, $\tau\in[0,1)$, and $\cD_Y,\cD_N,\cD_0\in\Delta(\cF\times[q]^k)$ with $\cD_Y$ being one-wise independent and $\cD_N=\cD_f\times\unif([q]^k)$ for some $\cD_f\in\Delta(\cF)$ and $\vecmu(\cD_Y)=\vecmu(\cD_N)$. Suppose there is a streaming algorithm $\ALG$ that solves $(\cF,\cD_Y,\cD_N,T,\cD_0,\tau)$- on instances of length $n$ with advantage $\Delta$ and space $s$, then there is a one-way protocol for $(\cF,\cD_Y,\cD_N)$- on instances of length $n$ using at most $sT$ bits of communication achieving advantage at least $\Delta/T$.

The proof of <ref> is based on a hybrid argument (e.g., <cit.>). We provide a proof here based on the proof of <cit.>.
Our proof is essentially the same as that of [8] with some minor modifications.
We note their proof was based on the proof of <cit.> and the proof of <cit.>.

Note that since we are interested in distributional advantage, we can fix the randomness in $\ALG$ so that it becomes a deterministic algorithm. By an averaging argument the randomness can be chosen to ensure the advantage does not decrease. Let $\Gamma$ denote the evolution of function of $\ALG$ as it processes a block of edges. That is, if the algorithm is in state $s$ and receives a stream $\vecsigma$ then it ends in state $\Gamma(s,\vecsigma)$. Let $s_0$ denote its initial state.

We consider the following collection of (jointly distributed) random variables: Let $\vecx^* \sim \textsf{Unif}(\{-1,1\}^n)$. Denote $\cY=\cY_{\pstrm,n}$ and $\cN=\cN_{\pstrm,n}$. Let $(\vecsigma_Y^{(0)},\vecsigma_Y^{(1)},\ldots,\vecsigma_Y^{(T)}) \sim \cY|_{\vecx^*}$. Similarly, let $(\vecsigma_N^{(0)},\vecsigma_N^{(1)},\ldots,\vecsigma_N^{(T)}) \sim \cN|_{\vecx^*}$. Recall by Remark <ref> that since $\cD_N=\cD_f\times\unif([q]^k)$, we have $\cN|_{\vecx^*}$ is independent of $\vecx^*$, a feature that will be crucial to this proof.

Let $S_t^Y$ denote the state of
$\ALG$ after processing $\vecsigma_Y^{(0)},\ldots,\vecsigma_Y^{(t)}$, i.e., $S_0^Y = \Gamma(s_0,\vecsigma_Y^{(0)})$ and $S_t^Y = \Gamma(S_{t-1}^Y,\vecsigma_Y^{(t)})$ where $s_0$ is the fixed initial state (recall that $\ALG$ is deterministic).
Similarly let $S_t^N$ denote the state of $\ALG$ after processing $\vecsigma_N^{(0)},\ldots,\vecsigma_N^{(t)}$. Note that since $\vecsigma_Y^{(0)}$ has the same distribution (conditioned on the same $\vecx^*$) as $\vecsigma_N^{(0)}$ by definition, we have $\|S_{0}^Y-S_{0}^N\|_{tvd}=0$.

Let $S^Y_{a:b}$ denote the sequence of states $(S_a^Y,\ldots,S_b^Y)$ and similarly for $S^N_{a:b}$. Now let $\Delta_t = \|S_{0:t}^Y-S_{0:t}^N\|_{tvd}$.
Observe that $\Delta_0=0$ while $\Delta_T\geq\Delta$. (The latter is based on the fact that $\ALG$ distinguishes the two distributions with advantage $\Delta$.)
Thus $\Delta \leq \Delta_T - \Delta_0 = \sum_{t=0}^{T-1} (\Delta_{t+1} - \Delta_t)$ and so there exists $t^*\in\{0,1,\dots,T-1\}$ such that

\[
\Delta_{t^*+1} - \Delta_{t^*} = \|S_{0:t^*+1}^Y-S_{0:t^*+1}^N\|_{tvd}-\|S_{0:t^*}^Y-S_{0:t^*}^N\|_{tvd}\geq\frac{\Delta}{T} \, .
\]

Now consider the random variable $\tilde{S} = \Gamma(S_{t^*}^Y,\vecsigma_N^{(t^*+1)})$ (so the previous state is from the  distribution and the input is from the  distribution). We claim below that $\| S_{t^*+1}^Y - \tilde{S} \|_{tvd} = \Exp_{A \sim_d S_{0:t^*}^Y}[\| S_{t^*+1}^Y|_{S_{0:t^*}^Y=A} - \tilde{S}|_{S_{0:t^*}^Y=A} \|_{tvd} ] \geq \Delta_{t^*+1} - \Delta_{t^*}$.
Once we have the claim, we show how to get a space $T\cdot s$ protocol for $(\cF,\cD_Y,\cD_n)$- with advantage $\Delta_{t^*+1} - \Delta_{t^*}$ concluding the proof of the lemma.

$\| S_{t^*+1}^Y - \tilde{S} \|_{tvd} \geq \Delta_{t^*+1} - \Delta_{t^*}$.

First, by triangle inequality for the total variation distance, we have

\[
\|S_{t^*+1}^Y - \tilde{S}\|_{tvd} \geq \|S_{t^*+1}^Y - S_{t^*+1}^N\|_{tvd} - \|\tilde{S} - S_{t^*+1}^N\|_{tvd} \, .
\]

Recall that $\tilde{S} = \Gamma(S_{t^*}^Y,\vecsigma_N^{(t^*+1)})$ and $S^N_{t^*+1} = \Gamma(S_{t^*}^N,\vecsigma_N^{(t^*+1)})$. Also, note that $\vecsigma_N^{(t^*+1)}$ follows the product distribution $(\cD_f\times\bern(q^{-k}))^{\alpha n}$ and in particular is independent of $S_{t^*}^Y$ and $S_{t^*}^N$. (This is where we rely crucially on the property $\cD_N = \cD_f\times\unif([q]^k)$.)
Furthermore $\Gamma$ is a deterministic function, and so we can apply the data processing inequality (Item (2) of <ref> with $X=S^Y_{t^*}$, $Y=S^N_{t^*}$, $W=\vecsigma_N^{(t^*+1)}$, and $f=\Gamma$) to conclude

\[\|\tilde{S} - S_{t^*+1}^N\|_{tvd} = \|\Gamma(S_{t^*}^Y,\vecsigma_N^{(t^*+1)}) -  \Gamma(S_{t^*}^N,\vecsigma_N^{(t^*+1)})\|_{tvd}\leq\|S_{t^*}^Y-S_{t^*}^N\|_{tvd}.\]

Combining the two inequalities above we get

\[
\|S_{t^*+1}^Y - \tilde{S}\|_{tvd} \geq \|S_{t^*+1}^Y - S_{t^*+1}^N\|_{tvd} - \|S_{t^*}^Y - S_{t^*}^N\|_{tvd}=\Delta_{t^*+1}-\Delta_{t^*}
\]

as desired.

We now show how a protocol can be designed for $(\cF,\cD_Y,\cD_N)$- that achieves advantage at least $\theta = \Exp_{A \sim_d S_{0:t^*}^Y}[\| S_{t^*+1}^Y|_{S_{0:t^*}=A} - \tilde{S}|_{S_{0:t^*}=A} \|_{tvd} ] \geq \Delta_{t^*+1} - \Delta_{t^*}$ concluding the proof of the lemma. The protocol uses the distinguisher $T_A:\{0,1\}^{s} \to \{0,1\}$ such that $\Exp_{A,S_{t^*+1}^Y,\tilde{S}}[T_A(S_{t^*+1}^Y)] - \Exp[T_A(\tilde{S})] \geq \theta$ which is guaranteed to exist by the definition of total variation distance.

Our protocol works as follows: Let Alice receive input $\vecx^*$ and Bob receive inputs $(M,\vecz)$ sampled from either $\cY_{\SD}|_{\vecx^*}$ or $\cN_{\SD}|_{\vecx^*}$ where $\cY_{\SD}$ and $\cN_{\SD}$ are the Yes and No distribution of $(\cF,\cD_Y,\cD_N)$-$\SD$ respectively.

* Alice samples $(\vecsigma^{(0)},\vecsigma^{(1)},\ldots,\vecsigma^{(T)}) \sim \cY|_{\vecx^*}$ and computes $A = S_{0:t^*}^Y \in \{0,1\}^{(t^*+1)s}$ and sends $A$ to Bob.

* Bob extracts $S_{t^*}^Y$ from $A$, computes $\widehat{S} = \Gamma(S_{t^*}^Y,\vecsigma)$, where $\vecsigma$ is the encoding of $(M,\vecz)$ as a stream, and outputs  if $T_A(\widehat{S})=1$ and  otherwise.

Note that if $(M,\vecz)\sim \cY_{\SD}|_{\vecx^*}$ then $\widehat{S} \sim_d S_{t^*+1}^Y|_{S^Y_{0:t^*} = A}$ while if $(M,\vecz)\sim \cN_{\SD}|_{\vecx^*}$ then $\widehat{S} \sim \tilde{S}_{S^Y_{0:t^*} = A}$.
It follows that the advantage of the protocol above exactly equals $\Exp_A[T_A(S_{t^+1}^Y)] - \Exp_A[T_A(\tilde{S})] \geq \theta \geq \Delta_{t^*+1}-\Delta_{t^*} \geq \Delta/T$.
This concludes the proof of the lemma.

By combining <ref> with <ref>, we immediately have the following consequence.

For $k \in \N$ let  $\alpha_0(k)$ be as given by <ref>.
Let $T\in\mathbb{N}$, $\alpha\in(0,\alpha_0(k)]$, $\tau\in[0,1)$, and $\cD_0, \cD_Y,\cD_N,  \in \Delta(\cF \times [q]^k)$ where $\cD_Y$ and $\cD_N$ are one-wise independent distributions with $\vecmu(\cD_Y)=\vecmu(\cD_N)$.

Then every streaming algorithm $\ALG$ solving $(\cF,\cD_Y,\cD_N,T,\cD_0,\tau)$- in the streaming setting with advantage $1/8$ for all lengths $n$ uses space $\Omega(\sqrt{n})$.

Let $\ALG$ be an algorithm using space $s$ solving  $(\cF,\cD_Y,\cD_N,T,\cD_0,\tau)$- with advantage $1/8$.
For $g \in \cF$, let $p_g = \Pr_{(f,\sigma)\sim \cD_Y}[f = g]$ and let $\cD_f$ be the distribution given by $\cD_f(g) = p_g$. Let
$\cD_M = \cD_f \times \textsf{Unif}([q]^k)$. Note that $\cD_M$ is uniform on the variables and satisfies $\vecmu(\cD_M) = \vecmu(\cD_Y) = \vecmu(\cD_N)$. Then by the triangle inequality $\ALG$ solves either the $(\cF,\cD_Y,\cD_M,T,\cD_0,\tau)$- with advantage $1/16$ or it solves the
$(\cF,\cD_N,\cD_M,T,\cD_0,\tau)$- with advantage $1/16$. Assume without loss of generality it is the former.
Then by <ref>, there exists a  one-way protocol for $(\cF,\cD_Y,\cD_M)$- using at most $sT$ bits of communication with advantage at least $1/(16T)$. Applying <ref> with $\delta = 1/(16T) > 0$, we now get that $s = \Omega(\sqrt{n})$.

§.§.§ Proof of the streaming lower bound

We are now ready to prove <ref>.

We combine <ref>, <ref> and <ref>. So in particular we set our parameters $\alpha$ and $T$ so that the conditions of these statements are satisfied. Specifically
$k$ and $\epsilon>0$, let $\alpha^{(1)}_0$ be the constant from <ref>
and let $\alpha^{(2)}_0$ be the constant from <ref>. Let $\alpha_0 = \min\{\alpha_0^{(1)},\alpha_0^{(2)}\}$,
Given $\alpha \in (0,\alpha_0)$ let $T_0$ be the constant from <ref> and let $T = T_0$. (Note that these choices allow for both <ref> and <ref> to hold.)

Suppose there exists a streaming algorithm $\ALG$ that solves $(\gamma-\epsilon,\beta+\epsilon)$-$\maxF$.
Let $\tau\in[0,1)$ and $\cD_Y, \cD_N,\cD_0$ be distributions such that (i) $\cD_Y$ and $\cD_N$ are one-wise independent, (ii) $\tau\cD_0+(1-\tau)\cD_Y\in S_\gamma^Y(\cF)$, and (iii) $\tau\cD_0+(1-\tau)\cD_N\in S_\beta^N(\cF)$.

Let $n$ be sufficiently large and let $\cY_{\strm,n}$ and $\cN_{\strm,n}$ denote the distributions of  and  instances of $(\cF,\cD_Y,\cD_N,T,\cD_0,\tau)$- of length $n$.
Since $\alpha$ and $T$ satisfy the conditions of <ref>, we have for every sufficiently large $n$

\[
\Pr_{\vecsigma\sim\cY_{\strm,n}}\left[\val_{\Psi(\vecsigma)}<\left(\gamma-\epsilon\right)\right]=o(1)
\text{~~~and~~~}
\Pr_{\vecsigma\sim\cN_{\strm,n}}\left[\val_{\Psi(\vecsigma)}>\left(\beta+\epsilon\right)\right]=o(1) \, .
\]

We conclude that $\ALG$ can distinguish  instances of ($\cF$)  from  instances  with advantage at least $1/4-o(1)\geq 1/8$.
However, since $\cD_Y,\cD_N$ and $\alpha$ satisfy the conditions of <ref> (in particular $\cD_Y$ and $\cD_N$ are one-wise independent and $\alpha \in (0,\alpha_0(k))$) such an algorithm requires space at least $\Omega(\sqrt{n})$. Thus, we conclude that any streaming algorithm that solves $(\gamma-\epsilon,\beta+\epsilon)$-($\cF$) requires $\Omega(\sqrt{n})$ space.

Finally, note that if $\gamma = 1$ then in <ref>, we have $\val_\Psi=1$ with probability one. Repeating the above reasoning with this information, shows that $(1,\beta+\epsilon)-\maxF$ requires $\Omega(\sqrt{n})$-space.

§.§ The lower bound against sketching algorithms

In the absence of a reduction from  to  for general $\cD_Y$ and $\cD_N$, we turn to other means of using the hardness of . In particular, we use lower bounds on the communication complexity of a $T$-player communication game in the simultaneous communication setting — one which is significantly easier to obtain lower bounds for than the one-way setting.
Below we explain their setup and show how our problems fit in their general class of problems.
We then describe a family of  $T$-player simultaneous communication games, which we call $(\cF,\cD_Y,\cD_N,T)$-, arising from applying their framework to our problems. (See <ref>.) We then show a simple reduction from $(\cF,\cD_Y,\cD_N)$- to $(\cF,\cD_Y,\cD_N,T)$-. Combining this reduction with our lower bounds on  and the reduction from  to streaming complexity leads to the proof of <ref>.
As in [8] we use the work of Ai, Hu, Li and Woodruff <cit.> (building up on Li, Nguyen and Woodruff <cit.>) to use the hardness of SD to show the hardness of $\maxF$ in the general case, in the dynamic streaming setting. To do so, we introduce a family of $T$-player
simultaneous communication games, which we call $(\cD_Y,\cD_N,T)$-, arising from applying their framework to our problems. (See <ref>.) We then show a simple reduction from $(\cD_Y,\cD_N)$- to $(\cD_Y,\cD_N,T)$-. Combining this reduction with our lower bounds on  and the reduction from $(\cD_Y,\cD_N,T)$- to streaming complexity leads to the proof of <ref>.

§.§.§ T-Player Simultaneous Version of SD

In this section, we consider the complexity of $T$-player number-in-hand simultaneous message passing communication games (abbrev. $T$-player simultaneous communication games). Such games are described by two distributions $\cY$ and $\cN$. An instance of the game is a $T$-tuple $(X^{(1)},\dots,X^{(T)})$ either drawn from $\cY$ or from $\cN$ and $X^{(t)}$ is given as input to the $t$-th player. A (simultaneous communication) protocol $\Pi = (\Pi^{(1)},\dots,\Pi^{(T)},\Pi_{\text{ref}})$ is a $(T+1)$-tuple of functions with $\Pi^{(t)}(X^{(t)}) \in \{0,1\}^c$ denoting the $t$-th player's message to the referee, and $\Pi_{\text{ref}}(\Pi^{(1)}(X^{(1)}),\dots,\Pi^{(T)}(X^{(T)}))\in \{\yes,\no\}$ denoting the protocol's output. We denote this output by $\Pi(X^{(1)},\dots,X^{(T)})$. The complexity of this protocol is the parameter $c$ specifying the maximum length of $\Pi^{(1)}(X^{(1)}),\dots,\Pi^{(T)}(X^{(T)})$ (maximized over all $X$). The advantage of the protocol $\Pi$ is the quantity

$$\left| \Pr_{(X^{(1)},\dots,X^{(T)})\sim\cY} [ \Pi(X^{(1)},\dots,X^{(T)}) = \yes] - \Pr_{(X^{(1)},\dots,X^{(T)})\sim \cN} [\Pi(X^{(1)},\dots,X^{(T)}) = \yes] \right|. $$

For $k,T\in\N$, $\alpha\in(0,1/k]$, a finite set $\cF$,

distributions $\cD_Y,\cD_N$ over $\cF\times[q]^k$, the $(\cF,\cD_Y,\cD_N,T)$- is a $T$-player communication game given by a family of instances $(\cY_{\simul,n},\cN_{\simul,n})_{n\in\N,n\geq1/\alpha}$ where for a given $n$, $\cY=\cY_{\simul,n}$ and $\cN=\cN_{\simul,n}$ are as follows: Both $\cY$ and $\cN$ are supported on tuples $(\vecx^*,M^{(1)},\dots,M^{(T)},\vecz^{(1)},\dots,\vecz^{(T)})$ where $\vecx^*\in[q]^n$, $M^{(t)}\in\{0,1\}^{k\alpha n\times n}$, and $\vecz^{(t)}\in(\cF\times\{0,1\})^{k\alpha n}$, where the pair $(M^{(t)},\vecz^{(t)})$ are the $t$-th player's inputs for all $t\in[T]$. We now specify the distributions of $\vecx^*$, $M^{(t)}$, and $\vecz^{(t)}$ in $\cY$ and $\cN$:

* In both $\cY$ and $\cN$, $\vecx^*$ is distributed uniformly over $[q]^n$.

* In both $\cY$ and $\cN$ the matrix $M^{(t)}\in\{0,1\}^{\alpha kn\times n}$ is chosen uniformly (and independently of $\vecx^*$) among matrices with exactly one $1$ per row and at most one $1$ per column.

* The vector $\vecz^{(t)}$ is determined from $M^{(t)}$ and $\vecx^*$ as follows. Sample a random vector $\vecb^{(t)}\in (\cF\times[q]^k)^{\alpha kn}$ whose distribution differs in $\cY$ and $\cN$. Specifically, let $\vecb^{(t)}=(\vecb^{(t)}(1),\dots,\vecb^{(t)}(\alpha n))$ be sampled from one of the following distributions (independent of $\vecx^*$ and $M$):

* $\cY$:  Each $\vecb^{(t)}(i)=(f_i,\tilde{\vecb}(i))\in\cF\times[q]^k$ is sampled independently according to $\cD_Y$.

* $\cN$:  Each $\vecb^{(t)}(i)=(f_i,\tilde{\vecb}(i))\in\cF\times[q]^k$ is sampled independently according to $\cD_N$.

We now set $\vecz^{(t)}=(f_i,\tilde{z}_i)$ where $\tilde{z}_i=1$ iff $ = (M^{(t)} \vecx^*)= \tilde{\vecb}^{(t)}(i)$.

If $\cF \subseteq\{f:[q]^k\to\{0,1\}\}$, then given an instance $\vecsigma = (\vecx^*,M^{(1)},\dots,M^{(T)},\vecz^{(1)},\dots,\vecz^{(T)})$,  we will let $\Psi(\vecsigma)$ represent the associated instance of $\maxF$ as described in <ref>.

Note that the instance $\Psi(\vecsigma)$ obtained in the  and  cases of $(\cF,\cD_Y,\cD_N,T)$- are distributed exactly according to instances derived in the  and  cases of $(\cF,\cD_Y,\cD_N,T,\cD_0,\tau=0)$- and thus <ref> can still be applied to conclude that  instances usually satisfy $\val_{\Psi(\vecsigma)} \geq \gamma - o(1)$ and  instances usually satisfy $\val_{\Psi(\vecsigma)} \leq \beta - o(1)$. We will use this property when proving <ref>.

We start by showing the  problems above do not have low-communication protocols when the marginals of $\cD_Y$ and $\cD_N$ match.

Let $\cF$ be a finite set, $k,q,T\in\N$, $\cD_Y,\cD_N\in \Delta(\cF \times [q]^k)$, and let $\alpha\in(0,1/k]$.
Suppose there is a protocol $\Pi$ that solves $(\cF,\cD_Y,\cD_N,T)$- on instances of length $n$ with advantage $\Delta$ and space $s$, then there is a one-way protocol for $(\cF,\cD_Y,\cD_N)$- on instances of length $n$ using at most $s(T-1)$ bits of communication and achieving advantage at least $\Delta/T$.

Let us first fix the randomness in $\Pi$ so that it becomes a deterministic protocol. Note that by an averaging argument the advantage of $\Pi$ does not decrease. Recall that $\cY$ and $\cN$ are Yes and No input distribution of $(\cF,\cD_Y,\cD_N,T)$- and we have

\[
\Pr_{X\sim\cY}[\Pi(X)=\yes]-\Pr_{X\sim\cN}[\Pi(X)=\yes]\geq\Delta \, .
\]

Now, we define the following distributions $\cD_0,\dots,\cD_{T}$. Let $\cD_0=\cY$ and $\cD_{T}=\cN$. For each $t\in[T-1]$, we define $\cD_t$ to be the distribution of input instances of $(\cF,\cD_Y,\cD_N,T)$- by sampling $\vecb^{(t')}(i)$ independently according to $\cD_Y$ (resp. $\cD_N$) for all $t'\leq t$ (resp. $t'>t$) and $i$ (see <ref> to recall the definition).  Next, for each $t\in[T]$, let

\[
\Delta_t=\Pr_{X\sim\cD_t}[\Pi(X)=\yes]-\Pr_{X\sim\cD_{t-1}}[\Pi(X)=\yes] \, .
\]

Observe that $\sum_{t\in[T]}\Delta_t=\Delta$ and hence there exists $t^*\in[T]$ such that $\Delta_{t^*}\geq\Delta/T$.

Now, we describe a protocol $\Pi'$ for $(\cF,\cD_Y,\cD_N)$- as follows. On input $(\vecx^*,M,\vecz)$, Alice receives $\vecx^*$ and Bob receives $(M,\vecz)$. Alice first samples matrices $M^{(1)},\dots,M^{(t^*-1)},M^{(t^*+1)},\dots,M^{(T)}$ as the second item in <ref>. Next, Alice samples $\vecb^{(t')}(i)=(f_i,\tilde{\vecb}^{(t')}(i))$ according to $\cD_Y$ (resp. $\cD_N$) for all $t'<t^*$ (resp. $t'>t^*$) and $i\in[\alpha nT]$ and sets $\vecz^{(t')}(i)=(f_i,\tilde{z}_i)$ as the third item in <ref>. Note that this is doable for Alice because she possesses $\vecx^*$. Finally, Alice sends $\{\Pi^{(t')}(M^{(t')},\vecz^{(t')})\}_{t'\in[T]\backslash\{t^*\}}$ to Bob. After receiving Alice's message $(X^{(1)},\dots,X^{(t^*-1)},X^{(t^*+1)},\dots,X^{(T)})$, Bob computes $\Pi^{(t^*)}(M,\vecz)$ and outputs $\Pi'(M,\vecz)=\Pi_{\text{ref}}(X^{(1)},\dots,X^{(t^*-1)},\Pi^{(t^*)}(M,\vecz),X^{(t^*+1)},\dots,X^{(T)})$.

It is clear from the construction that the protocol $\Pi'$ uses at most $s(T-1)$ bits of communication. To see $\Pi'$ has advantage at least $\Delta/T$, note that if $(\vecx^*,M,\vecz)$ is sampled from the Yes distribution $\cY_{\textsf{SD}}$ of $(\cF,\cD_Y,\cD_N)$-, then $((M^{(1)},\vecz^{(1)}),\dots,(M^{(t^*-1)},\vecz^{(t^*-1)}),(M,\vecz),(M^{(t^*+1)},\vecz^{(t^*+1)}),\dots,(M^{(T)},\vecz^{(T)}))$ follows the distribution $\cD_{t^*}$. Similarly, if $(\vecx^*,M,\vecz)$ is sampled from the No distribution $\cN_{\textsf{SD}}$ of $(\cF,\cD_Y,\cD_N)$-, then $((M^{(1)},\vecz^{(1)}),\dots,(M^{(t^*-1)},\vecz^{(t^*-1)}),(M,\vecz),(M^{(t^*+1)},\vecz^{(t^*+1)}),\dots,(M^{(T)},\vecz^{(T)}))$ follows the distribution $\cD_{t^*-1}$. Thus, the advantage of $\Pi'$ is at least

\begin{align*}
=\, &\Pr_{X\sim\cD_{t^*}}[\Pi(X)=\yes]-\Pr_{X\sim\cD_{t^*-1}}[\Pi(X)=\yes]=\Delta_{t^*}\geq\Delta/T \, .
\end{align*}

We conclude that there is a one-way protocol for $(\cF,\cD_Y,\cD_N)$- using at most $s(T-1)$ bits of communication achieving advantage at least $\Delta/T$.

As an immediate consequence of <ref> and <ref> we get that $(\cF,\cD_Y,\cD_N,T)$- requires $\Omega(\sqrt{n})$ bits of communication when the marginals of $\cD_Y$ and $\cD_N$ match.

For every $k,q\in\N$, there exists $\alpha_0 > 0$ such that for every $\alpha\in(0,\alpha_0)$ and $\delta>0$ the following holds: For every finite set $\cF$ and $T\in\N$ and every pair of distributions $\cD_Y,\cD_N\in \Delta(\cF \times [q]^k)$ with $\vecmu(\cD_Y) = \vecmu(\cD_N)$,
there exists $\tau > 0$ and $n_0$ such that for every $n \geq n_0$, every protocol for $(\cF,\cD_Y,\cD_N,T)$- achieving advantage $\delta$ on instances of length $n$ requires $\tau\sqrt{n}$ bits of communication.

We are now ready to prove <ref>.

§.§.§ Proof of Theorem <ref>

The proof is a straightforward combination of <ref> and <ref>
and so we pick parameters so that all these are applicable.

Given $\epsilon$ and $k$, let $\alpha^{(1)}_0$ be as given by <ref> and let $\alpha^{(2)}_0$ be as given by <ref>. Let $\alpha = \min\{\alpha^{(1)}_0,\alpha^{(2)}_0\}$. Given this choice of $\alpha$, let $T_0$ be as given by <ref>. We set $T = T_0$ below. Let $n$ be sufficiently large.

Throughout this proof we will be considering integer weighted instances of $\maxF$ on $n$ variables with constraints. Note that such an instance $\Psi$ can be viewed as a vector in $\Z^N$ where $N = O(|\cF|\times n^k)$ represents the number of possibly distinct constraints applications on $n$ variables.
Let $\Gamma = \{\Psi | \val_\Psi \geq \gamma - \epsilon\}$.
Let $B = \{\Psi | \val_\Psi \leq \beta + \epsilon\}$.
Suppose there exists a sketching algorithm $\ALG_1$ that solves $(\gamma-\epsilon,\beta+\epsilon)$-($\cF$) using at most $s(n)$ bits of space. Note that $\ALG_1$ must achieve advantage at least $1/3$ on the problem $(\Gamma,B)$.
By running several independent copies of $\ALG_1$ and thresholding appropriately, we can get an algorithm $\ALG_2$ with space $O(s)$ and advantage $1 - \frac{1}{100}$ solving $(\Gamma,B)$.

Now, let $\COMP$ and $\COMB$ be the compression and combination functions as given by this sketching algorithm (see <ref>). We use these to design a protocol for $(\cF,\cD_Y,\cD_N,T)$- as follows.

Let $(M^{(t)},\vecz^{(t)})$ denote the input to the $t$-th player in $(\cF,\cD_Y,\cD_N,T)$-. Each player turn his/her inputs into $\Psi^{(t)}=(C^{(t)}_1,\dots,C^{(t)}_{m_t})$
where $C^{(t)}_i$ corresponds to the constraint $(\vecj^{(t)}(i),f_i^{(t)})$ with $\vecj^{(t)}_i\in[n]^k$ the indicator vector for the $i$-th hyperedge of $M^{(t)}$. Next, the players use the shared randomness Note that currently we are sloppy in <ref> about the randomness used in a sketching algorithm.
Good point - should at least mention what common randomness is in sketching in that definition.Please take a look at the new definition of <ref>! to compute the sketch of his/her input $\COMP(\sum_iC_i^{(t)})$ and send it to the referee. Finally, the referee computes the sketch for all streams $\COMB( \COMP(\sum_iC^{(1)}_i),\COMP(\sum_iC^{(2)}_i),\dots,\COMP(\sum_iC^{(T)}_i))$ and outputs the answer correspondingly.

To analyze the above, note that the communication is $O(s)$. Next, by the advantage of the sketching algorithm, we have that

\begin{equation}
\min_{\Psi \in \Gamma}[\ALG_2(\Psi) = 1] - \max_{\Psi \in B}[\ALG_2(\Psi) = 1] \geq 1-12/100.
\label{eq:dyn-one}
\end{equation}

Now we consider what happens when $\Psi \sim \cY_{\simul,n}$ and $\Psi \sim \cN_{\simul,n}$. By <ref> we have that $\Pr_{\Psi \sim \cY_{\simul,n}}[\Psi \in \Gamma] \geq  1 - o(1)$ and $\Pr_{\Psi \sim \cN_{\simul,n}}[\Psi \in B] \geq  1 - o(1)$. Combining with <ref> we thus get

\[
\Pr_{\Psi \sim \cY_{\simul,n}}[\ALG_2(\Psi) = 1] - \Pr_{\Psi \sim \cN_{\simul,n}}[\ALG_2(\Psi) = 1] \geq 1 - 12/100 - o(1) \geq 1/2,
\]

We thus get that there is a $O(s)$ simultaneous communication protocol for $(\cF,\cD_Y,\cD_N,T)$- with at least advantage $1/2$.

Now we conclude by applying <ref> with $\delta = 1/2$ to get that $s = \Omega(\sqrt{n})/T = \Omega(\sqrt{n})$, thus yielding the theorem.

Rest of the stuff below from old writeup. Probably not needed, though we may use pieces of the proof above.

§ STREAMING SPACE LOWER BOUND FOR MAX-CSP(F)

In this section we prove the following theorem:

Update following theorem to dynamic. Include insertion-only theorem

For every $q,k \in \N$, every family of functions $\cF \subseteq \{f:[q]^k \to \{0,1\}\}$ and for every $0 \leq \beta<\gamma \leq 1$ if $\kgyf \cap \kbnf \neq \emptyset$, then for every $\epsilon>0$,  the $(\gamma-\eps,\beta+\eps)$-$\maxF$ requires $\Omega(\sqrt{n})$ space. Furthermore, if $\gamma = 1$, then $(1,\beta+\epsilon)$-$\maxF$ requires $\Omega(\sqrt{n})$ space.

For every $0 \leq \beta < \gamma \leq 1$,  $k,q\in\N$, $\cF \subseteq\{f:[q]^k\to\{0,1\}\}$ and $\epsilon,\delta > 0$ there exists $n_0$ and $\delta > 0$ such that the following holds.
If $\cD_Y \in \sgyf$ and $\cD_N \in \sbnf$ with $\vecmu(\cD_Y) = \vecmu(\cD_N)$ and $\cA$ is a space $s$ streaming algorithm for $(\gamma-\epsilon,\beta+\epsilon)$-$\maxF$ with advantage
$\delta$, then there exists $\cD'_Y$ and $\cD'_N$ with $\vecmu(\cD'_Y) = \vecmu(\cD'_N)$, and a protocol achieving advantage $\delta'$ solving $(\cD'_Y,\cD'_N)$-SD on instances of length $n$ for every $n \geq n_0$ using $O(s)$ bits of communication. Furthermore, if $\gamma = 1$, then an algorithm for $(1,\beta+\epsilon)$-$\maxF$ implies the existence of $\cD'_Y$, $\cD'_N$, and a protocol for $(\cD'_Y,\cD'_N)$-SD.

Equipped with <ref> and <ref>, we are ready to prove <ref>.
Let us fix $\alpha=\alpha_0$ as given in <ref>. Assume that there exists a streaming algorithm that uses space $s$ and solves $(\gamma-\eps,\beta+\eps)$-$\maxF$ with advantage $1/3$. Let $\cD_Y\in S_\gamma^Y$ and $\cD_N\in S_\beta^N$ be distributions with matching marginals: $\vecmu(\cD_Y)=\vecmu(\cD_N)$. By <ref>, there exist $\cD'_Y$ and $\cD'_N$ with $\vecmu(\cD'_Y) = \vecmu(\cD'_N)$, and a protocol achieving advantage $\delta'>0$ solving $(\cD'_Y,\cD'_N)$-SD on instances of length $n$ for every $n \geq n_0$ using $O(s)$ bits of communication. Finally, <ref> implies that this protocol must use at least $\tau\sqrt{n}$ bits of communication for a constant $\tau>0$. In particular, the space complexity of the assumed streaming algorithm for $(\gamma-\eps,\beta+\eps)$-$\maxF$ is $s\geq\Omega(\tau\sqrt{n})=\Omega(\sqrt{n})$. The case of $\gamma=1$ follows by the corresponding clause of <ref>.

§ HARDNESS OF ADVICE-SIGNAL-DETECTION WITH UNIFORM MARGINALS

The goal of this section is to prove a variant of <ref>  that will be used in  <ref> and <ref> for a proof of the general case of <ref>. Recall that in the $(\cD_Y,\cD_N)$- problem $|\cF|=1$, so we omit $\cF$. The main result of this section, presented in <ref>, gives an $\Omega(\sqrt{n})$ lower bound on the communication complexity of $(\cD_Y,\cD_N)$- for distributions with matching marginals $\vecmu(\cD_Y)=\vecmu(\cD_N)$ for the case when (i) the alphabet is Boolean $\{-1,1\}$ [Throughout this section we use $\{-1,1\}$ to denote the Boolean domain.], (ii) the marginals are uniform $\vecmu(\cD_Y)=\vecmu(\cD_N)=0^k$, but (iii) both players also receive a specific advice vector $\veca$. We define the corresponding Advice-SD communication game below.

In order to prove the hardness of Advice-SD, we first recall the Randomized Mask Detection (RMD) communication game [8], define its version with advice, Advice-RMD, and prove an $\Omega(\sqrt{n})$ lower bound on the communication complexity of this game in <ref>. The proof of the main result of this section, <ref>, will then follow from the corresponding lower bounds for Advice-RMD in <ref>.

In order to prove the hardness of Advice-SD, we first define the Randomized Mask Detection with advice (Advice-RMD) communication game, and prove an $\Omega(\sqrt{n})$ lower bound on the communication complexity of this game in <ref>. The proof of the main result of this section, <ref>, will then follow from the corresponding lower bounds for Advice-RMD in <ref>.

§.§ Hardness of

In this section we state a theorem that establishes hardness of  in the Boolean setting and with uniform marginals while allowing for advice. The proof of this theorem is postponed to <ref>. First we define the  one-way communication game.

Let $n,k\in\mathbb{N}, \alpha\in(0,1)$, where $k$ and $\alpha$ are constants with respect to $n$, and $\alpha n$ is an integer less than $n/k$.
For a pair $\cD_Y$ and $\cD_N$ of distributions over $\{-1,1\}^k$, we consider the following two-player one-way communication problem $(\cD_Y,\cD_N)$-.

* The generator samples the following objects:

* $\vecx^* \sim \textsf{Unif}(\{-1,1\}^n)$.

* $\Gamma \in S_n$ is chosen uniformly among all permutations of $n$ elements.

* We let $M \in \{0,1\}^{k\alpha n \times n}$ be a partial permutation matrix capturing $\Gamma^{-1}(j)$ for $j \in [k\alpha n]$. Specifically, $M_{ij} = 1$ if and only if $j = \Gamma(i)$. We view $M = (M_1,\ldots,M_{\alpha n})$ where each $M_i \in \{0,1\}^{k \times n}$ is a block of $k$ successive rows of $M$.

* $\vecb = (\vecb(1),\ldots,\vecb(\alpha n))$ is sampled from one of the following distributions:

* () each $\vecb(i) \in \{-1,1\}^k$ is sampled according to $\cD_Y$.

* () each $\vecb(i)  \in \{-1,1\}^k$ is sampled according to $\cD_N$.

* $\vecz=M\vecx^* \odot \vecb$, where $\odot$ denotes the coordinate-wise product of the elements.

* Define a vector $\veca\in [k]^n$ as $a_j =i$ where $i = \Gamma^{-1}(j) \pmod k$ for every $j \in [n]$.

* Alice receives $\vecx^*$ and $\veca$ as input.

* Bob receives $M$, $\vecz$, and $\veca$ as input.

We follow the approach of [12, 8] to prove the following theorem showing a $\Omega(\sqrt{n})$ communication lower bound for Boolean . We postpone the proof to <ref>.

We follow the approach of [12] to prove the following theorem showing a $\Omega(\sqrt{n})$ communication lower bound for Boolean . We postpone the proof to <ref>.

For every $k\in\N$, and every pair of distributions $\cD_Y,\cD_N \in \Delta(\{-1,1\}^k)$ with uniform marginals $\vecmu(\cD_Y)=\vecmu(\cD_N)=0^k$ there exists $\alpha_0>0$ such that for every $\alpha\leq\alpha_0$ and $\delta > 0$ there exists $\tau>0$ such that every protocol for $(\cD_Y,\cD_N)$- achieving advantage $\delta$ requires $\tau\sqrt{n}$ bits of communication on instances of length $n$.

§.§ Hardness of

Let us first extend the definition of the Signal Detection () problem to the following  one-way communication game.

Let $n,k,q\in\mathbb{N}, \alpha\in(0,1)$, where $k$, $q$ and $\alpha$ are constants with respect to $n$, and $\alpha n/k$ is an integer less than $n$. For a pair $\cD_Y$ and $\cD_N$ of distributions over $[q]^k$, we consider the following two-player one-way communication problem $(\cD_Y,\cD_N)$-.

* The generator samples the following objects:

* $\vecx^* \sim \textsf{Unif}([q]^n)$.

* $\Gamma \in S_n$ is chosen uniformly among all permutations of $n$ elements.

* We let $M \in \{0,1\}^{k\alpha n \times n}$ be a partial permutation matrix capturing $\Gamma^{-1}(j)$ for $j \in [k\alpha n]$. Specifically, $M_{ij} = 1$ if and only if $j = \Gamma(i)$. We view $M = (M_1,\ldots,M_{\alpha n})$ where each $M_i \in \{0,1\}^{k \times n}$ is a block of $k$ successive rows of $M$.

* $\vecb = (\vecb(1),\ldots,\vecb(\alpha n))$ is sampled from one of the following distributions:

* () each $\vecb(i) \in [q]^k$ is sampled according to $\cD_Y$.

* () each $\vecb(i)  \in [q]^k$ is sampled according to $\cD_N$.

* $\vecz = (z_1,\ldots,z_{\alpha n}) \in \{0,1\}^{\alpha n}$
is determined from $M$, $\vecx^*$ and $\vecb$ as follows.
We let $z_i = 1$ if $M_i \vecx^* = \vecb(i)$, and $z_i = 0$ otherwise.

* Define a vector $\veca\in [k]^n$ as $a_j =i$ where $i = \Gamma^{-1}(j) \pmod k$ for every $j \in [n]$.

* Alice receives $\vecx^*$ and $\veca$ as input.

* Bob receives $M$, $\vecz$, and $\veca$ as input.

Almost immediately we get the following corollary for the  problem from <ref>.

For every $k\in\N$, and every pair of distributions $\cD_Y,\cD_N \in \Delta(\{-1,1\}^k)$ with uniform marginals $\vecmu(\cD_Y)=\vecmu(\cD_N)=0^k$ there exists $\alpha_0>0$ such that for every $0<\alpha\leq\alpha_0$ and $\delta > 0$ there exists $\tau > 0$, such that every protocol for $(\cD_Y,\cD_N)$-advice-SD achieving advantage $\delta$ requires $\tau\sqrt{n}$ bits of communication on instances of length $n$.

We show that a protocol achieving advantage $\delta$ in the $(\cD_Y,\cD_N)$- game with $s$ bits of communication implies a protocol achieving advantage $\delta$ for the $(\cD_Y,\cD_N)$- game with $s$ bits of communication. Then the lower bounds of <ref> for distributions with matching marginals will finish the proof.

Assume that there exists Bob's algorithm $\cB(M, \vecz, \veca, \text{Alice's message})$ that distinguishes $\vecb_i\sim\cD_Y$ and $\vecb_i\sim\cD_N$ with advantage $\delta$ in the  game. For the  game, we keep the same algorithm for Alice, and modify Bob's algorithm as follows. Bob receives $M\in\{0,1\}^{k\alpha n \times n}, \vecz\in\{-1,1\}^{k\alpha n}, \veca$, and Alice's message, and partitions $\vecz=(\vecz_1,\ldots,\vecz_{\alpha n})$ where $\vecz_i\in\{-1,1\}^{k}$. For each $i\in[\alpha n]$, Bob computes $\widetilde{z}_i\in\{0,1\}$ as follows: $\widetilde{z}_i=1$ if and only if $\vecz_i=1^k$. Now Bob sets $\vecz'=(\widetilde{z}_1,\ldots,\widetilde{z}_{\alpha n})\in\{0,1\}^{\alpha n}$, and outputs $\cB(M, \vecz', \veca, \text{Alice's message})$. It is easy to see that in both $\yes$ and $\no$ cases, the distribution of the vectors $\vecz'$ computed by Bob is the distribution of vectors $\vecz$ sampled in the $(\cD_Y,\cD_N)$- game. Thus, the protocol achieves advantage $\delta$ for the $(\cD_Y,\cD_N)$- game using $s$ bits of communication as desired.

§.§ Proof of Theorem <ref>

Our proof of <ref> follows the methodology of [12] with some modifications as required by the Advice-RMD formulation. Their proof uses Fourier analysis to reduce the task of proving a communication lower bound to that of proving some combinatorial identities about randomly chosen matchings. We follow the same approach and this leads us to different conditions about randomly chosen hypermatchings which requires a fresh analysis in <ref>.

In order to prove <ref> we follow the approach of [12, 8] with the main difference in the analysis of a certain combinatorial problem in <ref>.

Without loss of generality in the following we assume that $n$ is a multiple of $k$. A vector $\veca\in [k]^n$ is called an advice vector if for every $i\in[k], \, |\{j\colon a_j=i\}|=n/k$.
For an advice vector $\veca\in [k]^n$, we say that a partial permutation matrix $M \in \{0,1\}^{k\alpha n \times n}$ of a permutation $\Gamma$ is $\veca$-respecting if for every $i\in[k\alpha n]$ and $j\in[n]$, $M_{ij}=1$ if and only if $a_j =i \pmod k$. Intuitively, $\veca$ is the advice vector that tells you which congruence class $\Gamma(j)$ lies in.

For each advice vector $\veca\in [k]^n$, each $\veca$-respecting partial permutation matrix $M \in \{0,1\}^{k\alpha n \times n}$, distribution $\cD$ over $\{-1,1\}^k$, and a fixed Alice's message, the posterior distribution function $p_{M,\cD,\veca}:\{-1,1\}^{k \alpha n}\rightarrow[0,1]$ is defined as follows. For each $\vecz\in\{-1,1\}^{k \alpha n}$, let

\[
p_{M,\cD,\veca}(\vecz) := \Pr_{\substack{\vecx^*\in\{-1,1\}^n\\\vecb\sim\cD^{\alpha n}}}[\vecz=(M\vecx^*)\odot\vecb\ |\ M, \ \veca,\ \text{Alice's message}]=\Exp_{\vecx^*\in A}\Exp_{\vecb\sim\cD^{\alpha n}}[\mathbf{1}_{\vecz=(M \vecx^*)\odot \vecb}] \,,
\]

where $A\subset\{-1,1\}^n$ is the set of Alice's inputs that correspond to the message.

Let $U$ be the uniform distribution over $\{-1,1\}^k$. Lemma 6.4 in [8] bounds from above the expression $\Exp_{M,\ M \text{ is } \veca\text{-resp.}}[\|p_{M,\cD,\veca}-\unif(\{-1,1\}^{k\alpha n})\|_{tvd}^2]$ for the case without the advice vector $\veca$ using a combinatorial quantity. An inspection of the proof of Lemma 6.4 in [8], reveals that an analogous statement holds in the case when the advice vector $\veca$ is present. We provide a proof of this bound for completeness in <ref> below.
=0[Lemma 6.4 in [8]]
Let $\veca\in [k]^n$, $A\subseteq\{-1,1\}^n$, and $f:\{-1,1\}^n\rightarrow\{0,1\}$ be the indicator function of $A$. Let $k\in\mathbb{N}$ and $\alpha\in(0,1/100k)$. Let $\cD$ be a distribution over $\{-1,1\}^k$ such that $\mathbb{E}_{\veca\sim\cD}[a_j]=0$ for all $j\in[k]$.

\[
\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}[\|p_{M,\cD,\veca}-U\|_{tvd}^2]\leq\frac{2^{2n}}{|A|^2}\sum_{\ell\geq2}^{k \alpha n}h(\ell)\cdot\sum_{\substack{\vecv\in\{0,1\}^n\\|\vecv|=\ell}}\widehat{f}(\vecv)^2 \, ,
\]

where $U\sim\unif(\{-1,1\}^{k\alpha n})$ and for each $\ell\in[n]$,

\[
h(\ell)=\max_{\substack{\vecv_\ell\in\{0,1\}^n\\|\vecv_\ell|=\ell}}  \Pr_{\substack{M\\M \text{is } \veca\text{-resp.}}}\left[\exists \vecs\in\{0,1\}^{k\alpha n}\backslash\{0^{k \alpha n}\},\ |\vecs(i)|\neq1\, \forall i,\ M^\top \vecs=\vecv_\ell\right] \, .
\]

Here for a vector $\vecs\in\{0,1\}^{k\alpha n}$ and integer $i\in[\alpha n]$, $\vecs(i)\in\{0,1\}^k$ denotes the $i$-th group of $k$ coordinates of $\vecs$.

Observe that

\[
\|p_{M,\cD,\veca}-U\|_2^2=\sum_{\vecs\in\{0,1\}^{k\alpha n}}\left(\widehat{p}_{M,\cD,\veca}(\vecs)-\widehat{U}(\vecs)\right)^2=\sum_{\vecs\in\{0,1\}^{k\alpha n}\backslash\{0^{k\alpha n}\}}\widehat{p}_{M,\cD,\veca}(\vecs)^2 \,.
\]

Now by the Cauchy–Schwarz inequality we have that

\begin{align}
\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}\left[\|p_{M,\cD,\veca}-U\|_{tvd}^2\right]&\leq2^{2k\alpha n}\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}\left[\|p_{M,\cD,\veca}-U\|_2^2\right]\nonumber\\
&=2^{2k\alpha n}\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}\left[\sum_{\vecs\in\{0,1\}^{k\alpha n}\backslash\{0^{k\alpha n}\}}\widehat{p_{M,\cD,\veca}}(\vecs)^2\right] \, . \label{eq:upper bound tvd 1 wise}
\end{align}

The following claim shows that the Fourier coefficients of the posterior distribution $p_{M,\cD,\veca}$ can be bounded from above by a certain Fourier coefficient of the indicator function $f$. Let's define $\GOOD:=\{\vecs\in\{0,1\}^{k\alpha n}\, |\, |\vecs(i)|\neq1\ \forall i\}$.

\[
\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}[\|p_{M,\cD,\veca}-U\|_{tvd}^2]\leq\frac{2^{2n}}{|A|^2}\sum_{\vecs\in\GOOD\backslash\{0^{k\alpha n}\}}\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}\left[\widehat{f}(M^\top \vecs)^2\right] \, .
\]

Observe that

\begin{align*}
\widehat{p_{M,\cD,\veca}}(\vecs)&= \frac{1}{2^{k\alpha n}}\sum_{\vecz\in\{-1,1\}^{k\alpha n}}p_{M,\cD,\veca}(\vecz)\prod_{\substack{i\in[\alpha n],j\in[k]\\s(i)_{j}=1}}z(i)_{j} \, .
\intertext{Recall that $p_{M,\cD,\veca}(\vecz)=\Exp_{\vecx^*\in A}\Exp_{\vecb\sim\cD^{\alpha n}}[\mathbf{1}_{\vecz=M \vecx^*\odot \vecb}]$, the equation becomes}
&=\frac{1}{2^{k\alpha n}}\cdot\Exp_{\vecx^*\in A}\left[\prod_{\substack{i\in[\alpha n],j\in[k]\\s(i)_{j}=1}}(M \vecx^*)_{i,j}\right]\Exp_{\vecb\sim\cD^{\alpha n}}\left[\prod_{\substack{i\in[\alpha n],j\in[k]\\s(i)_{j}=1}}b(i)_{j}\right] \, .
% &=\frac{1}{2^{\alpha kn}}\cdot\Exp_{\vecx^*\in A}(-1)^{s^\top M \vecx^*}\Exp_{b_1,\dots,b_{\alpha n}\sim\cD}(-1)^{s^\top b} \, .
\intertext{Since $\Exp_{\veca\sim\cD}[a_j]=0$ for all $j\in[k]$, the right most sum is $0$ if there exists $i$ such that $|\vecs(i)|=1$. This equation becomes}
&\leq\frac{1}{2^{k\alpha n}}\cdot\left|\Exp_{\vecx^*\in A}\left[\prod_{\substack{i\in[\alpha n],j\in[k]\\s(i)_{j}=1}}(M \vecx^*)_{i,j}\right]\right|\cdot\mathbf{1}_{\vecs\in\GOOD} \, .
\intertext{Note that as each row and column of $M$ has at most $1$ non-zero entry, we have}
&=\frac{1}{2^{k\alpha n}}\cdot\left|\Exp_{\vecx^*\in A}\left[\prod_{\substack{i\in[n]\\(M^\top \vecs)_{i}=1}} \vecx^*_{i}\right]\right|\cdot\mathbf{1}_{\vecs\in\GOOD}
\end{align*}

Now we relate the above quantity to the Fourier coefficients of $f$. Recall that $f$ is the indicator function of the set $A$ and hence for each $\vecv\in\{0,1\}^n$, we have

\[
\widehat{f}(\vecv)=\frac{1}{2^n}\sum_{\vecx^*}f(\vecx^*)\prod_{i\in[n]:v_i=1}\vecx^*_i=\frac{1}{2^n}\sum_{\vecx^*\in A}\prod_{i\in[n]:v_i=1}\vecx^*_i \, .
\]

Thus, the Fourier coefficient of $p_M$ can be bounded as follows.

\begin{equation}\label{eq:1 wise fourier coefficient}
\widehat{p_{M,\cD,\veca}}(\vecs)\leq\frac{1}{2^{\alpha kn}}\cdot\frac{2^n}{|A|}\left|\widehat{f}(M^\top \vecs)\right|\cdot\mathbf{1}_{\vecs\in\GOOD} \, .
\end{equation}

By plugging <ref> into <ref>, we have the desired bound and complete the proof of <ref>.

Next, by <ref>, we have

\begin{align*}
\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}[\|p_{M,\cD,\veca}-U\|_{tvd}^2]&\leq\frac{2^{2n}}{|A|^2}\sum_{\vecs\in\GOOD\backslash\{0^{\alpha kn}\}}\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}\left[\widehat{f}(M^\top \vecs)^2\right] \, .
\intertext{Since for a fixed $M$, the map $M^\top$ is injective, the right hand side of the above inequality has the following combinatorial form.}
&=\frac{2^{2n}}{|A|^2}\sum_{\vecv\in\{0,1\}^n\backslash\{0^n\}}\Pr_{\substack{M\\M \text{is } \veca\text{-resp.}}}\left[\exists \vecs\in\GOOD\backslash\{0^{k\alpha n}\},\ M^\top \vecs=\vecv\right]\widehat{f}(\vecv)^2 \, .
\intertext{By symmetry, the above probability term will be the same for $\vecv$ and $\vecv'$ having the same Hamming weight. Recall that $$h(\ell)=\max_{\substack{\vecv_\ell\in\{0,1\}^n\\|\vecv_\ell|=\ell}}  \Pr_{\substack{M\\M \text{is } \veca\text{-resp.}}}\left[\exists \vecs\in\GOOD\backslash\{0^{k\alpha n}\},\ M^\top \vecs=\vecv_\ell\right] \,,$$ this equation becomes}
&\leq\frac{2^{2n}}{|A|^2}\sum_{\ell\geq1}^nh(\ell)\cdot\sum_{\substack{\vecv\in\{0,1\}^n\\|\vecv|=\ell}}\widehat{f}(\vecv)^2 \, .
\intertext{
Note that for $\ell=1$ and every $\ell>\alpha kn$, $h(\ell)=0$ by definition. Thus, this expression simplifies to the following.}
&=\frac{2^{2n}}{|A|^2}\sum_{\ell\geq2}^{\alpha kn}h(\ell)\cdot\sum_{\substack{\vecv\in\{0,1\}^n\\|\vecv|=\ell}}\widehat{f}(\vecv)^2 \, .
\end{align*}

This completes the proof of <ref>.

Now we bound from above the combinatorial quantity $h(\ell)$ from <ref>.

For every $0<\alpha\in(0,1/100k^2)$ and $\ell\in[k \alpha n]$, we have

\[
\Pr_{\substack{M\\M \text{is } \veca\text{-resp.}}}\left[\exists \vecs\neq0,\ |\vecs(i)|\neq1\ \forall i,\ M^\top \vecs=\vecv_\ell\right]
%\leq\frac{(2\ell k\alpha^{1/k})^{\ell}}{n^{\ell/2}} \, .
\leq\left(\frac{\ell}{n}\right)^{\ell/2} (e^3\alpha k^5)^{\ell/2} \,.
\]

By symmetry, without loss of generality we can fix the advice vector $\veca=(1^{n/k}2^{n/k}\ldots k^{n/k})$. For non-negative integers $\ell_1,\ldots,\ell_k$, we say that $\vecv_\ell\in\{0,1\}^n$ is an $(\ell_1,\ldots,\ell_k)$-vector if for every $i\in[k]$, $\vecv$ has exactly $\ell_i$ entries equal $1$ in the $i$th group of $n/k$ coordinates. For fixed values of $\ell_i$,
let us define

\[
h(\ell_1,\ldots,\ell_k)=\Pr_{\substack{M\\M \text{is } \veca\text{-resp.}}}\left[\exists \vecs\neq0,\ |\vecs(i)|\neq1\ \forall i,\ M^\top \vecs \text{ is a } (\ell_1,\ldots,\ell_k) \text{-vector}\right] \, .
\]

We note that

\begin{align}\label{eq:hell}
h(\ell)=\max_{\substack{\ell_1,\ldots,\ell_k\geq0\\\sum_i \ell_i=\ell}} h(\ell_1,\ldots,\ell_k) \,.
\end{align}

An equivalent way to compute the probability $h(\ell_1,\ldots,\ell_k)$ is to fix the matching $M=\{(i, n/k+i,\ldots,(k-1)n/k+i)| i\in[\alpha n] \}$, and to let $\vecv$ be a random $(\ell_1,\ldots,\ell_k)$-vector . Then

\begin{align}\label{eq:hbound}
\Pr_{\substack{\vecv\\ \vecv \text{ is } (\ell_1,\ldots,\ell_k)}}\left[\exists \vecs\neq0,\ |\vecs(i)|\neq1\ \forall i,\ M^\top \vecs=\vecv\right]
\, ,
\end{align}

where $V\subseteq\{0,1\}^n$ is the set of all $(\ell_1,\ldots,\ell_k)$-vectors, and $U =\{\vecu\in V\colon \exists \vecs\neq0,\ |\vecs(i)|\neq1\ \forall i,\ M^\top \vecs=\vecu\}$. From $\ell_1+\ldots+\ell_k=\ell$, the number of $(\ell_1,\ldots,\ell_k)$-vectors is

\begin{align}\label{eq:vbound}
|V|=\prod_{i=1}^k \binom{n/k}{\ell_i} \geq \binom{n/k}{\sum_{i=1}^k{\ell_i}}=\binom{n/k}{\ell} \geq \left(\frac{n}{k\ell}\right)^\ell \,,
\end{align}

where the first inequality uses that $n/k\geq k\alpha n\geq \ell$ for $\alpha\leq1/k^2$.

For a vector $\vecs\in\{0,1\}^{k\alpha n}$, let $T_\vecs=\{i\colon |\vecs(i)|>0\}$ be the set of indices of non-zero blocks of $\vecs$. In order to give an upper bound on the size of $U$, first we pick a set $T_\vecs$, and then we choose a vector $\vecu$ such that $M^\top \vecs=\vecu$ for some $\vecs$ corresponding to the set $T_\vecs$. Note that since for each $i\in T$, $\vecs(i)>0$ and $\vecs(i)\neq1$ by the definition of $h(\ell)$, the size of $t=|T|\leq k/2$. For every $t$, the number of ways to choose $T_\vecs$ is $\binom{\alpha n}{t}$. For a fixed $T_\vecs$, it remains to choose the $\ell$ coordinates of $\vecu$ among at most $kt$ non-zero coordinates of $\vecs$.
For a vector $\vecs\in\{0,1\}^{k\alpha n}$, let $T_\vecs=\{i\in[\alpha n]\colon |\vecs(i)|>0\}$ be the set of indices of non-zero blocks of $\vecs$. In order to give an upper bound on the size of $U$, first we pick a set $T$, and then we choose a vector $\vecu$ such that $M^\top \vecs=\vecu$ for some $\vecs$ with (i) $|\vecs(i)\neq1|$ for all $i$ and (ii) $T_\vecs=T$. Note that since for each $i\in T$, $\vecs(i)>0$ and $|\vecs(i)|\neq1$, the size of $t=|T|\leq \ell/2$. For every $t$, the number of ways to choose $T$ is $\binom{\alpha n}{t}$. For a fixed $T$, it remains to choose the $\ell$ coordinates of $\vecu$ among at most $kt$ non-zero coordinates of $\vecs$.
This gives us the following upper bound on the size of $|U|$.

\begin{align}\label{eq:boundingu}
\leq \max_{t\leq \ell/2} \binom{\alpha n}{t}\binom{kt}{\ell} \,.
\end{align}

The second term of the upper bound in <ref> can be bounded from above by
\[\binom{kt}{\ell} \leq \left(\frac{ekt}{\ell}\right)^{\ell} \leq \left(\frac{ek\ell/2}{\ell}\right)^{\ell}=\left(\frac{ek}{2}\right)^{\ell}\,. \]

Now we'll show that the first term of the upper bound in <ref> can be bounded from above by
$\left(\frac{2ek\alpha n}{\ell}\right)^{\ell/2}
If $\ell\geq 2\alpha n$, then

\[
\binom{\alpha n}{t} \leq 2^{\alpha n}\leq 2^{\ell/2} \leq \left(\frac{2ek\alpha  n}{\ell}\right)^{\ell/2} \,,
\]

where in the last inequality we use $\ell\leq k \alpha n$.
If $\ell <2\alpha n$, then $t\leq \ell/2 < \alpha n$, and

\[
\binom{\alpha n}{t} \leq \left(\frac{e\alpha n}{t}\right)^t \leq \left(\frac{2e\alpha n}{\ell}\right)^{\ell/2}<
\left(\frac{2ek \alpha n}{\ell}\right)^{\ell/2} \,.
\]

The above implies that

\begin{align}\label{eq:ubound}
\leq \max_{t\leq \min\{\alpha n, \ell/2\}} \binom{\alpha n}{t}\binom{kt}{\ell}
\leq \left(\frac{ek}{2}\right)^{\ell} \left(\frac{2ek \alpha n}{\ell}\right)^{\ell/2}
\leq \left(\frac{n}{\ell}\right)^{\ell/2} (e^3\alpha k^3)^{\ell/2} \,.
\end{align}

Finally, from <ref>,

\[
h(\ell)=\max_{\substack{\ell_1,\ldots,\ell_k\geq0\\\sum_i \ell_i=\ell}} h(\ell_1,\ldots,\ell_k)
\leq
\left(\frac{k\ell}{n}\right)^\ell \cdot \left(\frac{n}{\ell}\right)^{\ell/2} (e^3\alpha k^3)^{\ell/2}
\leq
\left(\frac{\ell}{n}\right)^{\ell/2} (e^3\alpha k^5)^{\ell/2}
\,.
\]

In <ref> below we give the final ingredient needed for the proof of <ref>. If $U$ is the uniform distribution over $\{-1,1\}^k$, then we show that for every large set $A\subseteq\{0,1\}^n$ of inputs $x$ corresponding to a fixed Alice's message (and a fixed advice $\veca$), $\Exp_{M,M \text{is } \veca\text{-resp.}}[\|p_{M,\cD,\veca}-U\|_{tvd}^2]$ is small.

For every $k\in\N$ there exists $\alpha_0>0$ such that for every $0<\alpha\leq\alpha_0, \delta\in(0,1)$, and $c\leq \frac{\delta \sqrt{n}}{100 \sqrt{\alpha k^5}}$ the following holds for all large enough $n$. If $\cD$ is a distribution over $\{-1,1\}^k$ such that for all $j\in[k],\, \Exp_{\veca\sim\cD}[a_j]=0$,
and $A\subseteq\{-1,1\}^n$ is of size $|A|\geq 2^{n-c}$, then

\[
\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}[\|p_{M,\cD,\veca}-U\|_{tvd}^2]\leq \frac{\delta^2}{16} \,.
\]

where $U\sim\unif(\{-1,1\}^{k\alpha n})$.

<ref> and <ref> imply that for every $A$ of size $|A|\geq 2^{n-c}$,

\[
\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}[\|p_{M,\cD,\veca}-U\|_{tvd}^2] \leq\frac{2^{2n}}{|A|^2}\cdot\sum_{\ell\geq2}^{k \alpha n}\left(\frac{\ell}{n}\right)^{\ell/2} (e^3\alpha k^5)^{\ell/2} \sum_{\substack{\vecv\in\{0,1\}^n\\|\vecv|=\ell}}\widehat{f}(\vecv)^2 \, .
\]

For every $\ell\in[4c]$, <ref> implies that

\begin{align*}
\frac{2^{2n}}{|A|^2}\sum_{\substack{\vecv\in\{0,1\}^n\\|\vecv|=\ell}}\widehat{f}(\vecv)^2&\leq\left(\frac{4\sqrt{2}c}{\ell}\right)^\ell \, .
\end{align*}

By the Parseval identity,
$\sum_{\vecv}\widehat{f}(\vecv)^2\leq1$. This gives us that

\begin{align*}
\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}[\|p_{M,\cD,\veca}-U\|_{tvd}^2]&\leq\sum_{\ell\geq2}^{4c}\left(\frac{\ell}{n}\right)^{\ell/2} (e^3\alpha k^5)^{\ell/2} \cdot\left(\frac{4\sqrt{2}c}{\ell}\right)^\ell+\frac{2^{2n}}{|A|^2}\cdot\max_{4c<\ell\leq k\alpha n}\left\{\left(\frac{\ell}{n}\right)^{\ell/2} (e^3\alpha k^5)^{\ell/2}\right\}\,.
\intertext{Recall that $c\leq \frac{\delta \sqrt{n}}{100 \sqrt{\alpha k^5}}$. Let $\alpha_0=\frac{1}{2e^3k^5}$. Then for every $\alpha\leq\alpha_0$, the max term on the right hand side is maximized by $\ell=4c+1$ for all large enough $n$,}
&\leq\sum_{\ell\geq2}^{4c}\left(\frac{32e^3\alpha k^5 c^2}{n\ell}\right)^{\ell/2} + \left(\frac{8e^3c\alpha k^5}{n}\right)^{2c} \\
&\leq \sum_{\ell\geq2}^{4c} \left(\frac{\delta^2}{30}\right)^{\ell/2}+\left(\frac{8e^3\delta\sqrt{\alpha}}{100\sqrt{k^3}\sqrt{n}}\right)^{2c}
\\
&<\frac{\delta^2}{16} \, .
\end{align*}

We are ready to finish the proof of <ref>.

Let us set $\tau=\frac{\delta}{200\sqrt{\alpha k^5}}$, and let $\alpha_0$ be as set in <ref>.
Suppose that there exists a one-way communication protocol for $(\cD_Y,\cD_N)$- that uses $s=\tau\sqrt{n}$ bits of communication and has advantage at least $\delta$. By the triangle inequality there must exist a protocol with advantage $\delta/2$ and $s$ bits of communication for either the $(\cD_Y,\cD_{unif})$- or the $(\cD_N,\cD_{unif})$- problem. Without loss of generality, we assume that $(\cD_Y,\cD_{unif})$- can be solved with advantage $\delta/2$. Then,

\[
\|p_{M,\cD_Y,\veca}-p_{M,\cD_{unif},\veca}\|_{tvd}\geq\frac{\delta}{2} \, .
\]

Without loss of generality, we can assume that Alice's protocol is deterministic. In other words, for every $\veca$, Alice's $s$-bit communication protocol partitions the set of $\{-1,1\}^n$ of inputs $x$ into $2^s$ sets $A_1,\ldots,A_{2^s}\subseteq\{-1,1\}^n$ according to the message sent by Alice. Therefore, at least $(1-\delta/4)$-fraction of inputs $x\in\{-1,1\}^n$ belongs to sets $A_i$ of size $|A_i|\geq \frac{\delta}{4}\cdot 2^{n-s}\geq 2^{n-c}$ for $c=s+1-\log\delta$. By <ref>, for every $A_i$ of size $|A_i|\geq2^{n-c}$,

\[
\|p_{M,\cD_Y,\veca}-p_{M,\cD_{unif},\veca}\|_{tvd}|_{\vecx^*\in A_i}
=\Exp_{\substack{M\\M \text{is } \veca\text{-resp.}}}[\|p_{M,\cD,\veca}-U\|_{tvd}|_{\vecx^*\in A_i}]
\leq \delta/4 \,.
\]

\begin{align*}
\|p_{M,\cD_Y,\veca}-p_{M,\cD_{unif},\veca}\|_{tvd}
&\leq \Pr[x\in A_i\colon |A_i|< 2^{n-c}]\\
&+\Pr[x\in A_i\colon |A_i|\geq 2^{n-c}]\cdot\|p_{M,\cD_Y,\veca}-p_{M,\cD_{unif},\veca}\|_{tvd}|_{\vecx^*\in A_i}\\
&\leq \delta/4 + (1-\delta/4)\cdot \delta/4\\
&<\delta/2 \,.
\end{align*}

§ HARDNESS OF SIGNAL DETECTION

In this section we extend the hardness result of the SD problems for the special distributions described in <ref> to the fully general setting, thus proving the following theorem.

The bulk of this section is devoted to proving that for every pair of distributions $\cD_Y$ and $\cD_N$, we can find a path (a sequence) of intermediate distributions $\cD_Y = \cD_0,\cD_1,\ldots,\cD_L = \cD_N$ such that adjacent pairs in this sequence are indistinguishable by a “basic” argument, where a basic argument is a combination of an indistinguishability result from <ref> and a shifting argument.

=0 We note here that the ideas and proofs in this section are based directly on <cit.>. The main change is to move from working with “cubes” (i.e., $\{-1,1\}^k$ for various $k$) to working with general product sets (i.e., $[q_1] \times \cdots \times [q_k]$ for various $k,q_1,\ldots,q_k$).

Our proof comes in the following steps:

* For every marginal vector $\vecmu$, we identify a canonical distribution $\cD_{\vecmu}$ that we use as the endpoint of the path. So it suffices to prove that for all $\cD$, $\cD$ is indistinguishable from $\cD_{\vecmu(\cD)}$, i.e., there is a path of finite length from $\cD$ to $\cD_{\vecmu(\cD)}$.

* We give a combinatorial proof that there is a path of finite length (some function of $k$) that takes us from an arbitrary distribution to the canonical one.

Putting these ingredients together, along with a proof that a “basic step” is indistinguishable  gives us the final theorem.

Let $\gd = [q_1]\times \cdots [q_k]$ where $\forall i, q_i\in \mathbb{N}$. We start with the definition of the chain and the canonical distribution. For a distribution $\cD \in \Delta(\gd)$, its support is the set  $\supp(\cD) = \{\veca\in \gd\, |\, \cD(\veca) > 0\}$.  For $\cD \in \gd$, we define the marginal vector $\vecmu(\cD) = (\mu_{i,\sigma})_{i \in [k], \sigma\in [q_i]}$ as $\mu_{i,\sigma} = \Pr_{\veca \sim \cD} [a_i = \sigma]$. Next, we consider the following partial order on $\gd$. For vectors $\veca,\vecb \in \gd$ we use the notation $\veca \leq \vecb$ if $a_i \leq b_i$ for every $i \in [k]$. Further we use $\veca < \vecb$ if $\veca \leq \vecb$ and $\veca \ne \vecb$.

We refer to a sequence $\veca(0)< \veca(1) < \cdots < \veca(\ell)$, $\veca(i) \in \gd$ for every $i \in \{0,\ldots,\ell\}$,  as a chain of length $\ell$. Note that chains in $\gd$ have length at most $\sum_{i=1}^k (q_i-1)$.

Given a vector of marginals $\vecmu=(\mu_{i,\sigma})_{i\in[k],\sigma\in[q_i]}$, there exists a unique distribution $\cD$ with matching marginals ($\vecmu(\cD)=\vecmu$) such that the support of $\cD$ is a chain. We call this the canonical distribution $\cD_\mu$ associated with $\vecmu$.

We will prove the proposition by applying induction on $\sum_{i=1}^k q_i$. In the base case when $\sum_{i=1}^k q_i = k$, there is only one point in the support of the distribution and the claim holds trivially. For  $\sum_{i=1}^k q_i > k$, define $h = \arg \min_{i\in[k]} \mu_{i,q_i}$ and $\tau = \mu_{h,q_h}$. Let $\tilde{q}_h = q_h-1$ and $\tilde{q}_i = q_i$, for $i\ne h$. Define a vector of marginals $\tilde{\vecmu}=(\tilde{\mu}_{i,\sigma})_{i\in[k],\sigma\in[\tilde{q}_i]}$ as follows: $\tilde{\mu}_{i,\sigma} = (\mu_{i,\sigma}-\tau)/(1-\tau)$ if $i\neq h$ and $\sigma=q_i$, and $\tilde{\mu}_{i,\sigma} = \mu_{i,\sigma}/(1-\tau)$ otherwise. By the induction hypothesis, there exists a unique distribution $\tilde{\cD}$ supported on a chain such that $\vecmu(\tilde{\cD})=\tilde{\vecmu}$. Observe that the distribution $\cD=(1-\tau)\tilde{\cD} + \tau \{(q_1,\dots,q_k)\}$ has marginal $\mu$ and is supported on a chain. We will now show that $\cD$ is the unique distribution with these properties. For a distribution $\cD\in\Delta([q_1]\times\cdots\times[q_k])$ and  $\vecv\in[q_1]\times\cdots\times[q_k]$, we define $\cD(\vecv) = \Pr_{\vecc\sim \cD}[\vecc=\vecv] $. Note that it suffices to prove that if $\cD'\in\Delta([q_1]\times\cdots\times[q_k])$ is supported on a chain and $\vecmu(\cD')=\vecmu$, then $\cD'(q_1,\dots,q_k)=\tau$. Clearly $\cD'(q_1,\dots,q_k)\le\tau$. Let $\vecu$ be lexicographically the largest vector smaller than $(q_1,\dots,q_k)$ in the support of $\cD'$. Let $r$ be an index where $\vecu_{r}<q_r$. Since $\cD'$ is supported on a chain, $\cD'(\vecv)=0$ for $\vecv\in[q_1]\times\cdots\times[q_k]$ such that $\vecv_r = q_r$ and $\vecv\neq (q_1,\dots,q_k)$. Hence $\mu_{r,q_r} = \cD'(q_1,\dots,q_k)$. Since $\tau = \min_{i\in[k]} \mu_{i,q_i}$, we have $\tau\le \mu_{r,q_r} = \cD'(q_1,\dots,q_k)$.

Next we define a potential associated with distributions. For a distribution $\cD \in \Delta(\gd)$ define its potential to be

\Phi(\cD) = \Exp_{\vecb\sim\cD}\left[ ~\left(\sum_{j\in[k]} b_j\right)^2 ~\right]\, .

We will show shortly that $\cD_{\vecmu}$ is the distribution with maximum potential among all distributions with marginals $\vecmu$. In the process of showing this we will introduce a “polarization operator” which maps a distribution $\cD$ to a new one that increases the potential for typical distributions. Since this operator is useful also for further steps, we start with defining this operator and analyzing its effect on the potential.

For $\vecu,\vecv \in \gd$, let
$\vecu' = \min\{\vecu,\vecv\}\triangleq(\min\{u_1,v_1\},\ldots,\min\{u_k,v_k\})$ and let
$\vecv' = \max\{\vecu,\vecv\}\triangleq(\max\{u_1,v_1\},\ldots,\max\{u_k,v_k\})$. We say $\vecu$ and $\vecv$ are incomparable if $\vecu \not\leq \vecv$ and $\vecv \not\leq \vecu$. Note that if $\vecu$ and $\vecv$ are incomparable then $\{\vecu,\vecv\}$ and $\{\vecu',\vecv' \}$ are disjoint[To see this, suppose $\vecu=\vecu'$, then we have $u_j=\min\{u_j,v_j\}$ for all $j\in[k]$ and hence $\vecu\leq\vecv$, which is a contradiction. The same analysis works for the other cases.].

Given a distribution $\cD \in \Delta(\gd)$ and incomparable elements $\vecu,\vecv\in \gd$, we define the $(\vecu,\vecv)$-polarization of $\cD$, denoted $\cD_{\vecu,\vecv}$, to be the distribution as given below. Let $\epsilon = \min\{\cD(\vecu),\cD(\vecv)\}$.

\[
\cD_{\vecu,\vecv}(\vecb) =\left\{\begin{array}{ll}
\cD(\vecb)-\epsilon     & ,\ \vecb\in\{\vecu,\vecv\} \\
\cD(\vecb)+\epsilon       & ,\ \vecb \in \{\vecu', \vecv' \} \\
\cD(\vecb) & ,\ \text{otherwise.}
\end{array}\right.
\]

We refer to $\epsilon(\cD,\vecu,\vecv) = \min\{\cD(\vecu),\cD(\vecv)\}$ as the polarization amount.

It can be verified that the polarization operator preserves the marginals, i.e., $\vecmu(\cD) = \vecmu(\cD_{\vecu,\vecv})$. Note also that this operator is non-trivial, i.e., $\cD_{\vecu,\vecv}=\cD$, if  $\{\vecu,\vecv\} \not\subseteq \supp(\cD)$.

[Indistinguishability of the polarization step]theorempolarizationstephardness
Let $n,k,q\in\N$, $\alpha\in(0,1)$ where $k,q,\alpha$ are constants with respect to $n$ and $\alpha n$ is an integer less than $n/k$. For a distribution $\cD\in\Delta([q]^k)$, incomparable vectors $\vecu,\vecv\in[q]^k$, and $\delta>0$, there exists $\tau>0$ such that every protocol for $(\cD,\cD_{\vecu,\vecv})$-SD  achieving advantage $\delta$ requires $\tau\sqrt{n}$ bits of communication.

We defer the proof of this theorem to <ref> and focus instead on the number of steps

Let $\cD\in \Delta(\{-1,1\}^k)$ be a distribution with marginal vector $\vecmu=\vecmu(\cD)$ and let $\vecu,\vecv\in \supp(\cD)$ be incomparable. Then we have $\Phi(\cD_{\vecu,\vecv}) > \Phi(\cD)$.

Will fill soon.

Will fill soon.

§.§ Finite upper bound on the number of polarization steps

In this section we prove that there is a finite upper bound on the number of polarization steps needed to move from a distribution $\cD \in \Delta(\gd)$ to the canonical distribution with marginal $\vecmu(\cD)$, i.e., $\cD_{\vecmu(\cD)}$. Together with the indistinguishability result from <ref> this allows us to complete the proof of <ref> by going from $\cD_Y$ to $\cD_{\vecmu(\cD_Y)}=\cD_{\vecmu(\cD_N)}$ and then to $\cD_N$ by using the triangle inequality for indistinguishability.

In this section we extend our considerations to functions $A:\gd \to \R^{\geq 0}$. Let $\cfk = \{A:\gd \to \R^{\geq 0}\}$. For $A \in \cfk$ and $i\in[k]$, let $\mu_{0}(A) = \sum_{\veca\in\gd} A(\veca)$. Note $\Delta(\gd) \subseteq \cfk$ and $A \in \Delta(\gd)$ if and only if $A\in\cfk$ and $\mu_0(A) = \sum_{\veca \in \gd} A(\veca) = 1$. We extend the definition of marginals, support, canonical distribution, and polarization operators to $\cfk$. In particular we let $\vecmu(A) = (\mu_0,(\mu_{i,\sigma})_{i\in[k],\sigma\in[q_i]})$ where $\mu_{i,\sigma} = \sum_{\veca \in \gd: \veca_i = \sigma}  A(\veca)$. We also define canonical function and polarization operators so as to preserve $\vecmu(A)$. So given arbitrary $A$, let $\cD = \frac{1}{\mu_0(A)}\cdot A$. Note $\cD\in \Delta(\gd)$. For $\vecmu  = (\mu_0,(\mu_{i,\sigma})_{i\in[k],\sigma\in[q_i]})$ where $\forall i, \sum_{\sigma\in [q_i]} \mu_{i,\sigma} = \mu_0$, we define $A_{\vecmu} = \mu_0\cdot \cD_{\vecmu'}$ where $\vecmu' = (\mu_{i,\sigma}/\mu_0)_{i\in[k],\sigma\in[q_i]}$ to be the canonical function associated with $\vecmu$.

For distribution $A\in\cfk$, where $\gd = [q_1]\times\cdots\times[q_k]$, let $N(A)$ be the smallest $t$ such that there exists a sequence $\vecA = A_0,A_1,\ldots,A_t$ such that $A_0 = A$, $A_t = A_{\vecmu(A)}$ is canonical and for every $i \in [t]$ it holds that there exists incomparable  $\vecu_i,\vecv_i \in \supp(A_{i-1})$ such that $A_i = (A_{i-1})_{\vecu_i,\vecv_i}$. If no such finite sequence exists then let $N(A)$ be infinite. Let $N(k,q_1,\dots,q_k) = \sup_{A\in\cfk}  \{N(A)\}$, and $\tilde{N}(Q) = \max_{k,q_1,\ldots,q_k | \sum_i q_i = Q} N(k,q_1,\ldots,q_k)$. Again, if $N(A) = \infty$ for some $A$ or if no finite upper bound exists, $\tilde{N}(Q)$ is defined to be $\infty$.

Note that if $\cD \in \Delta(\gd)$, so is every element in the sequence, so the polarization length bound below applies also to distributions. Our main lemma in this subsection is the following:

$\tilde{N}(Q)$ is finite for every finite $Q$. Specifically $\tilde{N}(Q) \leq (Q^2+3)\tilde{N}(Q-1)\, .$
Consequently for every $k,q_1,\ldots,q_k$, $N(q_1,\ldots,q_k)$ is finite as well.

We prove <ref> constructively in the following four steps.

Step 1: The algorithm Polarize.
Let us start with some notations. For $A\in\cF([q_1]\times\cdots\times[q_k])$ we let $A|_{x_\ell = q_\ell}$ denote the function $A$ restricted to the domain $[q_1]\times\cdots\times[q_{\ell-1}] \times \{q_\ell\} \times [q_{\ell+1}]\times\cdots\times[q_k]$. Note that $A|_{x_\ell = q_\ell}$ is effectively a $(k-1)$-dimensional function. We also define $A|_{x_\ell < q_\ell}$ as the restriction of $A$ to the domain $[q_1]\times\cdots\times[q_{\ell-1}] \times [q_\ell-1] \times [q_{\ell+1}]\times\cdots\times[q_k]$..

[1]
k=1 OR $\not\exists i: q_i\ge 2$
Output: $A$.
WLOG, let $q_k\ge2$.
$t \gets 0$; $Q^- \gets \sum_{i=1}^k (q_i-1) - 1$;  $Q^+ \gets \sum_{i=1}^{k-1}(q_i-1)$
$(A_0)|_{x_k < q_k} \gets $ Polarize$(A|_{x_k <q_k})$ ; $(A_0)|_{x_k = q_k} \gets $ Polarize$(A|_{x_k = q_k})$
Let $(1)^k = \veca_t(0) < \cdots < \veca_t(Q^-) = (q_1,\dots,q_{k-1},q_{k}-1)$ be a chain supporting $(A_t)|_{x_k <q_k}$.
Let $((1)^{k-1},q_k) = \vecb_t(0) < \cdots < \vecb_t(Q^+) = (q_1,\dots,q_{k})$ be a chain supporting $(A_t)|_{x_k = q_k}$.
$\exists (i,j)$ with $j < Q^+$ s.t. $\max\{\veca_t(i),\vecb_t(j)\} = (q_1,\dots,q_k)$ and $A_t(\veca_t(i)), A_t(\vecb_t(j))>0$
Let $(i_t,j_t)$ be the lexicographically smallest such pair $(i,j)$.
$B_t \gets (A_t)_{\veca_t(i_t),\vecb_t(j_t)}$.
$(A_{t+1})|_{x_k <q_k} \gets $ Polarize($B_t|_{x_k <q_k}$); $(A_{t+1})|_{x_k = q_k} \gets (B_t)|_{x_k = q_k}$.
$t\gets t+1$.
Let $(1)^k = \veca_t(0) < \cdots < \veca_t(Q^-) = (q_1,\dots,q_{k}-1)$ be a chain supporting $(A_t)|_{x_k <q_k}$.
Let $((1)^{k-1},q_k) = \vecb_t(0) < \cdots < \vecb_t(Q^+) = (q_1,\dots,q_{k})$ be a chain supporting $(A_t)|_{x_k = q_k}$.
Let $\ell \in [k]$ be such that for every $\veca \in [q_1]\times\cdots\times[q_k] \setminus \{(q_1,\dots,q_k)\}$ we have $A_t(\veca)>0 \Rightarrow a_\ell < q_\ell$.
$(A_{t+1})|_{x_\ell < q_\ell} \gets $Polarize$(A_t)|_{x_\ell < q_\ell}$;  $(A_{t+1})|_{x_\ell = q_\ell} \gets (A_{t})|_{x_\ell = q_\ell}$.
Output: $A_{t+1}$.

The goal of the rest of the proof is to show that <ref> terminates after a finite number of steps and outputs $A_{\vecmu(A)}$.

Step 2: Correctness assuming Polarize terminates.

[Correctness condition of Polarize]
For every $A\in\cF([q_1]\times\cdots\times[q_k])$, if $\textsc{Polarize}$ terminates, then $\textsc{Polarize}(A)=A_{\vecmu(A)}$. In particular, $\textsc{Polarize}(A)$ has the same marginals as $A$ and is supported on a chain.

First, by the definition of the polarization operator (<ref>), the marginals of $A_t$ are the same for every $t$. So in the rest of the proof, we focus on inductively showing that if Polarize terminates, then $\textsc{Polarize}(A)$ is supported on a chain.

The base case where $k=1$ is trivially supported on a chain as desired.

When $k>1$, note that when the algorithm enters the Clean-up stage, if we let $m$ and $n$ denote the largest indices such that $A_t(\veca_t(m)), A_t(\vecb_t(n)) > 0$ and $ A_t(\vecb_t(n))\neq (q_1,\dots,q_k)$, then the condition that $\max\{\veca_t(m), \vecb_t(n)\} \ne (q_1,\dots,q_k)$ implies that there is a coordinate $\ell$ such that $\veca_t(m)_\ell < q_\ell$ and $\vecb_t(n)_\ell < q_\ell$. Since every $\vecc$ such that $A_t(\vecc) > 0$ and $c_k < q_k$ satisfies $\vecc \leq \veca_t(m)$, we have $A_t(\vecc) > 0$ implies $c_\ell < q_\ell$. Similarly for every $\vecc\ne (q_1,\dots,q_k)$ such that $c_k = q_k$, we have $A_t(\vecc)>0$ implies $c_\ell < q_\ell$.
We conclude that $A_t$ is supported on $\{(q_1,\dots,q_k)\} \cup \{\vecc\, |\, c_\ell < q_\ell\}$.
Thus, by the induction hypothesis, after polarizing $(A_t)|_{x_\ell < q_\ell}$ and leaving $(A_t)|_{x_\ell = q_\ell}$ unchanged,

we get that the resulting function $A_{t+1}$ is supported on a chain as desired and complete the induction. We conclude that if Polarize terminates, we have $\textsc{Polarize}(A)=A_{\vecmu(A)}$.

Step 3: Invariant in Polarize.
Now, in the rest of the proof of <ref>, the goal is to show that for every input $A$, the number of iterations of the while loop in <ref> is finite.
The key claim (<ref>) here asserts that the sequence of pairs $(i_t,j_t)$ is monotonically increasing in lexicographic order. Once we establish this claim, it follows that there are at most $Q^-\cdot Q^+$ iterations of the while loop and so $\tilde{N}(Q) \leq (Q^2+3)\tilde{N}(Q-1)\, ,$ proving <ref>.
Before proving <ref>, we establish the following properties that remain invariant after every iteration of the while loop.