For every $t\ge0$, we have $(A_t)|_{x_k=q_k}$ and $(A_t)|_{x_k<q_k}$ are both supported on chains.

For $(A_t)|_{x_k<q_k}$, the claim follows from the correctness of the recursive call to Polarize. For $(A_t)|_{x_k=q_k}$, we claim by induction on $t$ that the supporting chain $\vecb_t(0) < \cdots < \vecb_t(Q^+)$ never changes (with $t$). To see this, note that $\vecb_t(k-1)=(q_1,\dots,a_k)$ is the only point in the support of $(A_t)|_{x_k=q_k}$ that increases in value, and this is already in the supporting chain. Thus $\vecb_t(0) < \cdots < \vecb_t(Q^+)$ continues to be a supporting chain for $(A_{t+1})|_{x_k=q_k}$.

For $\vecc \in [q_1]\times\cdots\times[q_k]$, we say that a function $A:[q_1]\times\cdots\times[q_k] \to \R^{\geq0}$ is $\vecc$-respecting if for every $\vecc'$ such that $A(\vecc') > 0$, we have $\vecc' \geq \vecc$ or $\vecc' \leq \vecc$. We say that $A$ is $\vecc$-downward-respecting if $A$ is $\vecc$-respecting and the points in the support of $A$ above $\vecc$ form a partial chain, specifically, if $\vecu,\vecv > \vecc$ have $A(\vecu),A(\vecv) > 0$, then either $\vecu \geq \vecv$ or $\vecv \geq \vecu$.

Note that if $A$ is supported on a chain then $A$ is $\vecc$-respecting for every point $\vecc$ in the chain. Conversely, if $A$ is supported on a chain and $A$ is $\vecc$-respecting, then $A$ is supported on a chain that includes $\vecc$.

Let $A$ be a $\vecc$-respecting function and let $\tilde{A}$ be obtained from $A$ by a finite sequence of polarization updates, as in <ref>.
Then $\tilde{A}$ is also $\vecc$-respecting. Furthermore if $A$ is $\vecc$-downward-respecting and $\vecw > \vecc$ then
$\tilde{A}$ is also $\vecc$-downward-respecting and $A(\vecw) = \tilde{A}(\vecw)$.

Note that it suffices to prove the claim for a single update by a polarization operator since the rest follows by induction. So let $\tilde{A} = A_{\vecu,\vecv}$ for incomparable $\vecu,\vecv\in \supp(A)$.
Since $A$ is $\vecc$-respecting, and $\vecu,\vecv$ are incomparable, either $\vecu \leq \vecc,\vecv \leq \vecc$ or $\vecu \geq \vecc, \vecv \geq \vecc$. Suppose the former is true, then $\max\{\vecu, \vecv \}\leq \vecc$ and
$\min\{\vecu,\vecv\} \leq \vecc$, and hence, $\tilde{A}$ is $\vecc$-respecting. Similarly, in the case when $\vecu \geq \vecc, \vecv \geq \vecc$, we can show that $\tilde{A}$ is $\vecc$-respecting.
The furthermore part follows by noticing that for $\vecu$ and $\vecv$ to be incomparable if $A$ is $\vecc$-downward-respecting and $A(\vecu),A(\vecv)>0$, then $\vecu,\vecv \leq \vecc$, and so the update changes $A$ only at points below $\vecc$.

The following claim asserts that in every iteration of the while loop, by the lexicographically minimal choice of $(i_t,j_t)$, there exists a coordinate $h\in[k-1]$ such that every vector $c<a_t(i_t)$ in the support of $A_t$, $B_t$, or $A_{t+1}$ has $c_h<q_h$, and every vector $c\neq (q_1,\dots,q_k)$ in the support of $(A_t)|_{x_k = q_k}$ has $c_h<q_h$.

For every $t\ge 0$, $\exists h \in [k-1]$ such that $\forall \vecc \in [q_1]\times\dots\times[q_k]$, if $\vecc\in \supp(A_t)\cup\supp(B_t)\cup\supp(A_{t+1})$, then the following hold:

* If $\vecc<\veca_t(i_t)$, then $c_h<q_h$.

* If $c_k=q_k$ and $\vecc\neq(q_1,\dots,q_k)$, then $c_h<q_h$.

Since $(i_t,j_t)$ is lexicographically the smallest incomparable pair in the support of $A_t$, for $i < i_t$, $j < Q^+$, and
$A_t(\veca(i)), A_t(\vecb(j)) > 0$, we have $\max\{\veca(i),\vecb(j)\} \ne (q_1,\dots,q_k)$. Let $m$ be the largest index smaller than $i_t$ such that
$A_t(\veca_t(m)) > 0$. Similarly, let $n < Q^+$ be the largest index such that $A_t(\vecb_t(n)) > 0$. Then the fact that $\max\{\veca_t(m), \vecb_t(n)\} \ne (q_1,\dots,q_k)$ implies that there exists $h\in[k-1]$ such that $\veca_t(m)_h < q_h$ and $\vecb_t(n)_h < q_h$. Now, using the fact (from <ref>) that $(A_t)|_{x_k<q_k}$ is supported on a chain, we conclude that for every $\vecc < \veca_t(i_t)$, $A_t(\vecc)> 0$ implies that $\vecc \leq \veca_t(m)$ and hence, $c_h<q_h$. Similarly, for every vector $\vecc \ne (q_1,\dots,q_k)$ in the support of $(A_t)|_{x_k = q_k}$, by the maximality of $n$, we have $c_h < q_h$.

We now assert that the same holds for $B_t$. First, recall that $\supp(B_t)\subset\supp(A_t)\cup\{(q_1,\dots,q_k),\min\{\veca_t(i_t),\vecb_t(j_t)\}\}$ since $B_t=(A_t)_{\veca_t(i_t),\vecb_t(j_t)}$.
Next, note that the only point (other than $(q_1,\dots,q_k)$) where $B_t$ is larger than $A_t$ is
$\min\{\veca_t(i_t),\vecb_t(j_t)\}$. It suffices to show that $\min\{\veca_t(i_t),\vecb_t(j_t)\}_h < q_h $. We have $\min\{\veca_t(i_t),\vecb_t(j_t)\} \leq \vecb_t(j_t) \leq \vecb_t(n)$ and hence $\min\{\veca_t(i_t),\vecb_t(j_t)\}_h < q_h$.

Finally, we assert that same holds also for $A_{t+1}$. Since $A_{t+1}|_{x_k=q_k} = B_t|_{x_k=q_k}$, the second item in the claim follows trivially. To prove the first item, let us consider $\veca' \in [q_1]\times\cdots\times[q_k]$ defined as follows: $\veca'_h = q_h-1$ and $\veca'_{r} = \veca_t(i_t)_{r}$ for $r \ne h$. Note that $B_t|_{x_k <q_k}$ is $\veca_t(i_t)$-respecting since potentially the only new point in its support (compared to $A_t|_{x_k < q_k}$) is $\min\{\veca_t(i_t),\vecb_t(j_t)\} \leq \veca_t(i_t)$. From the previous paragraph we also have that if $B_t(\vecc) > 0$ and $\vecc < \veca_t(i_t)$, then $c_h < q_h$ and hence, $\vecc \leq \veca'$. On the other hand, if $B_t(\vecc) > 0$ and $\vecc \ge \veca_t(i_t)$, then $\vecc\ge a'$. Therefore, $B_t|_{x_k<q_k}$ is $\veca'$-respecting. By applying <ref>, we conclude that $(A_{t+1})|_{x_k<q_k}$ is also $\veca'$-respecting. It follows that if $\vecc < \veca(i_t)$ and $A_{t+1}(\vecc) > 0$, then $\vecc \leq \veca'$ and so $c_h < q_h$.

Step 4: Proof of <ref>.

The following claim establishes that the while loop in the $\textsc{Polarize}$ algorithm terminates after a finite number of iterations.

For every $t\ge 0$, $(i_t,j_t)<(i_{t+1},j_{t+1})$ in lexicographic ordering.

Consider the chain $\veca_{t+1}(0) < \cdots < \veca_{t+1}(Q^-)$ supporting $A_{t+1}|_{x_k < q_k}$. Note that for  $i \geq i_t$, $A_{t+1}|_{x_k < q_k}$ is $\veca_t(i)$-respecting (since $A_t|_{x_k<q_k}$ and $B_{t}|_{x_k<q_k}$ were also so).  In particular, $A_t|_{x_k<q_k}$ is $\veca_t(i)$-respecting because it is supported on a chain containing $a_t(i)$. Next $B_t|_{x_k<q_k}$ is $\veca_t(i)$-respecting since potentially the only new point in its support is $\min\{\veca_t(i_t),\vecb_t(j_t)\} \leq \veca_t(i)$. Finally, $A_{t+1}|_{x_k <q_k}$ is also $\veca_t(i)$-respecting using <ref>. Thus we can build a chain containing  $\veca_t(i)$ that supports $A_{t+1}|_{x_k<q_k}$. It follows that we can use $\veca_{t+1}(i) = \veca_t(i)$ for $i \geq i_t$. Now consider $i < i_t$. We must have $\veca_{t+1}(i) < \veca_{t+1}(i_t) = \veca_t(i_t)$.
By <ref>, there exists $h\in [k-1]$ such that for $i < i_t$, $\veca_{t+1}(i)_h < q_h$.

We now turn to analyzing $(i_{t+1},j_{t+1})$. Note that by definition, $A_{t+1}(\veca_{t+1}(i_{t+1}))>0$ and
$A_{t+1}(\vecb_{t+1}(b_{t+1}))>0$. First, let us show that $i_t \le i_{t+1}$. On the contrary, let us assume that $i_{t+1} < i_t$. It follows from the above paragraph that $\veca_{t+1}(i_{t+1})_h < q_h$. Also, for every $\vecb_{t+1}(j)$ with $j <Q^+$ and $A_{t+1}(\vecb_{t+1}(j))>0$, we have $\vecb_{t+1}(j)_h < q_h$. Therefore, $\max\{\veca(i_{t+1}),\vecb(j_{t+1})\} \ne (q_1,\dots,q_k)$ (in particular $\max\{\veca(i_{t+1}),\vecb(j_{t+1})\}_h<q_h$), which is a contradiction.

Next, we show that if $i_{t+1} = i_t$, then $j_{t+1}\ge j_t$. By the minimality of $(i_t,j_t)$ in the $t$-th round, for $j<j_t$ such that $A_t(b_t(j))>0$, we have $\max\{a_{t}(i_{t}),b_t(j)\} \ne (q_1,\dots,q_k)$. Since  $i_{t+1} = i_t$, $a_{t+1}(i_{t+1})=a_{t+1}(i_{t})=a_{t}(i_{t})$. We already noted in the proof of <ref> that $\vecb_t(0) < \cdots < \vecb_t(Q^+)$ is also a supporting chain for $(A_{t+1})|_{x_k=q_k}$. The only point where the function $A_{t+1}|_{x_k=q_k}$ has greater value than $A_t|_{x_k=q_k}$ is $(q_1,\dots,q_k)$. Therefore, for $j<j_t$ such that $A_{t+1}(b_{t+1}(j))>0$, we have $\max\{a_{t+1}(i_{t+1}), b_{t+1}(j)\} \ne (q_1,\dots,q_k)$ and hence, $j_{t+1}\ge j_t$.

So far, we have established that $(i_{t+1},j_{t+1})\ge (i_t,j_t)$ in lexicographic ordering. Finally, we will show that $(i_{t+1},j_{t+1}) \neq (i_t,j_t)$ by proving that at least one of $A_{t+1}(\veca_{t+1}(i_{t}))$ and $A_{t+1}(\vecb_{t+1}(j_t))$ is zero. The polarization update ensures that at least one of $B_{t}(\veca_{t}(i_{t}))$ and $B_{t}(\vecb_t(j_t))$ is zero. If $B_t(\vecb_t(j_t)) = 0$, then by definition, we have $A_{t+1}(\vecb_{t+1}(j_t)) = A_{t+1}(\vecb_t(j_t)) = 0$. Finally to handle the case $B_{t}(\veca_{t}(i_{t}))=0$, let us again define $\veca'$ as: $\veca'_h = q_h-1$ and $\veca'_{r} = \veca_t(i_t)_{r}$ for $r \ne h$, where $h$ is as given by <ref>. We assert that $B_t|_{x_k<q_k}$ is $\veca'$-downward-respecting. As shown in the proof of <ref>, we have $B_t|_{x_k<q_k}$ is $\veca'$-respecting. The support of $B_t|_{x_k<q_k}$ is contained in $\{\veca_t(0),\cdots,\veca_t(Q^-)\} \cup \{\min\{\veca_t(i_t),\vecb_t(j_t)\}\}$ and $\min\{\veca_t(i_t),\vecb_t(j_t)\} < \veca_t(i_t)$, and by <ref>, $\min\{\veca_t(i_t),\vecb_t(j_t)\}\leq \veca'$. It follows that $B_t|_{x_k<q_k}$ is $\veca'$-downward-respecting. Finally, by the furthermore part of <ref> applied to $B_{t}|_{x_k<q_k}$ and $\vecw = \veca_t(i_t)$, we get that $A_{t+1}(\veca_{t+1}(i_{t}))=A_{t+1}(\veca_t(i_t)) = B_{t}(\veca_t(i_t)) = 0$. It follows that $(i_{t+1},j_{t+1}) \ne (i_t,j_t)$.

By <ref>, we know that if <ref> terminates, we have $\textsc{Polarize}(A)=A_{\vecmu(A)}$. Hence, the maximum number of polarization updates used in Polarize (on input from $\cF([q_1]\times\cdots\times[q_k])$) serves as an upper bound for $\tilde{N}(Q)$, for $Q=\sum_{i=1}^k q_k$.
By <ref>, we know that there are at most $Q^2$ iterations of the while loop and so $\tilde{N}(Q) \leq (Q^2+3)\tilde{N}(Q-1)$ as desired.

§.§ Reduction from single function to a family of functions

In this subsection, we prove the following lemma that reduces an SD problem for a single function to an SD problem for a family of functions.

Suppose there exists $\cF,\cD_Y,\cD_N$, $\delta > 0$ with $\vecmu(\cD_Y) = \vecmu(\cD_N)$ and a $c=c(n)$-communication protocol achieving advantage $\delta$ solving $(\cF,\cD_Y,\cD_N)$-SD on instances of length $n$ for every $n \geq n_0$. Then
there exist $\cD_1,\cD_2\in\Delta([q]^k)$ with $\vecmu(\cD_1) = \vecmu(\cD_2)$, $\delta' > 0$, $n'_0$,  and a $c$-communication protocol achieving advantage $\delta'$ solving $(\cD_1,\cD_2)$-SD on instances of length $n\geq n'_0$ using $O(s)$ bits of communication.

We prove the lemma by a hybrid argument, where we slowly change the distribution $\cD_Y$ to $\cD_N$ by considering one function from $\cF$ at a time. The crux of the lemma is in showing that two adjacent steps in this sequence are at least as hard as some single-function SD problem, which follows from the following lemma.

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$. Let $\cF \subseteq\{f:[q]^k\to\{0,1\}\}$ For every $\epsilon,\delta\in(0,1]$, there exist $n'=\Omega(n)$ and constants $\alpha',\delta'\in(0,1)$ such that the following holds. For every distributions $\cD_Y,\cD_N,\cD_0,\cD_1,\cD_2\in\Delta(\cF\times[q]^k)$ such that $\cD_Y=(1-\epsilon)\cD_0+\epsilon\cD_1$ and $\cD_N=(1-\epsilon)\cD_0+\epsilon\cD_2$ and for every $c\in\N$, suppose there exists a protocol for $(\cF,\cD_Y,\cD_N)$- with parameters $n$ and $\alpha$ using $c$ bits of communication with advantage $\delta$, then there exists a protocol for $(\cF,\cD_1,\cD_2)$- with parameters $n'$ and $\alpha'$ using $c$ bits of communication with advantage $\delta'$.

The proof idea of <ref> is very similar to that of <ref>. We defer the proof to <ref> and turn to showing how <ref> follows.

Let $\ALG(\vecx^*; M,\vecz)$ be the $c$-bit protocol for $(\cF,\cD_Y,\cD_N)$-SD achieving advantage $\delta$ guaranteed to exist by the theorem statement. Let $\cF=\{f_1,\ldots,f_\ell\}$. Since $\vecmu(\cD_Y) = \vecmu(\cD_N)$ for each $i\in[m]$, we have that $\Pr[f=f_i\colon (f,\vecb)\sim\cD_Y]=\Pr[f=f_i\colon (f,\vecb)\sim\cD_N]$. Let us denote this probability by $w^{(i)}$, $w^{(i)}=\Pr[f=f_i\colon (f,\vecb)\sim\cD_Y]=\Pr[f=f_i\colon (f,\vecb)\sim\cD_N]$ for each $i\in[\ell]$.
For each $i\in[\ell]$, let $\cD_Y^{(i)}$ be the distribution of a random variable $\vecb\in[q]^k$ that is sampled from $(f,\vecb)\sim\cD_Y$ conditioned on $f=f_i$. Similarly, for each $i\in[\ell]$, let $\cD_N^{(i)}$ be the distribution of $\vecb\in[q]^k$ from $(f,\vecb)\sim\cD_N$ conditioned on $f=f_i$. This way we have that $\cD_Y$ and $\cD_N$ are the mixture distributions:
$\cD_Y=\sum_{i\in[\ell]} w^{(i)}\cdot \cD_Y^{(i)}$ and $\cD_N=\sum_{i\in[\ell]} w^{(i)}\cdot \cD_N^{(i)}$.

For every $i\in\{0,\ldots,\ell\}$, we define a distribution $\cD^{(i)}$ as the following mixture distribution:

\[
\cD^{(i)}=\sum_{j\in\{1,\ldots,i\}} w^{(j)}\cdot \cD_N^{(j)}+
\sum_{j\in\{i+1,\ldots,\ell\}} w^{(j)}\cdot \cD_Y^{(j)} \,.
\]

Let $p_i=\Pr[\ALG(\vecx^*; M,\vecz)=\yes\colon (f,\vecb)\sim\cD^{(i)}]$ for every $i\in\{0,\ldots,\ell\}$. Observe that $p_0=\Pr[\ALG(\vecx^*; M,\vecz)=\yes\colon (f,\vecb)\sim\cD_Y]$ and $p_\ell=\Pr[\ALG(\vecx^*; M,\vecz)=\yes\colon (f,\vecb)\sim\cD_N]$. Since the advantage of $\ALG$ in distinguishing $\cD_Y$ and $\cD_N$ is at least $\delta$, we have that

\[
\delta= \left|p_0-p_\ell\right|=\left|\sum_{i\in\{0,\ldots,\ell-1\}}(p_i-p_{i+1})\right| \leq \sum_{i\in\{0,\ldots,\ell-1\}}\left|p_i-p_{i+1}\right|\,.
\]

Let $\delta'=\delta/\ell$. We have that at least one term of this sum is $\left|p_i-p_{i+1}\right|\geq \delta'$. From this we conclude that for some $i\in\{0,\ldots,\ell-1\}$, $\ALG$ achieves advantage at least $\delta'$ for $(\cF,\cD^{(i)},\cD^{(i+1)})$-SD.

It remains to show that if one can distinguish $\cD^{(i)}$ and $\cD^{(i+1)}$ that differ only for $(f,\vecb)$ with $f=f_{i+1}$, then one can also distinguish $\cD_1=\cD_Y^{(i+1)}$ and $\cD_2=\cD_N^{(i+1)}$. Since $\vecmu(\cD_1) = \vecmu(\cD_2)$, this will finish the proof. We show that $\cD_1$ and $\cD_2$ are distinguishable using <ref>.

Let us define $\eps=w_{i+1}$, $\cD=\frac{1}{1-\eps}\left(\sum_{j\in\{1,\ldots,i\}} w^{(j)}\cdot \cD_N^{(j)}+
\sum_{j\in\{i+2,\ldots,\ell\}} w^{(j)}\cdot \cD_Y^{(j)}\right)$. Now observe that
$\cD^{(i)}=(1-\epsilon)\cD+\epsilon\cD_1$ and
$\cD^{(i+1)}=(1-\epsilon)\cD+\epsilon\cD_2$. Now by <ref>, a protocol that distinguishes $\cD^{(i)}$ and $\cD^{(i+1)}$ implies a protocol for $(\cD_1, \cD_2)$-SD with advantage $\delta''>0$ and communication complexity $O(s)$.

§.§ Putting it together

We now have the ingredients in place to prove <ref> which we recall below for convenience.

Fix $\cF \subseteq \{f:[q]^k \to \{0,1\}\}$ and distributions $\cD_Y,\cD_N \in \Delta(\cF\times[q]^k)$ with $\vecmu = \vecmu(\cD_Y) = \vecmu(\cD_N)$. <ref>, applied to $(\cF, \cD_Y,\cD_N)$, gives us $n_0,\delta'$, and distributions
$\cD_Y',\cD_N' \in \Delta([q]^k)$ with $\vecmu'=\vecmu(\cD_Y') = \vecmu(\cD_N')$ such that any $c$-communication protocol for $(\cF,\cD_Y,\cD_N)$- with advantage $\delta$ implies a $c$-communication protocol for $(\cD_Y',\cD_N')$- with advantage $\delta'$ for all $n\geq n_0$. Now we'll focus on proving a lower bounds for the problem $(\cD_Y',\cD_N')$-.

<ref>, applied to $\cD_Y'$, gives us $\cD_0 = \cD_Y',\cD_1,\ldots,\cD_t = \cD_{\vecmu'}$ such that $\cD_{i+1} = (\cD_i)_{\vecu(i),\vecv(i)}$, i.e., $\cD_i$ is an update of $\cD_i$, with $t \leq \tilde{N}(Q) < \infty$, for $Q=\sum_{i=1}^k q_k$.
Similarly <ref>, applied to $\cD_N'$, gives us $\cD'_0 = \cD_N',\cD'_1,\ldots,\cD'_{t'} = \cD_{\vecmu'}$ such that $\cD'_{i+1} = (\cD'_i)_{\vecu'(i),\vecv'(i)}$ with $t' \leq \tilde{N}(Q) < \infty$.

Applying <ref> with $\delta'' = \delta'/(2\tilde{N}(Q))$ to the pairs $\cD_i$ and $\cD_{i+1}$, we get that there exists $\tau_i$ such that every protocol for
$(\cD_i,\cD_{i+1})$- requires $\tau_i \sqrt{n}$ bits of communication to achieve advantage $\delta''$.
Similarly applying <ref> again with $\delta'' = \delta'/(2\tilde{N}(Q))$ to the pairs $\cD'_i$ and $\cD'_{i+1}$, we get that there exists $\tau'_i$ such that every protocol for
$(\cD'_i,\cD'_{i+1})$- requires $\tau'_i \sqrt{n}$ bits of communication to achieve advantage $\delta''$.

Letting $\tau' = \min\left\{\min_{i \in [t]}\{\tau_i\}, \min_{i \in [t']}\{\tau'_i\}\right\}$, we get, using the triangle inequality for indistinguishability, that every protocol $\Pi'$ for $(\cD_Y',\cD_N')$- achieving advantage $(t+t')\delta''\leq\delta'$ requires $\tau'\sqrt{n}$ bits of communication. Finally, by <ref>, every protocol $\Pi$ for $(\cF,\cD_Y,\cD_N)$- achieving advantage $\delta$ requires $\tau'\sqrt{n}$ bits of communication.

§ INDISTINGUISHABILITY OF THE POLARIZATION STEP

Recall that in <ref> we define a polarization operator that polarizes a distribution $\cD\in\Delta([q]^k)$ to $\cD_{\vecu,\vecv}\in\Delta([q]^k)$ for every incomparable pair $(\vecu,\vecv)$. In this section, we show that $(\cD,\cD_{\vecu,\vecv})$-SD requires $\Omega(\sqrt{n})$ communication.

Let $\vecu\vee\vecv,\vecu\wedge\vecv \in [q]^k$ be given by $u_i\vee v_i = \max\{u_i,v_i\}$ and $u_i\wedge v_i = \min\{u_i,v_i\}$.
Let $\cA_Y = \unif(\{\vecu,\vecv\})$ and $\cA_N = \unif(\{\vecu\vee\vecv,\vecu\wedge\vecv\})$. We prove <ref> in two steps. First, we use the Boolean hardness in <ref> to show in <ref> that the hardness holds for the special case $(\cA_Y,\cA_N)$-SD. =0
Next, we use a similar reduction as in the proof for Lemma 7.7 in [8] to reduce $(\cA_Y,\cA_N)$-advice-SD to $(\cD,\cD_{\vecu,\vecv})$-SD for arbitrary distribution $\cD\in\Delta([q]^k)$.=1
Next, we reduce $(\cA_Y,\cA_N)$-advice-SD to $(\cD,\cD_{\vecu,\vecv})$-SD for arbitrary distribution $\cD\in\Delta([q]^k)$.

§.§ Reduce a Boolean SD problem to a non-Boolean SD problem

In this subsection, we consider a special case of $\vecu,\vecv\in[q]^k$ where $u_i\neq v_i$ for every $i\in[k]$. The following key lemma of this subsection establishes the hardness of $(\cA_Y,\cA_N)$-SD via a reduction from a Boolean SD problem to a non-Boolean version.

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 $\vecu,\vecv \in [q]^k$ satisfying $u_i \ne v_i$ for all $i \in [k]$ and $\delta>0$, there exists $\tau>0$ such that every protocol for $(\cA_Y,\cA_N)$-SD  achieving advantage $\delta$ requires $\tau\sqrt{n}$ bits of communication.

We prove <ref> by a reduction. For such $\vecu,\vecv$, let $\bar{\vecu},\bar{\vecv} \in \{0,1\}^k$ be the Boolean version given by $(\bar{u}_i,\bar{v}_i) = (0,1)$ if $u_i < v_i$ and $(\bar{u}_i,\bar{v}_i) = (1,0)$ if $u_i > v_i$. Let $\bar{\cA}_Y = \unif(\{\bar{\vecu},\bar{\vecv}\})$ and $\bar{\cA}_N = \unif(\{\bar{\vecu}\vee\bar{\vecv},\bar{\vecu}\wedge\bar{\vecv}\})$. Note that both $\bar{\cA}_Y$ and $\bar{\cA}_N$ are distributions on Boolean domain with uniform marginals. Thus, <ref> shows that any protocol for $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD requires $\Omega(\sqrt{n})$ bits of communication. In the rest of this subsection, we reduce $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD to $(\cA_Y,\cA_N)$-SD.

For every $\bar{n},k,\bar{\alpha},q,\delta$, let $n=2q\bar{n}$ and $\alpha=q^{k-1}2^{-(k+2)}\bar{\alpha}$.
Let $\bar{I} = (\bar{\vecx},\bar{\Gamma},\bar{\vecb},\bar{M},\bar{\vecz},\bar{\veca})$ denote an instance of $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD of length $\bar{n}$ with parameter $\bar{\alpha}$.
We show below how Alice and Bob can use their inputs and shared randomness to generate an instance
$I = (\vecx,\Gamma,\vecb,M,\vecz,\veca)$  of $(\cA_Y,\cA_N)$-advice-SD of length $n$ with parameter $\alpha$ “locally” and “nearly” according to the correct distributions. Namely, we show that with high probability if $\bar{I}$ is a Yes (resp. No) instance of $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD, then $I$ will be a Yes (resp. No) instance of $(\cA_Y,\cA_N)$-SD.

Step 1: Specify the shared randomness.
The common randomness between Alice and Bob is an instances $I_R = (\vecx_R,\Gamma_R,\vecb_R,M_R,\vecz_R,\veca_R)$ drawn according to the Yes[The reduction also works if we used No distribution. However, the mapping between Yes and No instances would get flipped. Namely, if $\bar{I}$ is a Yes (resp. No) instance of $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD, then $I$ will be a No (resp. Yes) instance of $(\cA_Y,\cA_N)$-SD.] distribution of $(\cA_Y,\cA_N)$-advice-SD of length $n$ with parameter $\alpha$. For $j \in [\alpha n]$, let $V_j$ denote the set of variables in the $j$-th constraint, i.e., $V_j = \{\ell \in [n]\, |\,  \Gamma_R(\ell) \in \{ k(j-1)+1,\ldots,k(j-1)+k\}\}$. For $i \in [k]$, let $T_i$ be the set of variables that are in the $i$-th partition and take on values in $\{u_i,v_i\}$, i.e.,
$T_i = \{j \in [n]\, |\, a_j = i\, \&\, (\vecx_R)_i \in \{u_i,v_i\}\}$. Let $U \subseteq [\alpha n]$ be the set of constraints that work on variables in $T_i$, i.e., $U = \{j \in [\alpha n]\, |\, V_j \subseteq \cup_i T_i \}$. See <ref> for an example.

An example of shared randomness used in <ref>. Here $n=12$, $k=2$, $q=3$, and $\alpha=1/3$. The value of $\vecx_R\in[q]^n$ is listed in a table. Consider $(u_1,v_1)=(1,3)$ and $(u_2,v_2)=(3,2)$. The variables in sets $T_1,T_2$ are marked grey. The variables correspond to the set $U$ are circled with red lines and the variables correspond to sets $S_1,S_2$ are circled with yellow dashed lines.

If $|U| \geq \bar{\alpha}\bar{n}$ we say an error of type (1) has occurred. For $i \in [k]$, let $X_i\subseteq T_i$ be the set of variables that operate on constraints in $U$, i.e., $X_i = T_i \cap (\cup_{j \in U} V_j)$. Let $W_i \subseteq T_i$ be a set of variables that do not participate in any constraint, i.e., $W_i = T_i \setminus (\cup_{j \in [\alpha n]} V_j)$. Finally let $S_i$ be any set satisfying $|S_i| = \bar{n}/k$ with $X_i \subseteq S_i \subseteq X_i \cup W_i$ if such a set exists. If no such set exists we say an error of type (2) has occurred.

Step 2: Specify the reduction.
If there is an error, we simply set $I=I_R$. If no errors have occurred, our reduction will embed $\bar{I}$ into $I_R$ by replacing the constraints in $U$ and the variables in $\cup_i S_i$ as described next. Note that we have to specify variables $(\vecx,\Gamma,\vecb,M,\vecz)$. In particular, we want the private inputs can be computed locally. We verify the local property of the reduction in <ref> and prove the correctness of the reduction in <ref>.

* $\vecx$: Let $\rho:[\bar{n}] \to \cup_i S_i$ be a bijection satisfying $\bar{a}_j = i \Rightarrow \rho(j) \in S_i$. We now define $\vecx \in [q]^n$ as follows:

\[
x_j = \left \{ \begin{array}{ll}
(\vecx_R)_j & \mbox{ if $j \notin \cup_{i \in [k]}S_i$ } \\
u_i & j \in S_i \mbox{ for some } i \in [k] \mbox{ and } u_i < v_i \mbox{ and } \bar{x}_j = 0 \\
u_i & j \in S_i \mbox{ for some } i \in [k] \mbox{ and } u_i > v_i \mbox{ and } \bar{x}_j = 1 \\
v_i & j \in S_i \mbox{ otherwise }
\end{array} \right .
\]

* $\Gamma$ and $M$: Let $V = \{V(1),\ldots,V(\bar{n})\}$ with $V(j) < V(j+1)$ be such that $V = \{j \in [n] | \Gamma_R(j) \in \cup_{i \in [k]} S_i\}$. For $j \in [n]$ we let

\[
\Gamma(j) =  \left \{ \begin{array}{ll}
\Gamma_R(j) & \mbox{ if $j \notin V$}\\
\rho(\bar{\Gamma}(\bar{j})) & \mbox{ if $j = V(\bar{j})$} \\
\end{array} \right .
\]

It may be verified that $\Gamma$ is a permutation and furthermore the constraints in $\Gamma$ corresponding to $j \in U$ are derived from constraints of $\bar{I}$. $M$ is then defined as the partial permutation matrix capturing $\Gamma^{-1}(j)$ for $j\in[k\alpha n]$.

* $\vecb$: Since $\vecb$ is a hidden variable and won't be given to Alice and Bob, we postpone the specification of $\vecb$ to the proof of <ref>.

* $\vecz$: Let $\vecz(j)=\bar{\vecz}(V(j))$ if $j\in U$ and $\vecz(j)=\vecz_R(j)$ otherwise.

Step 3: Correctness of the reduction assuming no error occurs.
[The reduction can be computed locally]
Let $\bar{I} = (\bar{\vecx},\bar{\Gamma},\bar{\vecb},\bar{M},\bar{\vecz},\bar{\veca})$ be an instance of $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD and $I_R = (\vecx_R,\Gamma_R,\vecb_R,M_R,\vecz_R,\veca_R)$ be the shared randomness of Alice and Bob. The above reduction satisfies the following local properties:

* Alice can compute $\vecx$ using $I_R$ and $(\bar{\vecx},\bar{\veca})$.

* Bob can compute $(M,\vecz)$ using $I_R$ and $(\bar{M},\bar{\vecz},\bar{\veca})$.

* Note that from the construction, it suffices to have $\{S_i\}$, $\bar{\veca}$, $\bar{\vecx}$ to compute $\vecx$. Since $\{S_i\}$ can be obtained from $I_R$, we conclude that Alice can compute $\vecx$ using $I_R$ and $(\bar{\vecx},\bar{\veca})$.

* Note that from the construction, it suffices to have $\{S_i\}$, $\Gamma_R$, $\bar{\Gamma}(j)$ where $j\in[k\alpha n]$ to compute $M$. Since $\bar{\Gamma}(j)$ is encoded in $\bar{M}$ for every $j\leq k\alpha n$, and the other information can be obtained from $I_R$, we know that $M$ can be computed from $I_R$ and $\bar{M}$.
Finally, since $\vecz=\vecz'$, $\vecz$ can also be computed from $I_R$. We conclude that Bob can compute $(M,\vecz)$ using $I_R$ and $(\bar{M},\bar{\vecz},\bar{\veca})$.

[The distribution of $I$]
Let $\bar{I} = (\bar{\vecx},\bar{\Gamma},\bar{\vecb},\bar{M},\bar{\vecz},\bar{\veca})$ be an instance drawn from either the Yes or No distribution of $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD and $I_R = (\vecx_R,\Gamma_R,\vecb_R,M_R,\vecz_R,\veca_R)$ be a instance drawn from the Yes distribution of $(\cA_Y,\cA_N)$-advice-SD. Let $I = (\vecx,\Gamma,\vecb,M,\vecz,\veca)$ be the result of applying the above reduction on $\bar{I}$ and $I_R$. Then the following hold.

* $\vecx\sim\unif([q]^n)$.

* $M$ is a uniformly random partial permutation matrix as required in the item 3 of <ref>.

* Suppose there is no error happening in the reduction.

* If $\bar{I}$ is a Yes instance, then $\Pr[\vecz(j)=1]=\Pr_{\vecb(j)\sim\cA}[(M\vecx)(j)=\vecb(j)]$ for every $j\in[\alpha n]$.

* If $\bar{I}$ is a No instance, then $\Pr[\vecz(j)=1]=\Pr_{\vecb(j)\sim\cA'}[(M\vecx)(j)=\vecb(j)]$ for every $j\in[\alpha n]$.

Namely, if $\bar{I}$ is a Yes (resp. No) instance of $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD, then $I$ is a Yes (resp. No) instance of $(\cA_Y,\cA_N)$-SD.

* To prove $\vecx\sim\unif([q]^n)$, observe that $\vecx$ is obtained from $\vecx_R$ by flipping some of the $u_i$ to $v_i$ (and vice versa). In particular, (i) $\vecx_R\sim\unif([q]^n)$ and (ii) the flipping is decided by $\bar{\vecx}$, which is uniformly sampled from $\{0,1\}^{\bar{n}}$ and is independent to $\vecx_R$. Note that for a fixed $\vecx_R$, $S_i$, and $j\in S_i$, the probability of $x_j$ being set to $u_i$ is the same as being set to $v_i$. As a result, by symmetry of $u_i$ and $v_i$, we conclude that $\vecx\sim\unif([q]^n)$.

* By the symmetry of the $n$ variables, $M$ is a uniformly random partial permutation matrix as required in the item 3 of <ref>.

* Suppose there is no error happening in the reduction. We consider the following two cases: (i) $j\in[\alpha n]\backslash U$ and (ii) $j\in U$.

* For each $j\in[\alpha n]\backslash U$, by the construction we have $\vecz(j)=\vecz_R(j)$ and hence when fixing $\vecx_R,M_R$, we have $\Pr[\vecz(j)=1]=\Pr[\vecz_R(j)=1]=\Pr_{\vecb_R(j)\sim\cA}[(M_R\vecx_R)(j)=\vecb_R(j)]$. We set $\vecb(j) = \vecb_R(j)$ and note that $\vecb(j)\sim\cA_Y$ (resp. $\vecb(j)\sim\cA_N$) if $\bar{\vecb}(j)\sim\bar{\cA}_Y$ (resp. $\bar{\vecb}(j)\sim\bar{\cA}_N$) for every $j\in U$. Finally, since $j\notin U$, there exists $i\in[k]$ such that $(M_R\vecx_R(j))_i=(M\vecx(j))_i\notin\{u_i,v_i\}$ and hence $\Pr_{\vecb_R(j)\sim\cA_Y}[(M_R\vecx_R)(j)=\vecb_R(j)]=\Pr[(M\vecx)(j)=\vecb(j)]=0$. So we have $\Pr[\vecz(j)=1]=\Pr_{\vecb(j)\sim\cA_Y}[(M\vecx)(j)=\vecb(j)]$ (resp. $\Pr[\vecz(j)=1]=\Pr_{\vecb(j)\sim\cA_N}[(M\vecx)(j)=\vecb(j)]$) if $\bar{I}$ is a Yes (resp. No) instance as desired.

* For each $j\in U$, by construction we have $\vecz(j)=\bar{\vecz}(V(j))$. We set

\[
\vecb(j)_i =  \left \{ \begin{array}{ll}
u_i &  \mbox{ if $u_i < v_i$ and } \bar{\vecb}(V(j))_i = 0 \\
u_i &  \mbox{ if $u_i > v_i$ and } \bar{\vecb}(V(j))_i = 1 \\
v_i &  \mbox{ otherwise.}
\end{array} \right .
\]

First, observe that $\vecz(j)=1$ iff $(M\vecx)(j)=\vecb(j)$. To see this, note that

\begin{align*}
\vecz(j)=1 &\Leftrightarrow \bar{\vecz}(V(j))=1\\
&\Leftrightarrow (\bar{M}\bar{\vecx})(V(j))=\bar{\vecb}(V(j)) \, .
\intertext{For each $i\in[k]$, if $u_i<v_i$ and $\bar{\vecb}(V(j))_i=(\bar{M}\bar{\vecx})(V(j))_i=0$, we have $\vecb(j)_i=(M\vecx)(j)_i=u_i$. Similarly, for all the other situations we have $\vecb(j)_i=(M\vecx)(j)$ and hence the equation becomes}
&\Leftrightarrow (M\vecx)(j)=\vecb(j)
\end{align*}

as desired.

Next, observe that if $\bar{I}$ is a Yes (resp. No) instance, then $\vecb(j)\sim\cA_Y$ (resp. $\vecb(j)\sim\cA_N$). We analyze the two cases as follows.

* If $\bar{I}$ is a Yes instance, we have $\bar{\vecb}(V(j))\sim\bar{\cA}_Y=\unif(\{\bar{\vecu},\bar{\vecv}\})$. Recall that $(\bar{u}_i,\bar{v}_i)=(0,1)$ if $u_i<v_i$ and $(\bar{u}_i,\bar{v}_i)=(1,0)$ otherwise. Now observe that, by the above choice of $\vecb(j)$, we have $\bar{\vecb}(V(j))=\bar{\vecu}$ iff $\vecb(j)=\vecu$ (resp. $\bar{\vecb}(V(j))=\bar{\vecv}$ iff $\vecb(j)=\vecv$). Thus, we have $\vecb(j)\sim\cA_Y$ as desired.

* If $\bar{I}$ is a No instance, we have $\bar{\vecb}(V(j))\sim\bar{\cA}_N=\unif(\{\bar{\vecu}\vee\bar{\vecv},\bar{\vecu}\wedge\bar{\vecv}\})$. Recall that for each $i\in[k]$, $u_i\vee v_i=\max\{u_i,v_i\}$ and $u_i\wedge v_i=\min\{u_i,v_i\}$. Now observe that, by the above choice of $\vecb(j)$, we have $\bar{\vecb}(V(j))=\bar{\vecu}\vee\bar{\vecv}$ iff $\vecb(j)=\vecu\vee\vecv$ (resp. $\bar{\vecb}(V(j))=\bar{\vecu}\wedge\bar{\vecv}$ iff $\vecb(j)=\vecu\wedge\vecv$). Thus, we have $\vecb(j)\sim\cA_N$ as desired.

To sum up, for each $j\in U$, we have $\Pr[\vecz(j)=1]=\Pr_{\vecb(j)\sim\cA_Y}[(M\vecx)(j)=\vecb(j)]$ (resp. $\Pr[\vecz(j)=1]=\Pr_{\vecb(j)\sim\cA_N}[(M\vecx)(j)=\vecb(j)]$) if $\bar{I}$ is a Yes (resp. No) instance as desired.

Step 4: An error occurs with low probability.

When $n$ is sufficiently large, the probability of an error happening in the reduction is at most $2^{-\Omega((2/q)^{2k}\alpha n)}$.

Recall that for given $\bar{n},k,\bar{\alpha},q,\delta$, we let $n=2q\bar{n}$ and $\alpha=q^{k-1}2^{-(k+2)}\bar{\alpha}$.

Note that $U$ is a sum of $\alpha n$ i.i.d. $\textsf{Bern}((2/q)^k)$. So by concentration inequality, we have $\Pr[|U|>2(2/q)^k\alpha n]<2^{-\Omega((2/q)^{2k}\alpha n)}$. By the choice of parameters, we have $2(2/q)^k\alpha n\leq\bar{\alpha}\bar{n}$. Thus, type (1) error happens with probability at most $2^{-\Omega((2/q)^{2k}\alpha n)}$.

Note that by the choice of parameters, we have $|X_i|=|U|\leq\bar{n}/k$ and hence type (2) error happens only when $|U|+|W_i|<\bar{n}/k$ for some $i\in[k]$. For each $i\in[k]$, note that $|W_i|$ is a sum of $n/k-\alpha n$ i.i.d. $\textsf{Bern}(2/q)$. So by concentration inequality, we have $\Pr[|W_i|<(n/k-\alpha n)/q]<2^{-\Omega((1/q)^2(n/k-\alpha n))}$. By the choice of parameters, we have $(n/k-\alpha n)/q\geq\bar{n}/k$. Thus, type (2) error happens with probability at most $2^{-\Omega((1/q)^2(n/k-\alpha n))}\leq2^{-\Omega((2/q)^{2k}\alpha n)}$.

Step 5: Proof of <ref>.

For every $\bar{n},k,\bar{\alpha},q,\delta$, we let $n=2q\bar{n}$ and $\alpha=q^{k-1}2^{-(k+2)}\bar{\alpha}$.
Suppose there is a protocol for $(\cA_Y,\cA_N)$-SD using $C(n)$ bits of communication and achieving advantage $\delta$. We show that how to get a protocol $\bar{\Pi}$ for $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD with parameters $(\bar{n},\bar{\alpha})$ using $C(n)$ bits of communication and achieving advantage $\delta/2$.

Let $\bar{I} = (\bar{\vecx},\bar{\Gamma},\bar{\vecb},\bar{M},\bar{\vecz},\bar{\veca})$ be an instance drawn from either the Yes or No distribution of $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD where $(\bar{\vecx},\bar{\veca})$ is Alice's private input and $(\bar{M},\bar{\vecz},\bar{\veca})$ is Bob's private input. The protocol $\bar{\Pi}$ works as follows. Alice and Bob first use their private input and the shared randomness to compute $\vecx$ and $(M,\vecz)$ respectively. This can be done due to <ref>. Next, Alice and Bob simply invoke the protocol $\Pi$ on the new instance $\vecx$ and $(M,\vecz)$ and output the result accordingly.

It is immediate to see that $\bar{\Pi}$ only uses $C(n)$ bits of communication. To show that $\bar{\Pi}$ has advantage at least $\delta/2$, we first show that the joint distribution of $(\vecx,M,\vecz)$ is the same as that from an instance of $(\cA_Y,\cA_N)$-SD if there is no error in the reduction.
By <ref>, $\vecx\sim\unif([q]^n)$ and $M$ follows the distribution as required in the item 3 of <ref>.

When there is no error in the reduction and $\bar{I}$ is sampled from the Yes (resp. No) distribution of $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD, <ref> implies that $\vecz$ follows the conditional distribution (conditioned on $\vecx$ and $M$) of a Yes (resp. No) instance of $(\cA_Y,\cA_N)$-SD as required in the item 5 of <ref>. Next, <ref> shows that the probability of an error happening in the reduction is at most $\delta/2$. Finally, by triangle inequality, we conclude that $\bar{\Pi}$ has advantage at least $\delta/2$ in solving $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD.

To conclude, by <ref>, any protocol for $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD with advantage $\delta/2$ requires $\bar{\tau}\sqrt{\bar{n}}$ bits of communication. Thus, we have $C(n)\geq\bar{\tau}\sqrt{\bar{n}}\geq\tau\sqrt{n}$ for some constant $\tau>0$.

§.§ Indistinguishability of shifting distributions

In this subsection, we prove the following lemma which was used in <ref> for reducing a single-function SD to a multi-function SD, and will be used in <ref> for reductions between various  problems.

Given the parameters $n,\alpha$ and $\epsilon\in(0,1)$, define $n'=\epsilon n$ and $\alpha'=2\alpha$.

Let $(\vecx',M',\vecb',\vecz')$ be an instance of the $(\cF,\cD_1,\cD_2)$- problem where $\vecx'\in[q]^{n'}$, $M'\in\{0,1\}^{k\alpha'n'\times n'}$, $\vecb'\in[q]^{k\alpha'n'}$, $\vecz'\in\{0,1\}^{\alpha'n'}$. Let $R'$ be the shared randomness defined later. We specify the map
$(\vecx',M',\vecb',\vecz',R')\mapsto(\vecx,M,\vecb,\vecz)$ where $\vecx\in[q]^{n}$, $M\in\{0,1\}^{k\alpha n\times n}$, $\vecb\in[q]^{k\alpha n}$, $\vecz\in\{0,1\}^{\alpha n}$.

A reduction from $(\cF,\cD_1,\cD_2)$- to $(\cF,\cD_Y,\cD_N)$-SD
Let $\vecy \sim \textsf{Unif}([q]^{n-n'})$, $\vecw \sim \bern(2\eps)^{\alpha n}$. Let $\Gamma \in \{0,1\}^{n\times n}$ be a uniform permutation matrix. Let $\vecc = (\vecc(1),\ldots,\vecc((n-n')/k))$ where $\vecc(i) \sim \cD$ are chosen independently.

* Let $R' = (\vecy,\vecw,\Gamma,\vecc)$ be the shared randomness.

Let $\#_w(i) = |\{j \in [i]\, |\, w_j = 1\}|$ denote the number $1$'s among the first $i$ coordinates of $\vecw$.
If $\#_w(\alpha n) \geq \alpha' n'$ or if $\alpha n - \#_w(\alpha n) \geq (n-n')/k$ we declare an error, Note $\Exp[\#_w(n)] = \alpha'n'/2$ so the probability of error is negligible (specifically it is $\exp(-n)$).

Given $(\vecx',M',\vecb',\vecz',R')$, we now define $(\vecx,M,\vecb,\vecz)$ as follows.

* Let $\vecx = \Gamma (\vecx',\vecy)$ so $\vecx$ is a random permutation of the concatenation of $\vecx'$ and $\vecy$.

* Let $M' = (M'_1,\ldots,M'_{\alpha'n'})$ where $M'_i \in \{0,1\}^{k \times n'}$. We extend $M'_i$ to $N_i \in \{0,1\}^{k \times n}$ by adding all-zero columns to the right. For $i \in \{1,\ldots,(n-n')/k\}$, let $P_i \in \{0,1\}^{k \times n}$ be given by $(P_i)_{j\ell} =1$ if and only if $\ell = n' +(i-1)k + j$. Next we define a matrix $\tilde{M} \in \{0,1\}^{k\alpha n \times n} = (\tilde{M}_1,\ldots,\tilde{M}_{\alpha n})$ where $\tilde{M}_i \in \{0,1\}^{k \times n}$ is defined as follows: If $w_i = 1$ then we let $\tilde{M}_i = N_{\#_w(i)}$ else we let $\tilde{M}_i = P_{i - \#_w(i)}$. Finally we let $M = \tilde{M} \cdot \Gamma^{-1}$.

* Let $\vecb = (\vecb(1),\ldots,\vecb(\alpha n))$ where $\vecb(i)= \vecb'(\#_w(i))$ if $w_i = 1$, otherwise $\vecb(i)= \vecc(i-\#_w(i))$.

* Let $z_i=1$ if and only if $M_i\vecx=\vecb(i)$ for every $i\in[\alpha n]$.

Now, we verify that the reduction satisfies the following success conditions.

Success conditions for the reduction

* The reduction is locally well-defined. Namely, there exist random strings $R'$ so that (i) Alice can get $\vecx$ through a map $(\vecx',R') \mapsto \vecx$ while Bob can get $(M,\vecz)$ through a map $(M',\vecz',R') \mapsto (M,\vecz)$.

* The reduction is sound and complete. Namely, (i) $z_i=1$ if and only if $M_i\vecx = \vecb(i)$ for all $i\in[\alpha n]$. (ii) If $\vecb' \sim \cD_1^{\alpha'n'}$, then $\vecb \sim \cD_Y^{\alpha n}$. Similarly if $\vecb' \sim \cD_2^{\alpha'n'}$, then $\vecb \sim \cD_N^{\alpha n}$. (iii) $\vecx\sim \unif([q]^{n})$ and $M$ is a uniformly random matrix conditioned on having exactly one “$1$” per row and at most one “$1$” per column.

If $\#_w(\alpha n) \leq \alpha' n'$ and  $\alpha n - \#_w(\alpha n) \leq (n-n')/k$, then the second map in the reduction is locally well-defined, sound, and complete. In particular, the error event happens with probability at most $\exp(-\Omega(n))$ over the randomness of $R'$.

To see the reduction is locally well-defined, first note that Alice can compute $\vecx=\Gamma(\vecx',\vecy)$ from $\vecx'$ and the shared randomness $R'$ locally. As for Bob, note that the maximum index needed for $N$ and $\vecb'$ (resp. $P$ and $\vecc$) is at most $\#_w(\alpha n)$ (resp. $\alpha n-\#_w(i)$). Namely, if $\#_w(\alpha n) \leq \alpha' n'$ and $\alpha n - \#_w(\alpha n) \leq (n-n')/k$, then $M$ and $\vecb$ are well-defined. Note that this happens with probability at least $1-2^{-\Omega(n)}$. Also, one can verify from the construction that $M$ and $\vecb$ can be locally computed by $M'$, $\vecb'$, and the shared randomness $R'$.

To see the reduction is sound and complete, (i) $z_i=1$ if and only if $M_i\vecx=\vecb(i)$ for every $i\in[\alpha n]$ directly follows from the construction. As for (ii), if $\vecb'\sim\cD_1^{\alpha'n'}$. Now, for each $i\in[\alpha n]$, $\vecb(i)=\vecb'(\#_w(i))$ with probability $\epsilon$ and $\vecb(i)=\vecc(i-\#_w(i))$ with probability $1-\epsilon$. As $\vecb'(i')\sim\cD_1$ for every $i'\in[\alpha'n']$ and $\vecc(i')\sim\cD_0$ for every $i'\in[(n-n')/k]$, we have $\vecb(i)\sim(1-\epsilon)\cD_0+\epsilon\cD_1=\cD_Y$ as desired. Similarly, one can show that if $\vecb'\sim\cD_2^{\alpha'n'}$, then for every $i'\in[\alpha'n']$ we have $\vecb(i')\sim\cD_N$. Finally, we have $\vecx\sim\unif([q]^n)$ and $M$ is a uniformly random matrix with exactly one “$1$” per row and at most one “$1$” per column (due to the application of a random permutation $\Gamma$) by construction.

This completes the proof of the success conditions (1)-(2) for the reduction.

To wrap up the proof of <ref>, suppose there is a protocol $\Pi$ for $(\cF,\cD_Y,\cD_N)$- with parameters $n$ and $\alpha$ using $c$ bits of communication with advantage $\delta$. We describe a protocol $\Pi'$ for $(\cF,\cD_1,\cD_2)$- with parameters $n'$ and $\alpha'$ using $c$ bits of communication with advantage at least $\delta-2^{-\Omega(n)}$.

Let $(\vecx',M',\vecb',\vecz')$ be an instance of the $(\cF,\cD_1,\cD_2)$- problem where $\vecx'\in[q]^{n'}$, $M'\in\{0,1\}^{k\alpha'n'\times n'}$, $\vecb'\in[q]^{k\alpha'n'}$, $\vecz'\in\{0,1\}^{\alpha'n'}$. Let $R'$ be the shared randomness defined above. In the new protocol $\Pi'$, Alice and Bob computes their private inputs $\vecx$ and $(M,\vecz)$ respectively. By <ref>, the computation can be done locally with their original private inputs and the shared randomness. Also, with probability at least $1-2^{-\Omega(n)}$, the Yes (resp. No) instance of $(\cF,\cD_1,\cD_2)$- is mapped to the Yes (resp. No) instance of $(\cF,\cD_Y,\cD_N)$-. Namely, by directly applying $\Pi$ on the new inputs, Alice and Bob can achieve $\delta-2^{-\Omega(n)}$ advantage on $(\cF,\cD_1,\cD_2)$ using the same amount of communication as desired.

§.§ Proof of Theorem <ref>

Let $\vecu,\vecv$ be incomparable, let $S=\{i\in[k]\, |\, u_i\neq v_i \}$, and let $k''=|S|$.

Step 1: Specify the auxiliary distributions.

* Let $\cA_Y=\unif(\{\vecu|_S,\vecv|_S\})$ and $\cA_N=\unif(\{(\vecu|_S)\vee(\vecv|_S),(\vecu|_S)\wedge(\vecv|_S)\})$. By <ref>, $(\cA_Y,\cA_N)$- requires $\tau\sqrt{n}$ space.

* Let $\cD_1=\unif(\{\vecu,\vecv\})$ and $\cD_2=\unif(\{\vecu\vee\vecv,\vecu\wedge\vecv\})$.

* Finally, there exists $\cD_0$ such that we have $\cD=(1-2\epsilon)\cD_0+2\epsilon\cD_1$ and $\cD_{\vecu,\vecv}=(1-2\epsilon)\cD_0+2\epsilon\cD_2$.

In the following, we are going to describe reduction from $(\cA_Y,\cA_N)$- with parameters $(n'',\alpha'',k'')$ to $(\cD_1,\cD_2)$- with parameters $(n',\alpha',k)$. And by <ref>, there exists a reduction from $(\cD_1,\cD_2)$- with parameters $(n',\alpha',k)$ to $(\cD,\cD_{\vecu,\vecv})$- with parameters $(n,\alpha,k)$.

Step 2: Overview of the reduction from $(\cA_Y,\cA_N)$- to $(\cD,\cD_{\vecu,\vecv})$-.
Let $\Pi$ be a protocol for $(\cD,\cD_{\vecu,\vecv})$- with parameter $\alpha\leq1/(200k)$ using $C(n)$ communication bits to achieve advantage $\delta$ on instances of length $n$. We let $n''=(k''\epsilon/k)n$, $\alpha''=(2k/k'')\alpha$ and design a protocol $\Pi''$ for $(\cA_Y,\cA_N)$- with parameter $\alpha''$ achieving advantage at least $\delta/2$ on instances of length $n''$ using $C''(n'')=C(n)$ communication.
Thus, by <ref>, there exists a constant $\tau''>0$ such that $C(n)=C''(n'')\geq\tau''\sqrt{n''}=\tau''\sqrt{(k''\epsilon/k)}\sqrt{n}$ as desired.

To construct such reduction, we first reduce the above instance of $(\cA_Y,\cA_N)$- to an instance of $(\cD_1,\cD_2)$- with parameters $n'=kn''/k''$ and $\alpha'=\alpha''n''/n'$. Next, we invoke <ref> to get a protocol $\Pi'$ (from $\Pi$) which achieves $\delta-2^{-\Omega(n)}$ advantage on $(\cD_1,\cD_2)$- using $C(n)$ communication.

Without loss of generality, we assume $\Pi'$ is deterministic and our new protocol $\Pi''$ for $(\cA_Y,\cA_N)$- uses shared randomness between Alice and Bob. The protocol $\Pi''$ consists a map: $(\vecx'',M'',\vecb'',\vecz'',R'')\mapsto(\vecx',M',\vecb',\vecz')$.

Before describing the map, let us first state the desired conditions.

Success conditions for the reduction

* The reduction is locally well-defined. Namely, there exist a random string $R''$ so that (i) Alice can get $\vecx'$ through the maps $(\vecx'',R'') \mapsto \vecx'$ while Bob can get $(M',\vecz')$ through the map $(M'',\vecz'',R'') \mapsto (M',\vecz')$.

* The reduction is sound and complete. Namely, (i) $z'_{i}=1$ if and only if $M'_{i}\vecx' = \vecb'(i)$ for all $i\in[\alpha'n']$. (ii) If $\vecb'' \sim \cA_Y^{\alpha''n''}$ then $\vecb' \sim \cD_1^{\alpha'n'}$. Similarly if $\vecb'' \sim \cA_N^{\alpha''n''}$ then $\vecb' \sim \cD_2^{\alpha'n'}$. (iii) $\vecx'\sim \unif([q]^{n'})$ and $M'$ is a uniformly random matrix conditioned on having exactly one “$1$” per row and at most one “$1$” per column.

Step 3: Specify and analyze the reduction from $(\cA_Y,\cA_N)$- to $(\cD_1,\cD_2)$-.
We now specify the first map mentioned above and prove that it satisfies conditions (1)-(2).

A reduction from $(\cA_Y,\cA_N)$- to $(\cD_1,\cD_2)$-

* Let $R'' \sim \unif([q]^{n'-n''})$ be the shared randomness.

Given $(\vecx'',M'',\vecb'',\vecz'',R'')$ we define $(\vecx',M',\vecb',\vecz')$ as follows. To get $M'$, $\vecz'$ and $\vecb'$ we need some more notations. First, note that $\alpha''n''=\alpha'n'$ due to the choice of parameters.

* Let $\vecx' = (\vecx'',R'')$.

* $M'$ can be viewed as the stacking of matrices $M''_1,\ldots,M''_{\alpha'' n''} \in \{0,1\}^{k'' \times n''}$. We first extend $M''_i$ by adding all-zero columns at the end to get $N'_i \in \{0,1\}^{k'' \times n'}$. We then stack $N'_i$ on top of $P'_i \in \{0,1\}^{(k-k'')\times n'}$ to get $M'_i$, where $(P'_i)_{j\ell} = 1$ if and only if $\ell = n'' + (i-1)k + j$. We let $M'$ be the stacking of $M'_1,\ldots,M'_{\alpha' n'}$.

* Let $\vecb'' = (\vecb''(1),\cdots,\vecb''(\alpha' n'))$. Let $\tilde{\vecu} = (u_{k''+1},\ldots,u_{k})$ denote the common parts of $\vecu$ and $\vecv$. We let
$\vecb'(i) = (\vecb''(i),\tilde{\vecu})$ and $\vecb' = (\vecb'(1),\cdots,\vecb'(\alpha' n'))$.

* Let $z'_i=1$ if and only if $M'_i\vecx' = \vecb'(i)$ for all $i\in[\alpha'n']$ as required.

The above reduction is locally well-defined, sound, and complete.

To see the map is locally well-defined, note that Alice can compute $\vecx'= (\vecx'',R'')$ locally. Similarly, Bob can compute $M'$ locally by construction. As for $\vecz'$, note that for every $i\in[\alpha'n']$, $z'_i=1$ if and only if $z''_i=1$ and $P_i'\vecx'=\tilde{\vecu}$. Since Bob has $\vecz'$ and can locally compute $P_i'\vecx'$ for every $i$, her can also compute $\vecz'$ locally.

To see the map is sound and complete, (i) $z'_i=1$ if and only if $M'_i\vecx'=\vecb'(i)$ follows from the construction. As for (ii), for each $i\in[\alpha'n']=[\alpha''n'']$, if $\vecb''_i\sim\cA_Y=\unif(\{\vecu|_S,\vecv|_S\})$, then $\vecb'_i\sim\unif(\{(\vecu|_S,\tilde{\vecu}),(\vecv|_S,\tilde{\vecu})\})=\unif(\{\vecu,\vecv\})=\cD_1$ as desired. Similarly, one can show that if $\vecb''_i\sim\cA_N$, then $\vecb'_i\sim\cD_1$. Finally, we have $\vecx'\sim\unif([q]^{n'})$ by construction and hence (iii) holds.

This completes the proof of conditions (1)-(2) for the reduction.

Step 4: Proof of <ref>.

Let us start with setting up the parameters. Given $k\in(0,1/(200k)),\alpha,n,\cD$, and incomparable pair $(\vecu,\vecv)\in\supp(\cD)$ and polarization amount $\epsilon=\epsilon(\cD,\vecu,\vecv)$, let $k''=|\{i\in[k]\, |\, u_i\neq v_i\}|$, $n''=(k''\eps/k)n$, $\alpha''=(2k/k'')\alpha$, $n'=kn''/k''$, $\alpha'=\alpha''n'/n'$, and $\delta''=\delta/2$.

Now, for the sake of contradiction, we assume that there exists a protocol $\Pi=(\Pi_A,\Pi_B)$ for $(\cD,\cD_{\vecu,\vecv})$- with advantage $\delta$ and at most $\tau\sqrt{n}$ bits of communication.

First, by <ref>, if $(\vecx'',M'',\vecz'')$ is a Yes (resp. No) instance of $(\cA_Y,\cA_N)$-, then the output of the reduction, i.e., $(\vecx',M',\vecz')$, is a Yes (resp. No) instance of $(\cD_1,\cD_2)$-. Next, Alice and Bob run the protocol $\Pi'$ from <ref> on $(\vecx',M',\vecz')$. By the correctness of the reduction as well as the protocol $\Pi'$, we know that Alice and Bob have advantage at least $\delta-\exp(-\Omega(n))\geq\delta/2=\delta''$ in solving $(\cA_Y,\cA_N)$- with at most $\tau\sqrt{n}=\tau\sqrt{(k/(k''\epsilon))n''}$ bits of communication.

Finally, by <ref>, we know that there exists a constant $\tau_0>0$ such that any protocol for $(\cA_Y,\cA_N)$- with advantage $\delta''$ requires at least $\tau_0\sqrt{n''}$ bits of communication. This implies that $\tau\geq\tau_0\sqrt{k''\epsilon/k}$. We conclude that any protocol for $(\cD,\cD_{\vecu,\vecv})$- with advantage $\delta$ requires at least $\tau\sqrt{n}$ bits of communication.

§.§ Old writeup

In this section we show the hardness of SD for some very specific distributions.
Just a temporary section that needs to find the right place in the paper

Recalling definition below for my convenience. It differs from previous section somewhat - but hopefully just in symbols being used.
I've synced these two definitions. I think we can remove this one now, and use <ref> instead.

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.

* 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^* = \widetilde{\vecb}(i)$, and $z_i = 0$ otherwise.

* Define a function $\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.

For positive integers $q$ and $k$ and vectors $\vecu, \vecv \in [q]^k$, we define the following notations for this section.
Let $\vecu\vee\vecv,\vecu\wedge\vecv \in [q]^k$ be given by $u'_i = \max\{u_i,v_i\}$ and $v'_i = \min\{u_i,v_i\}$.
Let $\cA = \unif(\{\vecu,\vecv\})$ and $\cA' = \unif(\{\vecu\vee\vecv,\vecu\wedge\vecv\})$.

Our main theorem for this section is the following:
Theorem statement needs to be fixed. Say Polarization works. Remove advice.

For every $q,k$ and vectors $\vecu,\vecv \in [q]^k$ and $\delta > 0$ there exists $\tau> 0$ such that every algorithm for $(\cA_Y,\cA_N)$-(advice-)SD achieving advantage $\delta$ requires space $\tau \sqrt{n}$ on instances of length $n$.

We prove the theorem by reducing some Boolean SD problems to the problem above, and then appealing to <ref>. The first of our lemmas considers the case of $\vecu,\vecv$ such that $u_i \ne v_i$ for every $i$. For such $\vecu,\vecv$ let $\bar{\vecu},\bar{\vecv} \in \{0,1\}^k$ be given by $(\bar{u}_i,\bar{v}_i) = (0,1)$ if $u_i < v_i$ and $(\bar{u}_i,\bar{v}_i) = (1,0)$ if $u_i > v_i$.
Let $\bar{\cA} = \unif(\{\bar{\vecu},\bar{\vecv}\})$ and $\bar{\cA'} = \unif(\{\bar{\vecu\vee\vecv},\bar{\vecu\wedge\vecv}\})$. Note that both $\bar{\cA}$ and $\bar{\cA'}$ are distributions on Boolean domain with uniform marginals. Our first lemma gives a reduction from the Boolean SD problem to the non-Boolean version.

For every $k,q, \vecu,\vecv \in [q]^k$ satisfying $u_i \ne v_i$ for every $i \in [k]$ the following holds: If there exists a space $s(n)$ algorithm for $(\cA_Y,\cA_N)$-advice-SD achieving advantage $\delta$ then there exists a $???$ space algorithm for $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD achieving advantage $\delta/2$.

We prove the lemma by giving a reduction. Let $\Pi$ be a $s(n)$-space protocol for $(\cA_Y,\cA_N)$-advice-SD. We show how to get
a protocol $\bar{\Pi}$ for $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD from $\Pi$.

Let $\bar{n}$ be a multiple of $k$ and let $\bar{I} = (\bar{x},\bar{\Gamma},\bar{\vecb},\bar{M},\bar{\vecz},\bar{\veca})$ denote an instance of $(\bar{\cA}_Y,\bar{\cA}_N)$-advice-SD of length $\bar{n}$ with parameter $\bar{\alpha}$.
We show below how to generate an instance
$I = (x,\Gamma,\vecb,M,\vecz,\veca)$  of $(\cA_Y,\cA_N)$-advice-SD of length $n$ with parameter $\alpha$ “locally” and “nearly” according to the correct distributions for $n = (2q)\bar{n}$ and $\alpha = q^{k-1}2^{-(k+2)}\bar{\alpha}$.

The common randomness between Alice and Bob is an instances $I_R = (\vecx_R,\Gamma_R,\vecb_R,M_R,\vecz_R,\veca_R)$ drawn according to the distribution $\cD_\cA^n$. Define $\cD_\cA^n$? For the sake of analysis we also draw $\vecb'$ according to $(\cA')^{\alpha n}$ and let  $I'_R = (\vecx_R,\Gamma_R,\vecb'_R,M_R,\vecz'_R,\veca_R)$.
For $j \in [\alpha n]$, let $V_j$ denote the set of variables in the $j$th constraint, i.e., $V_j = \{\ell \in [n] |  \Gamma_R(\ell) \in \{ k(j-1)+1,\ldots,k(j-1)+k\}\}$. For $i \in [k]$, let $T_i$ be the set of variables that are in the $i$th partition and take on values in $\{u_i,v_i\}$, i.e.,
$T_i = \{j \in [n] | a_j = i \& (\vecx_R)_i \in \{u_i,v_i\}\}$. Let $U \subseteq [\alpha n]$ be the set of constraints that work on variables in $T_i$, i.e., $U = \{j \in [\alpha n] | V_j \subseteq \cup_i T_i \}$. If $|U| \geq \bar{\alpha}\bar{n}$ we say an error of type (1) has occurred. For $i \in [k]$, let $X_i\subseteq T_i$ be the set of variables that operate on constraints in $U$, i.e., $X_i = T_i \cap (\cup_{j \in U} V_j)$. Let $W_i \subseteq T_i$ be a set of variables that do not participate in any constraint, i.e., $W_i = T_i \setminus (\cup_{j \in [\alpha n]} V_j)$. Finally let $S_i$ be any set satisfying $|S_i| = \bar{n}/k$ with $X_i \subseteq S_i \subseteq X_i \cup W_i$ if such a set exists. If no such set exists we say an error of type (2) has occurred.

Assuming no errors have occurred, our reduction will embed $\bar{I}$ into $I_R$ by replacing the constraints in $U$ and the variables in $\cup_i S_i$ as described next. Let $\rho:[\bar{n}] \to \cup_i S_i$ be a bijection satisfying $\bar{a}_j = i \Rightarrow \rho(j) \in S_i$. We now define $\vecx \in [q]^n$ as follows:

\[
x_j = \left \{ \begin{array}{ll}
(\vecx_R)_j & \mbox{ if $j \notin \cup_{i \in [k] S_i}$ } \\
u_i & j \in S_i \mbox{ for some } i \in [k] \mbox{ and } u_i < v_i \mbox{ and } \bar{x}_j = 0 \\
u_i & j \in S_i \mbox{ for some } i \in [k] \mbox{ and } u_i > v_i \mbox{ and } \bar{x}_j = 1 \\
v_i & j \in S_i \mbox{ otherwise }
\end{array} \right .
\]

The above completes the embedding of $\bar{\vecx}$ into $\vecx$. We now turn to embedding the constraints (which involves two part - choosing the locations via $\Gamma$ and choosing the actual constraints via $\vecb$). Let $V = \{V(1),\ldots,V(\bar{n})\}$ with $V(j) < V(j+1)$ be such that $V = \{j \in [n] | \Gamma_R(j) \in \cup_{i \in [k]} S_i\}$. For $j \in [n]$ we let

\[
\Gamma(j) =  \left \{ \begin{array}{ll}
\Gamma_R(j) & \mbox{ if $j \notin V$}\\
\rho(\bar{\Gamma}(\bar{j})) & \mbox{ if $j = V(\bar{j})$} \\
\end{array} \right .
\]

It may be verified that $\Gamma$ is a permutation and furthermore the constraints in $\Gamma$ corresponding to $j \in U$ are derived from constraints of $\bar{I}$.
Next we turn to defining $\vecb = (\vecb(1),\ldots,\vecb(\alpha n))$. If $j \in [\alpha n] \setminus U$ then we use a constraint from $I_R$ by setting $\vecb(j) = \vecb_R(j)$. To determine $\vecb(j)$ for $j \in U$ we denote $U = \{U(1),\ldots,U(u)\}$ with $U(i) < U(i+1)$. Then $j = U(\bar{j})$ for some $\bar{j} \in [u]$ and we set $\vecb(j) = \vecu$ based on  $\bar{\vecb}(\bar{j})$ as follows, for $i \in [k]$:

\[
\vecb(j)_i =  \left \{ \begin{array}{ll}
u_i &  \mbox{ if $u_i < v_i$ and } \bar{\vecb}(j)_i = 0 \\
u_i &  \mbox{ if $u_i > v_i$ and } \bar{\vecb}(j)_i = 1 \\
v_i &  \mbox{ otherwise }
\end{array} \right .
\]

For the purpose of analysis we also define $\vecb'$ as $\vecb'(j) = \vecb(j)$ if $j \in U$ and $\vecb'_R(j)$ otherwise. The above now completely determines an instance $I = (\vecx,\Gamma,\vecb,M,\vecz,\veca)$ of length $n$ with parameter $\alpha$, when there is no error. For the sake of analysis we also let $I = I_R$ if there is an error, and define $I' = (\vecx,\Gamma,\vecb',M,\vecz',\veca)$ if ther is no error and $I' = I'_R$ if there is an error. We now analyze the properties of this transformation.

Details above should be correct though may need elaboration. Details below omitted but should be easily fillable.

(1) We claim that if there is no error then $\vecz = \vecz'$ and Alice and Bob can locally generate their inputs according to $I$ (and hence $I'$ since it has the same input).

(2) We claim that if $\bar{I} \sim \cD_{\bar{\cA}}^{\bar {n}}$ then $I \sim \cD_{\cA}^n$. Similarly if $\bar{I} \sim \cD_{\bar{\cA'}}^{\bar{n}}$ then $I' \sim \cD_{\cA'}^n$. We also need $I\sim \cD_{\cA'}^n$ when $\bar{I} \sim \cD_{\bar{\cA'}}^{\bar{n}}$ right?

(3) Finally we argue that if $n = (2q)\bar{n}$ and $\alpha = q^{k-1}2^{-(k+2)}\bar{\alpha}$ then the probability of error of either type is at most $\delta/2$. Note that $\E[|U|] = (2/q)^k \alpha n$. This allows to assert that by applying the local transformation, the resulting protocol $\Pi$ achieves an advantage of at least $\delta/2$. To bound the error probabilities we note that an error of type (1) or (2) occurs only if $|U| > \bar{\alpha}\bar{n}$ or if there exists $i \in [k]$ such that $|W_i| \leq \bar{n}/k$. The expected size of $U$ is $(2/q)^k \alpha n \leq 1/2 \bar{\alpha}\bar{n}$ (using $\alpha = q^{k-1}2^{-(k+2)}\bar{\alpha}$ and $n = (2q)\bar{n}$) so the first event happens with exponentially small probability in $n$ (and so less that $\delta/4$ for sufficiently large $n$). Similarly the expected size of $W_i$ is at least $(2/q)(1-\alpha)n/k \geq 2 \bar{n}/k$ using $\bar{n} = n/(2q)$ (and $\alpha \leq 1/2$). Again for sufficiently large $n$ we can make this probability smaller than $\delta/(4k)$ for any given $i$ and by taking the union bound over all the error events we get that the error probability is at most $\delta/2$.

The above handles the case where $u_i \ne v_i$ for all $i$.
We now show how to extend the hardness to settings where $u_i = v_i$ for some $i$.
To this end, given $\vecu,\vecv \in [q]^k$, let $S = \{i \in [k] | u_i \ne v_i\}$, let $\widetilde{k} = |S|$ and
let $\widetilde{\vecu}, \widetilde{\vecv} \in [q]^{\widetilde{k}}$ be the projections of $\vecu$ and $\vecv$ to coordinates of $S$. Let $\widetilde{\vecu\vee\vecv},\widetilde{\vecu\wedge\vecv}$ denote the coordinatewise maximum and minimum of $\widetilde{\vecu}$ and $\widetilde{\vecv}$, and let $\widetilde{\cA}$ and $\widetilde{\cA'}$ denote the uniform distribution on these pairs. In the following lemma we assert that distinguishing
$\cA$ from $\cA'$ is as hard as distinguishing $\widetilde{\cA}$ and $\widetilde{\cA'}$. In fact we prove something more general (keeping in mind our future use. We also allow convex combinations with a fixed distribution $\cA_0$.

For every $k,q, \vecu,\vecv \in [q]^k$, $\cA_0 \in \Delta([q]^k)$ and $\lambda \in [0,1]$ the following holds: If there exists a space $s(n)$ algorithm for $((1-\lambda)\cA_0 + \lambda\cA,(1-\lambda)\cA_0 + \lambda \cA')$-advice-SD achieving advantage $\delta$ then there exists a $???$ space algorithm for $(\widetilde{\cA},\widetilde{\cA'})$-advice-SD achieving advantage $\delta/4$.

We should be able to extract this proof from Section 7 of previous paper.

Complete proof of <ref>

§ DICHOTOMY FOR EXACT COMPUTATION

In this section we prove <ref>. For this, we will use tight bounds on the randomized communication complexity of the Disjointness () and Gap Hamming Distance () problems.

In the $\Disj_{n}$ problem, Alice and Bob receive binary strings $x,y\in\{0,1\}^n$ of Hamming weight $\Delta(x)=\Delta(y)=n/4$, respectively. If the Hamming distance $\Delta(x,y)=n/2$ the players must output $1$, if $\Delta(x,y)< n/2$ they must output $0$.

In the $\GHD_{n,t,g}$ problem, Alice and Bob receive binary strings $x,y\in\{0,1\}^n$, respectively. If the Hamming distance $\Delta(x,y)\geq t+g$ the players must output $1$, if $\Delta(x,y)\leq t-g$ they must output $0$, otherwise they may output either $0$ and $1$.

The following results give tight bounds on the randomized communication complexity of $\Disj$ and $\GHD$.

For all large enough $n$, any randomized protocol solving $\Disj_n$ with probability $2/3$ must use $\Omega(n)$ bits of communication.

For every $a\in(0,1/2]$ and every $g\geq 1$, and all large enough $n$ the following holds. If $t\in[an, (1-a)n]$, then any randomized protocol solving $\GHD_{n,t,g}$ with probability $2/3$ must use $\Omega(\min\{n, n^2/g^2\})$ bits of communication.

Equipped with these results, we are ready to prove <ref>.

While this theorem doesn't give tight bounds on the space complexity of $\maxF$ in terms of $n$, the dependence on $\eps$ is tight. For every family of functions $\cF$, if we sample $O(n/\eps^2)$ random constraints, then by the Chernoff bound we preserve the values of all assignments within a factor of $1\pm\eps$.

For the first item of the theorem, we note that the maximum number of simultaneously satisfiable constraints in a $\sigma$-satisfiable formula is the number of non-zero constraints $f \in \cF\setminus\{\veczero\}$ in it. This can be computed in space $O(\log{n})$.

Now we turn to the proof of the second item of the theorem in the streaming setting.
To this end, first we prove that there exists an unsatisfiable instance $I$ of $\textsf{Max-CSP}(\cF\setminus\{\veczero\})$. Let $I$ be an instance on $kq$ variables that has every constraint from $\cF\setminus\{\veczero\}$ applied to every (unordered) $k$-tuple of distinct variables. Any assignment $\vecnu\in[q]^{kq}$ has at least $k$ equal coordinates. That is, there exists $\sigma\in[q]$ such that $\Sigma=\{i\colon \vecnu_i=\sigma\}$ has size $|\Sigma|\geq k$. Since $\cF$ is not $\sigma$-satisfiable, there exists a function $f\in\cF\setminus\{\veczero\}$ that $f(\sigma^k)\neq 1$. Thus, the corresponding constraint of $I$ is not satisfied by $\vecnu$.

Now we pick a minimal unsatisfied formula $J$ on $kq$ variables with constraints from $\cF\setminus\{\veczero\}$, that is a formula such that all proper subsets of the constraints of $J$ can be simultaneously satisfied. Since $J$ doesn't have zero-constraints, $J$ must have at least two constraints. We partition $J$ into two arbitrary non-empty subsets of constraints $J=J_A\sqcup J_B$. Note that by minimality of $J$, $J_A$ and $J_B$ are both satisfiable.

Observe that item 2(a) of the theorem follows from 2(b) by setting $\eps=\Theta(1/n)$. In order to prove the item 2(b), we reduce $\Disj_{m}$ for $m=|J|^{-1}\eps^{-1}$ to $\maxF$ on $n$ variables.  We can assume that $\eps\geq\frac{kq}{n|J|}$, as for smaller $\eps$ the optimal lower bound of $\Omega(n)$ is implied by this setting. We partition the $n$ variables of $\maxF$ into at least $m$ groups of size $kq$. Let $x,y\in\{0,1\}^{m}$ be the inputs of Alice and Bob in the $\Disj_{m}$ problem. If $x_i=1$, then Alice applies the constraints $J_A$ to the $i$th block of $kq$ variables of the formula. Similarly, if $y_i=1$, then Bob applies the constraints $J_B$ to the $i$th block of $kq$ variables. Let $C_A$ and $C_B$ be the sets of constraints produced by Alice and Bob, respectively, and let $\Psi=C_A\cup C_B$. Since $\Delta(x)=\Delta(y)=m/4$,  the total number of constraints in the formula $|\Psi|=|J|m/4$. Note that $\Psi$ is satisfiable if and only if $\Disj(x, y)=1$. Therefore, if $x$ and $y$ are disjoint, then $\val(C_A\cup C_B)=1$, otherwise

\[
\val(\Psi)\leq 1-\frac{4}{|J|m}<1-\eps
\, .
\]

Any streaming algorithm that receives constraints $C_A$ and $C_B$ and solves $(1,1-\eps)$-$\maxF$ with probability $2/3$, also solves the $\Disj_m$ problem. Therefore, by <ref>, such an algorithm must use space $\Omega(m)=\Omega(1/\eps)$.

In order to prove item 2(c), we reduce the $\GHD_{n,t,g}$ problem to $\maxF$ on $nkq+O(1)=O(n)$ variables, where $t=n(1-\gamma)$ and $g\geq1$ will be determined later. We will create two groups of constraints: the first group of constraints $C_A\cup C_B$ will have value $1-O(\Delta(x,y)/n)$, and the second group of constraints will have value close to $\rho_{\min}$. By taking a weighed combination of these two groups we will get a formula whose value is less than $\gamma-\eps$ for $\Delta(x,y)\geq t+g$, and value is at least $\gamma$ for $\Delta(x,y)\leq t$.

Again, we start with a minimal unsatisfiable formula on $kq$ variables. If $|J|=2d$ is even, then we arbitrarily partition $J$ into two sets of $d$ constraints $J_A$ and $J_B$. If $|J|$ is odd, then we add one constraint to $|J|$ as follows. By minimality, there is an assignment that satisfies $|J|-1$ constraints of $J$, let $c$ be one of these constraints. We add another copy of $c$ to $J$, and partition $J$ into two sets of $d$ constraints $J_A$ and $J_B$. Note that while $J_A$ and $J_B$ are satisfiable, only $2d-1$ constraints of $J_A\cup J_B$ can be satisfied simultaneously.

Let $x,y\in\{0,1\}^n$ be the inputs of Alice and Bob in the $\GHD_{n,t,g}$ problem. If $x_i=1$, then Alice applies the constraints $J_A$ to the $i$th block of $kq$ variables of the formula, otherwise Alice applies the constraint $J_B$ to these variables. Similarly, if $y_i=1$ or $y_i=0$, then Bob applies the constraints $J_A$ or $J_B$ to the $i$th block of $kq$ variables. Let $C_A$ and $C_B$ be the sets of constraints produced by Alice and Bob, respectively. Observe that $|C_A|=|C_B|=nd$. The set of constraints added by Alice and Bob when processing their $i$th coordinates is satisfiable if and only if $x_i=y_i$. When $x_i\neq y_i$, then by the construction of $J$, exactly $2d-1$ constraints are satisfiable. Therefore,

\[
\val(C_A\cup C_B)=1-\frac{\Delta(x,y)}{2dn}
\, .
\]

Let $\gamma'=(\gamma+\rho_{\min})/2<\gamma$. By the definition of $\rho_{\min}(\cF)$, there exists $n_0$ and a formula $\Phi'$ of $\maxf$ such that $\val(\Phi')=\gamma'$. By taking several copies of $\Phi'$ on the same $n_0$ variables, we get an instance $\Phi$ with $D=|\Phi|=\frac{n(2d-1)(1-\gamma)}{\gamma-\gamma'}=\Theta(n)$ constraints and value $\val(\Phi)=\gamma'$.

Now we output an instance $\Psi$ of $\maxF$ on $nkq+n_0$ variables that is simply a union of $C_A \cup C_B$ and $\Phi$ on disjoint sets of variables. By construction.

\[
\val(\Psi)=\frac{(2dn-\Delta(x,y))+\gamma'D}{2dn+D}
\, .
\]

In the case when $\Delta(x,y)\leq t=(1-\gamma)n$, we have

\[
\val(\Psi) \geq \frac{2dn-(1-\gamma)n+\gamma'D}{2dn+D}= \gamma
\, .
\]

And for the case of $\Delta(x,y)\geq t+g=(1-\gamma)n+g$, we have that

\[
\val(\Psi) \leq \frac{(2dn-(1-\gamma)n-g)+\gamma'D}{2dn+D}= \gamma -\frac{g}{2dn+D}=\gamma-\eps
\]

for $g=\eps(2dn+D)=\Theta(n\eps)$.

Therefore, any streaming algorithm for $(\gamma,\gamma-\eps)$-$\maxF$ will imply a protocol for the $\GHD_{n,t,g}$ problem.
By <ref>, any such streaming algorithm must use at least $\Omega(\min\{n, n^2/g^2\})=\Omega(\min\{n, \eps^{-2}\})$ bits of communication.

§ ACKNOWLEDGMENTS

We are grateful to Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, and Huacheng Yu, for detecting a fatal error in an earlier version of this paper [7] and then for pinpointing the location of the error. As a result the main theorem of the current paper is significantly different than the theorem claimed in the previous version.

Thanks to Johan Håstad for many pointers to the work on approximation resistance and answers to many queries.
Thanks to Dmitry Gavinsky, Julia Kempe and Ronald de Wolf for prompt and detailed answers to our queries on outdated versions of their work [12]. Thanks to Prasad Raghavendra for answering our questions about the approximation resistance dichotomy from his work [23]. Thanks to Saugata Basu for the pointers to the algorithms for quantified theory of the reals. Thanks to Jelani Nelson for pointers to $\ell_1$ norm estimation algorithms used in the earlier version of this paper.
Thanks to Alex Andoni for pointers to $\ell_{1,\infty}$ norm estimation algorithms.

[1]
Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak.
Streaming algorithms via precision sampling.
In FOCS 2011, pages 363–372. IEEE, 2011.

[2]
Per Austrin and Elchanan Mossel.
Approximation resistant predicates from pairwise independence.
Comput. Complex., 18(2):249–271, 2009.

[3]
Alexandr Andoni.
Personal communication, 24 December 2020.

[4]
Saugata Basu, Richard Pollack, and Marie-Françoise Roy.
Algorithms in Real Algebraic Geometry.
Springer, 2006.

[5]
Andrei A. Bulatov.
A dichotomy theorem for nonuniform CSPs.
In Chris Umans, editor, FOCS 2017, pages 319–330. IEEE,

[6]
Stephen P. Boyd and Lieven Vandenberghe.
Convex optimization.
Cambridge University Press, 2004.

[7]
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy.
Classification of the streaming approximability of Boolean CSPs.
CoRR, abs/2102.12351v1, 24th February a2021.

[8]
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy.
Approximability of all Boolean CSPs in the dynamic streaming
CoRR, abs/2102.12351v3, 14th April b2021.

[9]
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy.
Approximability of all finite CSPs in the dynamic streaming
CoRR, abs/2105.01161, 3rd May c2021.

[10]
Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy.
Optimal streaming approximations for all Boolean Max-2CSPs and
In FOCS 2020, pages 330–341. IEEE, 2020.

[11]
Amit Chakrabarti and Oded Regev.
An optimal lower bound on the communication complexity of
SIAM J. Comput., 41(5):1299–1317, 2012.

[12]
Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf.
Exponential separation for one-way quantum communication complexity,
with applications to cryptography.
SIAM J. Comput., 38(5):1695–1708, 2009.

[13]
Venkatesan Guruswami and Runzhou Tao.
Streaming hardness of unique games.
In APPROX 2019, pages 5:1–5:12. LIPIcs, 2019.

[14]
Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy.
Streaming complexity of approximating Max 2CSP and Max Acyclic
In APPROX 2017. LIPIcs, 2017.

[15]
Subhash Khot.
On the power of unique 2-prover 1-round games.
In STOC 2002, pages 767–775. ACM, 2002.

[16]
Michael Kapralov and Dmitry Krachun.
An optimal space lower bound for approximating MAX-CUT.
In STOC 2019, pages 277–288. ACM, 2019.

[17]
Jeff Kahn, Gil Kalai, and Nathan Linial.
The influence of variables on Boolean functions.
In FOCS 1988, pages 68–80. IEEE, 1988.

[18]
Michael Kapralov, Sanjeev Khanna, and Madhu Sudan.
Streaming lower bounds for approximating MAX-CUT.
In SODA 2015, pages 1263–1282. SIAM, 2015.

[19]
Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker.
$(1+ \omega(1))$-approximation to MAX-CUT requires linear space.
In SODA 2017, pages 1703–1722. SIAM, 2017.

[20]
Bala Kalyanasundaram and Georg Schintger.
The probabilistic communication complexity of set intersection.
SIAM J. Discrete Math., 5(4):545–557, 1992.

[21]
Subhash Khot, Madhur Tulsiani, and Pratik Worah.
A characterization of strong approximation resistance.
In STOC 2014, pages 634–643, 2014.

[22]
Ryan O'Donnell.
Analysis of Boolean functions.
Cambridge University Press, 2014.

[23]
Prasad Raghavendra.
Optimal algorithms and inapproximability results for every CSP?
In STOC 2008, pages 245–254, 2008.

[24]
Alexander A. Razborov.
On the distributional complexity of disjointness.
In ICALP 1990, pages 249–253. Springer, 1990.

[25]
Thomas J. Schaefer.
The complexity of satisfiability problems.
In STOC 1978, pages 216–226. ACM, 1978.

[26]
Alexander A. Sherstov.
The communication complexity of gap hamming distance.
Theory Comput., 8(1):197–208, 2012.

[27]
Noah Singer, Madhu Sudan, and Santhoshini Velusamy.
Streaming approximation resistance of every ordering csp.
In APPROX 2021, pages 17:1–17:19. LIPIcs, 2021.

[28]
Thomas Vidick.
A concentration inequality for the overlap of a vector on a large
set, with application to the communication complexity of the
gap-hamming-distance problem.
Chicago J. Theor. Comput. Sci., 18(1):1–12, 2012.

[29]
Dmitriy Zhuk.
A proof of CSP dichotomy conjecture.
In FOCS 2017, pages 331–342. IEEE, 2017.