We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on instances with $O(n)$ constraints.
We also identify a broad subclass of problems for which any improvement over the trivial approximability requires $\Omega(n)$ space.
The key technical core is an optimal, $q^{-(k-1)}$-inapproximability for the -$\bmod\; q$ problem, which is the Max CSP problem where every constraint is given by a system of $k-1$ linear equations $\bmod\; q$ over $k$ variables.

Our work builds on and extends the breakthrough work of Kapralov and Krachun (Proc. STOC 2019) who showed a linear lower bound on any non-trivial approximation of the MaxCut problem in graphs. MaxCut corresponds roughly to the case of  -$\bmod\; q$ with ${k=q=2}$. For general CSPs in the streaming setting, prior results  only yielded $\Omega(\sqrt{n})$ space bounds. In particular no linear space lower bound was known for an approximation factor less than $1/2$ for any CSP. Extending the work of Kapralov and Krachun to -$\bmod\; q$ to $k>2$ and  $q>2$ (while getting optimal hardness results) is the main technical contribution of this work. Each one of these extensions provides non-trivial technical challenges that we overcome in this work.

§ INTRODUCTION

In this work we consider the approximability of constraint satisfaction problems (CSPs) by streaming algorithms with sublinear space. We give tight inapproximability results for a broad class of CSPs, while giving somewhat weaker bounds on the approximability of every CSP. We introduce these terms below.

§.§ Background

We consider the general class of constraint satisfaction problems with finite constraints over finite-valued variables. A problem in this class, denoted $\maxF$, is given by positive integers $q$ and $k$ and a family of functions $\cF \subseteq \{f:\Z_q^k \to \{0,1\}\}$. An instance of the problem consists of $m$ constraints placed on $n$ variables that take values in the set $\Z_q = \{0,\ldots,q-1\}$, where each constraint is given by a function $f \in \cF$ and $k$ distinct indices of variables $j_1,\ldots,j_k \in [n]$. Given an instance $\Psi$ of $\maxF$, the goal is to compute the value $\val_\Psi$ defined to be the maximum, over all assignments to $n$ variables, of the fraction of constraints satisfied by the assignment. For $\alpha\in[0,1]$, the goal of the $\alpha$-approximate version of the problem is to compute an estimate $\eta$ such that $\alpha \cdot \val_\Psi \leq \eta \leq \val_\Psi$.

In this work we consider the space complexity of approximating $\maxF$ by a single pass (potentially randomized) streaming algorithm that is presented the instance  $\Psi$ one constraint at a time. We consider “non-trivial” approximation algorithms for $\maxF$, where we first dismiss two notions of “triviality”. First note that since we only consider space restrictions but not time restrictions, one can sample $O(n)$ constraints of $\Psi$ and solve the $\maxF$ problem on the sampled constraint optimally to get a $(1-\epsilon)$-approximation algorithm for every constant $\epsilon>0$ in $\widetilde{O}(n)$ space. Thus for this paper we view non-trivial algorithms to be those that run in $o(n)$ space.[We note that there is a gap between the $o(n)$ space we allow and the $O(n \log n)$ space that is trivial, but we are not able to get sharp enough lower bounds to address this gap.] The other form of “triviality” we dismiss is in the approximation factor.
Given a family $\cF$, let $\rho_{\min}(\cF)$ denote the infimum, over all instances $\Psi$ of $\maxF$, of the value $\val_\Psi$. Note that the algorithm that outputs the constant $\rho_{\min}(\cF)$ is a ($O(1)$-space!) $\rho_{\min}(\cF)$ approximation algorithm for $\maxF$. Thus we consider $\rho_{\min}(\cF)$ to be the “trivial” approximation factor for a family $\cF$. With these two notions of “triviality” in mind, we define $\maxF$ to be $\alpha$-approximable (in the streaming setting) if $\alpha$ is the largest constant such that there exists an $\alpha$-approximation algorithm for $\maxF$ using $o(n)$ space. We say that $\maxF$ is simply approximable (in the streaming setting) if it is $\alpha$-approximable for some $\alpha > \rho_{\min}$. We define a problem to be approximation-resistant (in the streaming setting) otherwise.

§.§ Results

Our first main result in this paper gives a sufficient condition for a problem to be approximation resistant in the streaming setting.
We say that $f:\Z_q^k\to \{0,1\}$ is a wide constraint if there exists $\veca \in \Z_q^k$ such that for every $i \in \Z_q$ we have $f(\veca + i^k)=1$ where $i^k = (i,i,\ldots,i)$ and addition is performed in the group $\Z_q^k$. We say that a family $\cF$ is wide if every function $f \in \cF$ is wide.

For every $q,k$ and every wide family $\cF$, $\maxF$ is approximation-resistant.

Many natural CSPs are wide, including Boolean problems such as Max $k$-SAT and Max $q$-colorability. Others, such as Max $k$-LIN$(q)$ and the “Unique Games” problem,  contain wide subfamilies with the same “trivial” approximation factor, and thus <ref> implies these are also approximation resistant. We elaborate on some of these examples in <ref>. However, clearly wideness does not capture all CSPs. For general CSPs, while we do not pin down the approximability exactly, we do manage to pin it down up to a multiplicative factor of $q$.

For every $q,k$ and every family $\cF$, if $\cF$ is $\alpha$-approximable then $\alpha \in [\rho_{\min}(\cF),q \cdot \rho_{\min}(\cF)]$.

Both <ref> follow from our more detailed <ref>. In <ref> we give a few examples illustrating  how our theorems give tight lower bounds for some commonly studied CSPs including Max $q$-coloring, Unique Games, and Max Linear Systems.

§.§ Prior work

There have been a number of works in the broad area of approximations for streaming constraint satisfaction problems and lower bound techniques for those [7, 15, 11, 1, 12, 9, 8, 10, 6, 2, 3, 4, 14].
Among these our work is the first work to aim to get tight inapproximability results for a broad class of CSPs for almost linear space single-pass streaming algorithms.
Previous works either did not get tight approximation factors or were aimed at specific problems or only got $\Omega(\sqrt{n})$-space lower bounds, though some do target multi-pass streaming algorithms [2, 3] — which we do not do here. We describe the state of the art prior to our work below. (More detailed descriptions of prior works can be found in [4].)

On the front of general lower bounds,
Chou, Golovnev, Sudan and Velusamy [4] explored the same set of CSP problems as we do, i.e, $\maxF$ for arbitrary $q,k$ and $\cF$. Their focus is on looser space lower bounds: specifically, they focus on problems that require $n^{\Omega(1)}$ space vs. those where $n^{o(1)}$ space suffices. They give a complete dichotomy for sketching algorithms, a special class of streaming algorithms. They also give sufficient conditions for approximation resistance with respect to sub-polynomial space general streaming algorithms. Theorem 2.9 in their paper shows that families $\cF$ where the satisfying assignments of every function in the class support a one-wise independent distribution are approximation resistant. This theorem is incomparable with our <ref> in that they give approximation resistance for a broader collection of problems (all wide families support one-wise independence) but the space lower bound is weaker — they give an $\Omega(\sqrt{n})$ lower bound and we get $\Omega(n)$ lower bounds for wide families.
[4] does not give an analogue of our <ref>, though such a result (with the weaker $\Omega(\sqrt{n})$ space lower bound) can be derived from their theorems equally easily. Indeed, our <ref> is based on their work.

Turning to linear space lower bounds the breakthrough work here is due to Kapralov and Krachun [10], who show that approximating Max Cut (which translates in our setting to $\maxF$ for $\cF = \{\oplus_2\}$ where $\oplus_2:\{0,1\}^2 \to \{0,1\}$ is the binary XOR function) to within a factor $\frac12+\epsilon$ requires $\Omega(n)$ space for every $\epsilon >0$. Indeed, our work builds on their work and we compare our techniques later.
Prior to the work of Kapralov and Krachun, there was a weaker result due to Kapralov, Khanna, Sudan and Velingker [12] showing that there exists $\epsilon > 0$ such that  ($1-\epsilon$)-approximation for Max Cut requires linear space. Finally, Chou, Golovnev and Velusamy [6] get a tight
inapproximability for Max Exact 2-SAT (corresponding to $\maxF$ for $\cF = \{\vee_2\}$, where $\vee_2:\{0,1\}^2\to\{0,1\}$ is the binary OR function) for linear space algorithms, by a reduction from Max Cut.

Thus, prior to our work it was conceivable (though of course extremely unlikely) that every $\maxF$ allowed a $1/2$-approximating streaming algorithm using $o(n)$ space. Our work is the first to prove inapproximability $\alpha \leq 1/2$ for any $\maxF$. Indeed, we get inapproximabilities going to $0$ either as $q \to \infty$ (e.g., for the Unique Games problem) or as $k \to \infty$ (e.g., for the Max $k$-equality problem with $q = 2$ as defined later in <ref>).

The main contribution of our work is to extend the techniques of [10] to problems beyond Max Cut.  Indeed the bulk of our proof takes the tour-de-force proof in [10] and finds the correct replacements in our setting. In the process, we arguably even present cleaner abstractions of their work. We elaborate on this further in the next section but first comment on why we feel the extensions are not straightforward given [10]. First we note that the exact class of problems we are able to deal with in <ref> is not the fullest extension one may hope for. At the very least we have expected to cover the same set of problems as <cit.>, i.e., families supporting one-wise independent distributions, but this remains open. Indeed to get our extensions we have to formulate a new communication problem which generalizes the one in [10] and is different from the many variations considered in [5] and [4]. In particular we are forced to work with a less expressive set of communication problems that already forces a “linear-algebraic” restriction on the core problems we work with. (We do believe a slight extension of our results to “families containing  one-wise independent cosets of $\Z_q^k$” should be more feasible.) Having identified the right set of problems, carrying out the proof of Kapralov and Krachun is still non-trivial. In particular one has to be careful to ensure that the improvement in the exponent of the space bound (from $n^{1/2}$ to $n$) is by a full factor of $2$ and not a factor of $k/(k-1)$, which is what one natural extension would lead to! We comment on these improvements in greater detail in the following.

Finally we point out that an extension of the lower bounds in [4] to $\Omega(n)$ space lower bounds may actually be false. In particular, there is a candidate algorithm for one of the problems (Max $2$-AND) that might improve on the approximation factors with $\omega(\sqrt{n})$ space. It certainly works better on the hard instances from previous reductions, but we do not have an improved analysis on all graphs.

§.§ Techniques and New Contributions

There are two lines of previous work that seem relevant to this work and we discuss our technical contributions relative to those here. We start with quick comparison with the previous work [4] that gives $\Omega(\sqrt{n})$ lower bounds for a broader subset of problems than those addressed in this paper. We then move on to the work [10] which is much closer to our work and needs more detailed comparison.

Comparison with [4].  While there is some obvious overlap in the set of problems considered in [4]  and this paper (and also in the set of authors) we claim that, beyond this aspect, the overlap in techniques is minimal. Both papers do use lower bounds on communication problems to establish lower bounds on streaming CSPs (which is standard in the context of streaming lower bounds). But the exact set of communication problems is different, and the tools used to establish the lower bounds are also different. In particular, [4] create roughly a new communication problem for every $\gamma,\beta$ and $\cF$ and the main technical contributions there are lower bounds for these problems achieved mainly through a rich set of reductions among these communication problems. In our work we essentially work with one communication problem (once we fix $k$ and $q$) and the core of our work is proving a lower bound for this problem. (This lower bound is based on extending [10] and we will elaborate on this later.) We use this one problem to get hardness for many different $\gamma,\beta$ and $\cF$ — this part is arguably related to the work of [4] but we feel this is the obvious part of their work as well as our work. Finally, turning to the communication problems, the natural communication problems used to analyze streaming complexity involves one way communication among a large constant number of players. The exact problem of this type that we focus on is different from the ones considered in [4] due to a concept we call “folding”. Folding makes our problems too restrictive to work for [4] (i.e., would prevent them for addressing every $(\gamma,\beta)-\maxF$), whereas we do not know how to get our lower bounds without folding. We also note that [4] derive their multiplayer lower bounds from lower bounds for a corresponding 2-player game and all their reductions work only for these 2-player games, which are inherently limited to yielding $\Theta(\sqrt{n})$ space lower bounds.

We now turn to the more significant comparison, with [10]. We start with a quick review of the main steps of [10] and then describe our analysis and conclude with a summary of the differences/new contributions relative to [10].

Summary of [10].
[10] work with a distributional $T$-player one-way communication game for some constant $T$. The game also has a parameter $\alpha > 0$. In instances of length $n$ of this game,  $T$ players $P_1,\ldots,P_T$ get partial matchings $M_1,\ldots,M_T$ on the vertex set $[n]$ along with respective binary labels $\vecz_1,\ldots,\vecz_T$ on the edges of the matchings, i.e., player $t$ receives input $(M_t,\vecz_t)$. Each matching contains $\alpha n$ edges, while each corresponding label $\vecz_t$ is an element of $\{0,1\}^{\alpha n}$. In the communication game, the players sequentially broadcast messages as follows. Player $t \in [T-1]$ computes a small message $c_t$ which is a function of $M_t,\vecz_t$ and all “previous messages” $c_1,\ldots,c_{t-1}$,[For technical reasons the lower bounds are proved in the stronger model where player $t$ get $M_1,\ldots,M_{t-1}$ as well, but this difference is not crucial for the current discussion.] after which the $T$th player outputs a single $0/1$ bit that is said to be the output of the communication protocol. The complexity of the protocol is the maximum over $t\in [T]$ of the message length $c_t$, and the goal of the players is to distinguish input instances drawn according to a  distribution from those drawn according to a  distribution, defined as follows.

In instances chosen from the  distribution, the matchings $M_1,\ldots,M_T$ are chosen uniformly and independently from the set of matchings containing $\alpha n$ edges on the vertex set $[n]$. Furthermore, the vectors $\vecz_1,\ldots,\vecz_T$ are chosen uniformly and independently from $\{0,1\}^{\alpha n}$. In the  distribution, the matchings are chosen as in the  distribution, but in order to generate $\vecz_1,\ldots,\vecz_T$, we choose a common hidden vector $\vecx^* \in \{0,1\}^n$ uniformly at random and set each $\vecz_t$ as $\vecz_t(e) = x^*_a \oplus_2 x^*_b$ for every edge $e = (a,b)$. Thus, the label $\vecz_t$ can be viewed as specifying which edges of the $i$-th matching cross the cut determined by $\vecx^*$. If $T \gg \frac1\alpha$ then it can be seen that the  and  distributions are very far. The key theorem shows that for every $\alpha > 0$ and $T$, any protocol distinguishing  instances from  instances with constant advantage requires $\Omega(n)$ space. With this lower bound a space lower bound on Max Cut is straightforward.

Turning to the communication lower bound, the focus of the analysis are the sets $B_1,\ldots,B_T \subseteq \{0,1\}^n$ corresponding to the purported hidden vector $\vecx^*$ that are consistent with the messages $c_1,\ldots,c_T$. Specifically for $t \in [T]$, $B_t$ is the set of all vectors $\vecx^*$ that are consistent with the first $t$ matchings $M_{1:t}$ and the first $t$ messages $c_{1:t}$. [10] argue that the sets $B_t$ are not shrinking too fast (in either the  case or the  case) using a property that they term “$C$-boundedness,” defined by the Fourier spectrum of the indicator function of $B_t$ (the function in $\{0,1\}^n$ to $\{0,1\}$ that is $1$ on $B_t$). We do not give the exact definition of boundedness here but roughly describe it as follows: Given an arbitrary set $B$ of size $S$ and a Fourier weight $w$, the total Fourier mass (strictly the $\ell_1$-mass)  of the $w$th level Fourier coefficients of $B$ is well-known (by classical Fourier analysis) to be bounded by some amount $U(w) = U_{S,n}(w)$. For $C$-bounded sets, the corresponding Fourier mass is required to be at most $C^w U(w/2)$. The factor of two gained here in the argument of $U$ is the crux to improvement in the space lower bound from $\sqrt{n}$ to $n$. (If the right hand side had been of the form $C^w U(\alpha w)$ then the space lower bound would be $\Omega(n^{1/(2\alpha)})$.) This factor of two, in turn, is attributable to the fact that the $\vecz_t$ only contain information about pairs of bits of $\vecx^*$.
Their analysis shows that, for every $t$, $B_t$ is $C_t$-bounded for some constant $C_t$. (The proof is inductive on $t$ but the inductive hypothesis is complex and we won't reproduce it here.) They further show that if $B_T$ is $C$-bounded for some constant $C$, then the distinguishing probability is at most $o(1)$.

Our Analysis.
The core of our paper focuses on one problem for every given $q$ and $k$, which we call . This is the problem given by $\maxF$ for $\cF = \{f_{b_2,\ldots,b_{k}}:\Z_q^k \to \{0,1\}\}$, where $f_{b_2,\ldots,b_{k}}(a_1,\ldots,a_k) = 1$ if and only if $a_t = a_1 + b_t \bmod q$ for every $t \in \{2,\ldots,k\}$. All our lower bounds effectively come from a tight $q^{-(k-1)}$-inapproximability of this problem for every $q$ and $k$.

To study this problem we introduce a $T$-player communication problem that we call the “Implicit Randomized Mask Detection Problem” (IRMD) described as follows: There are $T$ players each of whom receives an $\alpha n$ $k$-hypermatching $M_t$ (i.e., a set of $\alpha n$ $k$-uniform hyperedges on $[n]$ that are pairwise disjoint). Additionally, the players receive a label in $\Z_q^{k}$ for every hyperedge they see. Thus the $i$th player's input is $(M_t,\vecz_t)$ where $\vecz_t \in (\Z_q^{k})^{\alpha n}$. In the  distribution the $\vecz_t$'s are drawn uniformly. In the  distribution a vector
$\vecx^* \in [q]^n$ is drawn uniformly and the label associated with an edge $\vecj = (j_1,\ldots,j_k)$ is $(x^*_{j_1} + a_{\vecj},\ldots,x^*_{j_k} + a_{\vecj})$ where $a_{\vecj} \in [q]$ is chosen uniformly and independently for each edge in each matching. The goal of the players is to distinguish between the  and  distributions with minimal communication (with one-way communication from the $t-1$th player to the $t$th player, as before).

To lower bound the communication complexity of IRMD we consider a  folded version of the problem we call IFRMD where the labels associated with an edge are from
$\Z_q^{k-1}$ and obtained by mapping an IRMD label $\vecz = (z^{(1)},\ldots,z^{(k)}) \in \Z_q^k$ to the label $\tilde{\vecz} = (z^{(2)} - z^{(1)},\ldots,z^{(k)}-z^{(1)})$.
With this folding we recover the same communication problem as [10] for the case of $k=q=2$ and the main focus of our work is proving lower bounds for higher $k$ and $q$.

Our analysis of the communication complexity of IFRMD follows the same sequence of steps (with imitation even within the steps) as [10]. In particular we also use the same sets $B_1,\ldots,B_T$ and use the same notion of boundedness.

Turning to the induction and the analysis of boundedness of $B_t$ for general $t$,  we are able to extract a clean lemma (<ref>) that makes the induction completely routine. To explain this contribution note that $B_t$ is the intersection of $B_{t-1}$ with a set say $A_t$ where $A_t$ is of the same type as $B_t$ (both are obtained by looking at the vector $\vecx^*$ projected to a matching followed by some folding). Thus both $B_{t-1}$ and $A_t$ are bounded sets. To complete the induction it would suffice to prove that the intersection of bounded sets is bounded, but alas this is not true! To get that $B_t$ is bounded, we need to use the fact that the matching $M_t$ is random and chosen independently of $B_{t-1}$ but it turns out that that is all that is needed. This is exactly what we show in <ref> — and of course this only happens with high probability over the choice of $M_t$.

Incremental contribution over [10].
Given that our result closely follows [10] we now focus on some key differences, and why these contributions are conceptually significant.

* The analysis of [10] is intricate and it is not a priori clear what problems it may extend to. Our choice of $\maxkeqq$ is not the obvious choice, and was not our first choice. More natural choices would be to go for more general linear systems, or even functions supporting “one-wise independence”, but we are unable to push the analysis to more general cases. Our choice reflects an adequate one to get coarse bounds on the approximability of every problem while getting tight ones for many natural ones.

* The choice of the communication problems to work with is also not obvious: Indeed working with both IRMD and IFRMD seems necessary for our approach — the former is more useful for our final inapproximability results whereas the latter is the one we are able to analyze.

* The exact notion of boundedness that is necessary and sufficient for our results is also not completely obvious. It is only in hindsight, after carrying out the entire analysis, does it become clear that the notion that works is exactly the same as the one in [10]. Part of the challenge is that in the inductive proof of boundedness even the base case (which is quite simple in [10]) is not obvious in our case, and nor is the inductive step.

* With respect to the base case we note that if we had adopted a weaker notion of boundedness allowing $w$th level Fourier mass to grow roughly as $U((k-1)w/k)$ boundedness would have been easier to prove but the result would not be optimal. Getting a bound of $U(w/2)$ is not technically hard, but involves a non-trivial randomization in the choice of folding purely for analysis purposes. (So there is an implicit passing back and forth between the IRMD and IFRMD problems in this technical step.)

* We also feel that it is important that we are able to extract an induction lemma (<ref>) that clearly separates the (Fourier and combinatorial) analytic ingredients from the probabilistic setup. We believe the lemma is clarifying even when applied to the proof of [10].

* Finally we note that the underlying combinatorics are made significantly more intricate due to the need to work with $k > 2$. A conceptual difference from [10] here is that whereas they explore the distribution of the number of edges in a random matching that intersect with a fixed set of vertices, we have to explore the distribution of edges that have an odd intersection (or non-zero mod $q$ intersection) with a random hypermatching. Indeed this part is clarifying the role of some of the quantities explored in the previous work. Additionally, we note that the number of parameters we have to track is much larger (and indeed it is fortunate that the number of parameters remains a constant independent of $k$), and managing these in our inequalities is a non-trivial technical challenge (even given the heavy lifting in [10]).

Organization of the rest of the paper. We start with some background material in <ref>. We introduce our communication problems ( and ) in <ref> and state our lower bounds for these. We use these lower bounds to prove our streaming lower bounds in <ref>. <ref> introduces the notion of bounded sets and proves our lower bound on the communication problems modulo some lemmas on the boundedness of sets encountered by the protocol.
<ref> proves these lemmas on boundedness concluding the proofs.
<ref> proves these lemmas on boundedness. The appendix includes a few remaining technical proofs.

§ PRELIMINARIES

We use the following notations throughout the paper. Let $\N=\{1,\dots\}$ denote the set of natural numbers and let $[n]=\{1,2,\dots,n\}$. For a discrete set $X$ and a function $f:X\rightarrow\mathbb{R}$, we denote $\|f\|_p=(\sum_{x\in X}|f(x)|^p)^{1/p}$ for every $p>0$ and $\|f\|_0=\sum_{x\in X}\mathbf{1}_{f(x)\neq 0}$.

§.§ Total variation distance

In our analysis we will use the total variation distance between probability distributions, and several bounds on it presented in this section.

Let $\Omega$ be a finite probability space and $X,Y$ be random variables with support $\Omega$. The total variation distance between $X$ and $Y$ is defined as follows.

\[
\|X-Y\|_{tvd} :=\frac{1}{2}
\sum_{\omega\in\Omega}\left|\Pr[X=\omega]-\Pr[Y=\omega]\right| \, .
\]

We will use the triangle and data processing inequalities for the total variation distance.

For random variables $X, Y$ and $W$:

* (Triangle inequality) $\|X-Y\|_{tvd}\geq\|X-W\|_{tvd}-\|Y-W\|_{tvd}$.

* (Data processing inequality) If $W$ is independent of both $X$ and $Y$, and $f$ is a function, then  $\|f(X,W)-f(Y,W)\|_{tvd}\leq\|X-Y\|_{tvd}$.

Let $X,~Y,~W$ be random variables and let $f$ be a function. If there exists $\delta>0$ such that for every fixed $x$ in the support of $X$, we have

\[\|f(x,Y)-f(x,W)\|_{tvd}\le \delta\, , \]
then the following holds:

\[\|(X,f(X,Y))-(X,f(X,W))\|_{tvd}\le \delta\, .\]

Consider any statistical test $T$ distinguishing the joint distributions $(X,f(X,Y))$ and $(X,f(X,W))$. It suffices to prove that

\[\mathbb{E}_{X,Y}[T(X,f(X,Y))]-\mathbb{E}_{X,W}[T((X,f(X,W)))]\le \delta \, .\]

We have

\begin{align*}
&\mathbb{E}_{X,Y}[T(X,f(X,Y))]-\mathbb{E}_{X,W}[T((X,f(X,W)))] \\
&=  \mathbb{E}_{x\sim X}\left[\mathbb{E}_{y\sim Y\mid X=x}[T(x,f(x,y))]\right] - \mathbb{E}_{x\sim X}\left[\mathbb{E}_{w\sim W\mid X=x}[T(x,f(x,w))]\right]\\
&= \mathbb{E}_{x\sim X}\left[\mathbb{E}_{y\sim Y\mid X=x}[T(x,f(x,y))]-\mathbb{E}_{w\sim W\mid X=x}[T(x,f(x,w))]\right]\\
&\le \mathbb{E}_{x\sim X}[\delta] = \delta \, ,
\end{align*}

where the last step follows from the hypothesis that for every fixed $x$, we have
\[\|f(x,Y)-f(x,W)\|_{tvd}\le \delta\, . \]

We will also need the following lemma from [10].

Let $X^1,X^2$ be random variables taking values on finite sample space $\Omega_1$. Let $Z^1,Z^2$ be random variables taking values on sample space $\Omega_2$, and suppose that $Z^2$ is independent of $X^1,X^2$. Let $f:\Omega_1\times\Omega_2 \rightarrow \Omega_3 $ be a function. Then

\[
\|(X^1,f(X^1,Z^1))-(X^2,f(X^2,Z^2)) \|_{tvd} \le \|(X^1,f(X^1,Z^1))-(X^1,f(X^1,Z^2)) \|_{tvd} + \|X^1-X^2\|_{tvd} \, .
\]

§.§ Concentration inequality

We will use the following concentration inequality from [10] which is essentially an Azuma-Hoeffding style inequality for submartingales.

Let $X=\sum_{i\in[N]}X_i$ where $X_i$ are Bernoulli random variables such that for every $k\in[N]$, $\Exp[X_k \, |\, X_1,\dots,X_{k-1}]\leq p$ for some $p\in(0,1)$. Let $\mu=Np$. For every $\Delta>0$, we have:

\[
\Pr\left[X\geq\mu+\Delta\right]\leq\exp\left(-\frac{\Delta^2}{2\mu+2\Delta}\right) \, .
\]

§.§ Fourier analysis

In this paper, we will use Fourier analysis over $\Z_q$ (see, for instance, [13, 8]).
For a function $f: \Z_q^n \to \Comp$, its Fourier coefficients are defined by $\widehat{f}(\vecu) = \frac{1}{q^n}\sum_{\veca\in\Z_q^n}f(\veca)\cdot\overline{\omega^{\vecu^\top\veca}}$, where $\vecu\in\Z_q^n$ and $\omega=e^{2\pi i/q}$ is the primitive $q$-th root of unity. In particular, for every $\veca$,  $f(\veca)=\sum_{\vecu\in\Z_q^n}\widehat{f}(\vecu)\cdot\omega^{\vecu'^\top\veca}$.
Later we will use the three following important tools.
Note that here we define the $p$-norm of $f$ as $\|f\|_p^p=\sum_{\vecx\in\Z_q^n}|f(\vecx)|^p$ rather than the standard definition which uses expectation. This is for future notational convenience.

For every function $f:\Z_q^n\to\Comp$,

\[
\|f\|_2^2=\sum_{\veca\in\Z_q^n}f(\veca)^2=q^n\sum_{\vecu\in\Z_q^k}\widehat{f}(\vecu)^2 \, .
\]

Note that for every distribution $f$ on $\Z_q^n$, $\widehat{f}(0^n)=q^{-n}$. For the uniform distribution $U$ on $\Z_q^n$, $\widehat{U}(\vecu)=0$ for every $\vecu\neq0^n$. Thus, by <ref>, for any distribution $f$ on $\Z_q^n$:

\begin{align}\label{eq:dist}
\|f-U\|_2^2=q^n\sum_{\vecu\in\Z_q^n}\left(\widehat{f}(\vecu)-\widehat{U}(\vecu)\right)^2=q^n\sum_{\vecu\in\Z_q^n\backslash\{0^n\}}\widehat{f}(\vecu)^2 \, .
\end{align}

We now introduce some standard facts about how convolutions interact with the Fourier transform operation. For functions $f,g\colon \Z_q^n \to \Comp$, their convolution $f\star g\colon \Z_q^n \to \Comp$ is defined as $(f\star g)(\veca)=\sum_{\vecv\in\Z_q^n} f(\vecv) g(\veca-\vecv)$. The first lemma is the so-called “convolution theorem,” which essentially states that, up to normalization factors, the Fourier transform of the convolution of two functions is equal to the product of the individual Fourier transforms.

For $f,g: \Z_q^n \to \Comp$, we have

\[
\widehat{f\star g}(\vecu) = q^n \cdot \widehat{f}(\vecu)\cdot\widehat{g}(\vecu).
\]

for all $\vecu \in \Z_q^n$.

Note that

\begin{align*}
\widehat{f\star g}(\vecu) &= \frac{1}{q^n} \sum_{\veca \in \Z_q^n} (f\star g)(\veca) \cdot \overline{\omega^{\vecu^\top \veca}}\\
&= \frac{1}{q^n} \sum_{\veca \in \Z_q^n} \left(\sum_{\vecv\in\Z_q^n} f(\vecv) g(\veca-\vecv)\right)  \overline{\omega^{\vecu^\top \veca}}\\
&= \frac{1}{q^n} \sum_{\veca \in \Z_q^n} \sum_{\vecv\in\Z_q^n} f(\vecv) \overline{\omega^{\vecu^\top \vecv}} \cdot g(\veca-\vecv) \overline{\omega^{\vecu^\top (\veca-\vecv)}} \\
&= \frac{1}{q^n} \sum_{\vecv\in\Z_q^n} f(\vecv) \overline{\omega^{\vecu^\top \vecv}} \cdot \sum_{\veca \in \Z_q^n} g(\veca-\vecv) \overline{\omega^{\vecu^\top (\veca-\vecv)}}\\
&= q^n \cdot \frac{1}{q^n}\sum_{\vecv\in\Z_q^n} f(\vecv) \overline{\omega^{\vecu^\top \vecv}} \cdot \frac{1}{q^n}\sum_{\veca \in \Z_q^n} g(\veca) \overline{\omega^{\vecu^\top \veca}}\\
&= q^n \cdot \widehat{f}(\vecu) \cdot \widehat{g}(\vecu),
\end{align*}

as desired.

We will also need the following lemma, which states that the Fourier transform of the product of two functions is given by the convolution of the individual Fourier transforms.

For every $f,g:\Z_q^n\to\Comp$, and $\vecu\in\Z_q^n$, we have

\[
\widehat{f\cdot g}(\vecu) = \sum_{\vecu'\in\Z_q^n}\widehat{f}(\vecu')\cdot\widehat{g}(\vecu-\vecu')\,.
\]

Furthermore, for every $h\in[n]$,

\[
\sum_{\substack{\vecu\in\Z_q^n\\ \|\vecu\|_0=h}}\widehat{f\cdot g}(\vecu) = \sum_{\vecu\in\Z_q^n}\sum_{\substack{\vecu'\in\Z_q^n\\ \|\vecu+\vecu'\|_0=h}}\widehat{f}(\vecu)\cdot\widehat{g}(\vecu')\,.
\]

For every $\vecu\in\Z_q^n$, we have

\begin{align*}
\widehat{f\cdot g}(\vecu) &= \frac{1}{q^n}\sum_{\veca\in\Z_q^n}f(\veca)\cdot g(\veca)\cdot\overline{\omega^{\vecu^\top\veca}} \\
&= \frac{1}{q^n}\sum_{\veca\in\Z_q^n} \left(\sum_{\vecu'\in\Z_q^n}\widehat{f}(\vecu')\cdot\omega^{\vecu'^\top\veca}\right)\cdot g(\veca)\cdot\overline{\omega^{\vecu^\top\veca}} \\
&= \sum_{\vecu'\in\Z_q^n}\widehat{f}(\vecu')\cdot \left(\frac{1}{q^n}\sum_{\veca\in\Z_q^n}g(\veca)\cdot \overline{\omega^{(\vecu-\vecu')^\top\veca}}\right) \\
&= \sum_{\vecu'\in\Z_q^n}\widehat{f}(\vecu')\cdot\widehat{g}(\vecu-\vecu')\, .
\end{align*}

Next, for every $h\in[n]$,

\begin{align*}
\sum_{\substack{\vecu\in\Z_q^n\\ \|\vecu\|_0=h}}\widehat{f\cdot g}(\vecu) &= \sum_{\substack{\vecu\in\Z_q^n\\ \|\vecu\|_0=h}}\sum_{\vecu'\in\Z_q^n}\widehat{f}(\vecu')\cdot\widehat{g}(\vecu-\vecu') \,
\intertext{Letting $\vecw=\vecu-\vecu'$ and switching the order of the summations, the equation becomes}
&= \sum_{\vecu'\in\Z_q^n}\sum_{\substack{\vecw\in\Z_q^n\\ \|\vecw+\vecu'\|_0=h}}\widehat{f}(\vecu')\cdot\widehat{g}(\vecw) \, ,
\end{align*}

which, after renaming variables, proves the furthermore part of the lemma.

The hypercontractivity theorem states that the 2-norm of a function after the application of a noise operator can be nicely upper bounded.

Let $f:\Z_q^n\to\Comp$ be a square-integrable function and let $1<p<2$,
$0 \leq \rho \leq \frac1{\sqrt{p-1}}(1/q)^{1/2 - 1/p}$,
we have

\[
\|T_\rho f\|_2\leq\|f\|_p \,,
\]

where $T_\rho$ is the noise operator defined by $T_\rho f(\vecx)=\sum_{\vecu\in\Z_q^n}\widehat{f}(\vecu)\rho^{\|\vecu\|_0}\omega^{\vecu^\top\vecx}$.

Next, we prove the following consequence of the hypercontractivity theorem.

There exists $\zeta > 0$ such that for every $q$, every $f:\Z_q^n\to\{a\in\Comp\, |\, |a|\leq1\}$ and $B=\{\veca\in\Z_q^n\, |\, f(\veca)\neq0\}$ the following holds: If $|B|\geq q^{n-b}$ for some $b\in\N$, then for every $\vecv\in\Z_q^n$ and every $h\in\{1,\dots,4b\}$, we have

\[
\frac{q^{2n}}{|B|^2}\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu+\vecv\|_0=h}}|\widehat{f}(\vecu)|^2\leq\left(\frac{\zeta\cdot b}{h}\right)^h \, .
\]

First, let us consider $\vecv = 0^n$ and $f:\Z_q^n\to\{a\in\Comp\, |\, |a|\leq1\}$. Let us pick $p = 1 + \frac{h}{\zeta b}$ and $\rho = \frac{1}{\sqrt{p-1}}(1/q)^{1/2-1/p}$, where $\zeta > 4$ is a constant to be specified later. Assume $|B|\geq q^{n-b}$.

The choices of $p$ and $\rho$ satisfy the preconditions of <ref>, and so applying <ref> we have

\[
\sum_{\vecu\in\Z_q^n}\rho^{2\|\vecu\|_0}|\widehat{f}(\vecu)|^2 = \|T_\rho f\|_2^2  \leq \|f\|_p^2 = \left(\frac{1}{q^n}\sum_{\vecx\in\Z_q^n}|f(\vecx)|^{p}\right)^{2/p} \leq \left(\frac{|B|}{q^n}\right)^{2/p}.
\]

Now, suppose $h\in \{1,\dots, 4b\}$. Noting that $\rho^{2h}\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu\|_0=h}}|\widehat{f}(\vecu)|^2 \leq \sum_{\vecu\in\Z_q^n} \rho^{2\|\vecu\|_0} |\widehat{f}(\vecu)|^2$, we have

\begin{align}
\frac{q^{2n}}{|B|^2}\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu\|_0=h}}|\widehat{f}(\vecu)|^2 &\leq \frac{1}{\rho^{2h}}\left(\frac{q^n}{|B|}\right)^{2-2/p} \nonumber \\
&\leq \frac{1}{\rho^{2h}} q^{(2-2/p)b} \nonumber\\
&= \frac{q^{\left(1+\frac{2b}{h}-\frac{2}{p}-\frac{2b}{hp}\right)h}}{(p-1)^h} \nonumber\\
&= \left(\frac{\zeta b}{h} \cdot  q^{1+\frac{2b}{h}-\frac{2}{p}-\frac{2b}{hp}}\right)^h, \label{eq:qbratio}
\end{align}

where the first equality above is by our choice of $\rho$ and the second by our choice of $p$.
Observe that the exponent of $q$ in the final expression above can be bounded as follows:

\begin{align}
1 + \frac{2b}{h}-\frac{2}{p}-\frac{2b}{ph} &= 1 + \frac{2b}{h} - \frac{2\left(1+\frac{b}{h}\right)}{1+\frac{h}{\zeta b}} \nonumber\\
&= \left(1+\frac{h}{\zeta b}\right)^{-1} \left(\frac{2}{\zeta} + \frac{h}{\zeta b} - 1\right) \nonumber\\
&\leq  \left(1+\frac{h}{\zeta b}\right)^{-1} \left(\frac{6}{\zeta}-1\right). \label{eq:qexp}
\end{align}

Note that if we set $\zeta = 6$, then it follows that (<ref>) is $\leq 0$. For this choice of $\zeta$, (<ref>) can be bounded from above by $\left(\frac{\zeta b}{h}\right)^h$, implying that

\[
\frac{q^{2n}}{|B|^2}\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu\|_0=h}}|\widehat{f}(\vecu)|^2 \leq \left(\frac{\zeta b}{h}\right)^h.
\]

In order to extend the above to sums over translational shifts, i.e., $\vecu$ such that $\|\vecu+\vecv\|_0 = h$ for an arbitrary $\vecv\in\Z_q^n$, consider the function $g(\vecx)=f(\vecx)\cdot{\omega^{\vecx^\top\vecv}}$. We have for every $\vecx\in\Z_q^n$,

\[
\widehat{g}(\vecu)=q^{-n}\sum_{\veca\in\Z_q^n}g(\veca)\overline{\omega^{\veca^\top\vecu}}=q^{-n}\sum_{\veca\in\Z_q^n}f(\veca)\overline{\omega^{\veca^\top(\vecu-\vecv)}}=\widehat{f}(\vecu-\vecv) \, .
\]

By applying the above analysis on $g$, we have

\[
\frac{q^{2n}}{|B|^2}\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu+\vecv\|_0=h}}|\widehat{f}(\vecu)|^2 = \frac{q^{2n}}{|B|^2}\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu\|_0=h}}|\widehat{g}(\vecu)|^2 \leq\left(\frac{\zeta b}{h}\right)^h,
\]

as desired.

§ COMMUNICATION PROBLEMS

Throughout this paper, we will be dealing with $k$-hypermatchings on vertices from the set $[n]$, i.e., a set of edges $e_1,\ldots,e_m$ where $e_i \subseteq [n]$, $|e_i| = k$ and $e_i \cap e_j = \emptyset$ for every $i \ne j \in [m]$. We let $e_i = \{(e_i)_1,\ldots,(e_i)_k\}$. The direct encoding of a matching $M = \{e_1,\ldots,e_m\}$ will be given by a hypermatching matrix $A \in \{0,1\}^{km \times n}$ where $A_{k(i-1)+\ell,j} = 1$ if and only if $j = (e_i)_\ell$. (Thus, $A$ is a matrix with row sums being $1$ and column sums being at most $1$. Note that $A$ also depends on the ordering of $e_1, e_2, \dots, e_m$ as well as the ordering of the nodes within each $e_i$.)

We will also find it convenient to refer to edges by their indicator vectors in $\Z_q^n$. For an edge $e_i$, we will use the boldface notation $\vece_i \in \Z_q^n$ to refer to this vector, i.e., $(\vece_i)_j = 1$ if $j = (e_i)_\ell$ for some $\ell \in [k]$, while $(\vece_i)_j = 0$ otherwise.

We are now ready to define the communication game, which we term the Implicit Randomized Mask Detection (IRMD) problem:

Let $q,k,n,T\in\mathbb{N}$ and $\alpha\in(0,1/k)$ be parameters. Let $\cD_Y$ and $\cD_N$ be distributions over $\Z_q^k$.
In the $(\cD_Y,\cD_N)$-$\IRMD_{\alpha,T}$ game, there are $T$ players and a hidden $q$-coloring encoded by a random $\vecx^*\in\Z_q^n$. The $t$-th player has two inputs: (a.) $A_t\in\{0,1\}^{\alpha kn\times n}$, the hypermatching matrix (see above) corresponding to a random hypermatching $M_t$ of size $\alpha n$ and (b.) a vector $\vecz_t\in\Z_q^{\alpha kn}$ that can be generated from one of two different distributions:

* (Yes) $\vecz_t=A_t \vecx^*+\vecb_t$ where $\vecb_t\in\Z_q^{\alpha kn}$ is of the form $\vecb_t=(\vecb_{t,1},\dots,\vecb_{t,\alpha n})$ and each $\vecb_{t,i}\in\Z_q^k$ is sampled from $\cD_Y$.

* (No) $\vecz_t=A_t \vecx^*+\vecb_t$ where $\vecb_t\in\Z_q^{\alpha kn}$ is of the form $\vecb_t=(\vecb_{t,1},\dots,\vecb_{t,\alpha n})$ and each $\vecb_{t,i}\in\Z_q^k$ is sampled from $\cD_N$.

This is a one-way game where the $t$-th player can send a private message to the $(t+1)$-th player after receiving a message from the previous player. The goal is for the $T$-th player to be able to decide whether the $\{\vecz_t\}$ have been chosen from the “Yes” distribution or “No” distribution. The advantage of a protocol (in which the $T$-th player outputs either “Yes” or “No”) is defined as $|\Pr_{\cD_Y}[\text{the }T\text{-th player outputs Yes}]-\Pr_{\cD_N}[\text{the }T\text{-th player outputs Yes}]|$.

We remark that the inputs to the $T$ players in the  problem can be viewed as a stream $\vecsigma = \vecsigma^{(1)} \circ \cdots \circ \vecsigma^{(T)}$, where the $t$-th player's input $(A_t,\vecz_t)$ is converted to a stream $\vecsigma^{(t)}=(\sigma^{(t)}(i) | i \in [\alpha n])$ where the elements of the stream are of the form $\sigma^{(t)}(i) = (\vecj^{(t)}(i),\vecz^{(t)}(i))$ with $\vecj^{(t)}(i) \in [n]^k$ is a sequence of $k$ distinct elements of $[n]$ and $\vecz^{(t)}(i) \in \Z_q^k$. This “streaming” representation will be used when we relate the complexity of  to the approximability of various $\maxF$ problems in <ref>.

We suppress the subscripts $\alpha$ and $T$ when they are clear from context. Furthermore,
we simply use $\IRMD$ to refer to $(\cD_Y,\cD_N)$-$\IRMD$ with $\cD_Y$ being the uniform distribution over $\{0^k,1^k,\dots,(q-1)^k\}$ and $\cD_N$ being the uniform distribution over $\Z_q^k$.
The following theorem shows that in this special case, the $\IRMD$ problem requires linear communication.
We remark that the  theorem could hold for other pairs of distributions and leave the question of when such a lower bound holds as an interesting open problem.

For every $q,k\in\mathbb{N}$ and $\delta\in(0,1/2)$, $\alpha\in(0,1/k)$, $T\in\mathbb{N}$ there exists $n_0 \in \mathbb{N}$ and  $\tau\in(0,1)$ such that the following holds. If $\cD_Y,\cD_N$ are the uniform distributions over $\{0^k,1^k,\dots,(q-1)^k\}$ and $\Z_q^k$ respectively and $n \geq n_0$ then every protocol for $(\cD_Y,\cD_N)$-$\IRMD_{\alpha,T}$ with advantage $\delta$ requires $\tau n$ bits of communication.

We prove the hardness of $\IRMD$ by first proving the hardness of a folded version of $\IRMD$.
In the folded version of the communication problem, we augment each hyperedge with an associated center $c \in e$. Given a $k$-hypermatching $M = (e_1,\ldots,e_m)$ and a sequence of centers $\vecc = (c_1,\ldots,c_m)$ with $e_i = ((e_i)_1,\ldots,(e_i)_k = c_i)$, the $\vecc$-centered folded encoding of $M$ is the matrix $A_{\vecc}\in \Z_q^{(k-1)m \times n}$ given by

\[
(A_\vecc)_{(k-1)(i-1)+\ell,j} = \left\{\begin{array}{ll}
1     &  \text{, if }j \in \{(e_i)_\ell\} \text{ and } \ell\in [k-1]\\
-1     & \text{, if }j=c_i \text{ and } \ell\in [k-1]\\
0       & \text{, otherwise}
\end{array}
\right.
\]

See <ref> for an example. We define the folded version of the $\IRMD$ problem below (note that all the arithmetic is over $\Z_q$):

Let $q,k,n,T\in\mathbb{N}$ and $\alpha\in(0,1/k)$ be parameters.
In the  game, there are $T$ players and a hidden $q$-coloring encoded by a random $\vecx^*\in\Z_q^n$. The $t$-th player has a pair of inputs $(A_{t,\vecc_t},\vecw_t)$ given as follows. $A_{t,\vecc_t}\in\Z_q^{\alpha(k-1)n\times n}$ gives a $\vecc_t$-centered folded encoding of a random hypermatching $M_t$ of size $\alpha n$, and $\vecw_t\in\Z_q^{\alpha(k-1)n}$ is a vector that can be generated from two different distributions:

* () $\vecw_t=A_{t,\vecc_t} \vecx^*$.

* () $\vecw_t$ is uniform over $\Z_q^{\alpha(k-1)n}$.

This is a one-way game where the $t$-th player can send a private message to the $(t+1)$-th player after receiving message from the previous player. The goal is to decide (by the $T$-th player) whether the $\{\vecw_t\}$ are coming from the  distribution or the  distribution. The advantage of a protocol is defined as
$$\left|\Pr_{(A_{t,c_t},\vecw_t)_{t\in T} \sim \yes}[\text{the }T\text{-th player outputs Yes}]-\Pr_{(A_{t,c_t},\vecw_t)_{t\in T} \sim \no}[\text{the }T\text{-th player outputs Yes}]\right|.$$

The main technical theorem of this paper is the following $\Omega(n)$ communication lower bound for $\IFRMD$.

For every $q,k\in\mathbb{N}$ and $\delta\in(0,1/2)$, there exists $\alpha_0\in(0,1/k)$ such that for every $\alpha\in(0,\alpha_0]$ and every $T\in\mathbb{N}$ and every $\delta\in(0,1)$, there exists $\tau\in(0,1)$ such that the following holds. When $n\in\mathbb{N}$ is large enough, any protocol for $\IFRMD$ with advantage $\delta$ requires $\tau n$ bits of communication.

The proof of <ref> is given in the beginning of <ref>.

We now prove a lemma establishing a reduction from $\IFRMD$ to $\IRMD$ that preserves the communication complexity. Note that by this lemma, <ref> will be an immediate corollary of <ref>.

Let $n,k,\alpha$ be the parameters. Suppose there exists a protocol for $\IRMD$ using at most $s$ bits communication with advantage $\delta$, then there exists a protocol for $\IFRMD$ using at most $s$ bits communication with advantage $\delta$.

Suppose we have an instance of $\IFRMD$ with input $(A_{t,\vecc_t},\vecw_t)$ to the $t$-th player. We show how to transform this into an instance of $\IRMD$. For each $t$, the $t$-th player performs the following computations on his/her input:

* Use $A_{t,\vecc_t}$ to compute the underlying hypermatching $M_t$ (by identifying the set of nonzero columns for each block of $k-1$ rows of $A_{t,\vecc_t}$) and compute the corresponding matrix $\Pi_t$.

* For each $i\in[\alpha n]$, sample $a_{t,i}\in\Z_q$ uniformly at random. Let $z_t\in\Z_q^{\alpha k n}$ be defined by $(z_t)_{(i-1)k+j}=(w_t)_{(i-1)k+j} + a_{t,i}$ for each $j=1,2,\dots,k-1$ and $z_{t,ik}=a_{t,i}$.

We claim that the inputs $(A_t, \vecz_t)$ correspond to an instance of $\IRMD$. It suffices to show that if $(\{(A_{t,\vecc_t},\vecw_t)\}_{t\in[T]},\vecx^*)$ follows the  (resp. ) distribution of $\IFRMD$, then $(\{(A_t,\vecz_t)\}_{t\in[T]},\vecx^*)$ follows the  (resp. ) distribution of $\IRMD$.

Let $m=\alpha n$. For each $t$, let $e^{(t)}_1, e^{(t)}_2, \dots, e^{(t)}_m$ be the hyperedges corresponding to $A_{t,\vecc_t}$ (in order), with $(e_i^{(t)})_k = c_{t,i}$.

We first focus on the  case. Then, note that for $j=1,2,\dots, k-1$, we have

\begin{align*}
(z_t)_{(i-1)k+j} &= (w_t)_{(i-1)k+j} + a_{t,i} = (x^*_{(e_i^{(t)})_j} + x^*_{c_{t,i}}) + a_{t,i} = x^*_{(e_i^{(t)})_j} + (x^*_{c_{t,i}} + a_{t,i}).
\end{align*}

\begin{align*}
(z_t)_{ik} = a_{t,i} = x^*_{c_{t,i}} + (x^*_{c_{t,i}} + a_{t,i}) = x^*_{(e_i^{(t)})_k} + (x^*_{c_{t,i}} + a_{t,i}).
\end{align*}

Thus, it follows that $\vecz_t = \Pi_t \vecx^* + \vecb_t$, where $\vecb_t = (\vecb_{t,1}, \dots, \vecb_{t,\alpha n})$ is given by $\vecb_{t,i} = (x^*_{c_{t,i}} + a_{t,i})\cdot\mathbf{1}_k$ where $\mathbf{1}_k$ is the all $1$ vector of length $k$.

Since $a_{t,i}$ is uniform over $\Z_q$, this takes care of the  case.

The  case is easier to see: $\Pi_t$ encodes a random $k$-hypermatching of size $\alpha n$ and $\vecz_t$ is uniform over $\Z_q^{\alpha kn}$.

For the sake of contradiction, suppose there exists a protocol for IRMD with advantage $\delta$ using fewer than $\tau n$ bits of communication. Then by <ref> there exists a protocol for IFRMD with advantage $\delta$ using fewer than $\tau n$ bits of communication, which contradicts <ref>. This completes the proof of <ref>.

In the following section we show how <ref> yields the claimed hardness of streaming problems. In the rest of this paper, we focus on the proof of <ref>, i.e., the linear communication lower bound for IFRMD.

§ STREAMING PROBLEMS AND HARDNESS

In this section we state and prove our main technical theorem establishing linear space lower bounds for the approximability of many CSPs.

Below we define the two crucial constants associated with a family $\cF$ which lay out the “trivial” approximability, and the inapproximability that we prove. In particular we define the notion of a width
$\omega(\cF) \in [1/q,1]$ for every family $\cF$. The notion of a wide family from <ref> corresponds to a family with maximum width, i.e., $\omega(\cF)=1$.

For a family $\cF$, we define its minimum value $\rho_{\min}(\cF)$ to be the infimum over all instances $\Psi$ of $\maxF$ of $\val_\Psi$. For $\vecb \in \Z_q^k$ and $f:\Z_q^k \to \{0,1\}$ we define $\vecb$-width of $f$, denoted $\omega_{\vecb}(f)$ to be the quantity $\frac{|\{a\in\Z_q\, |\, f(\vecb + a^k)=1\}|}q$. The width of $f$, denoted $\omega(f)$, is given by $\omega(f) = \max_{\vecb \in \Z_q^k} \{\omega_{\vecb}(f)\}$. Finally for a family $\cF$, we define its width to be $\omega(\cF) =\min_{f\in\cF} \{\omega(f)\}$. We say that a family $\cF$ is wide if $\omega(\cF) = 1$.

As described above $\rho_{\min}(\cF)$ may not even be computable given $\cF$, but as pointed out in [4] it is a computable function. Key to this assertion is the following equivalent definition of $\rho_{\min}(\cF)$ which follows from Definition 2.4 and Proposition 2.5 of [4].

For every $k,q, \cF \subseteq \{f:\Z_q^k \to \{0,1\}\}$ we have

$$\rho_{\min}(\cF) = \rho(\cF) := \min_{\cD_{\cF} \in \Delta(\cF)} \left\{ \max_{\cD \in \Delta([q])} \left\{ \Exp_{f \sim \cD_{\cF},  \veca \sim \cD^k} [ f(\veca) ]         \right\} \right\}.$$

We are now ready to prove the main theorem of the paper on the approximability of CSPs by applying <ref>.

For every $k,q, \cF \subseteq \{f:\Z_q^k \to \{0,1\}\}$ and every $\epsilon \in (0,1/10)$ we have the following: Every randomized single-pass streaming $\left(1+\epsilon\right)\cdot \frac{\rho(\cF)}{\omega(\cF)}$-approximation algorithm for $\maxF$ requires $\Omega(n)$ space.

Given $\cF$ and $\epsilon\in(0,1/10)$, we let $\alpha = \epsilon/(100k^2q)$ and $T$ be some large enough constant that only depends on $q,k,\cF,\epsilon,\alpha$.
Let $\ALG$ be a space $s$ algorithm distinguishing instances from the set $\{\Psi ~|~ \val_\Psi \geq (1-\epsilon/3)\omega(\cF)\}$ from instances from the set $\{\Psi ~|~ \val_\Psi \leq (1+\epsilon/3)\rho(\cF)\}$ with success probability at least $2/3$. We show how to use $\ALG$ to device an $s$-bit
communication protocol for $\IRMD = \IRMD_{\alpha,T}$ with advantage at least $1/6$.

For $f\in \cF$, let $\vecb_f \in \Z_q^k$ be a sequence maximizing $\omega_{\vecb_f}(f)$ and let $S_f = \{\vecb_f + a^k\, |\, a \in \Z_q\}$. Further let $\cD_\cF \in \Delta(\cF)$ be a distribution achieving the minimum in the equivalent definition of $\rho(\cF)$ from <ref>.
Let $\vecsigma = (\sigma_1,\ldots,\sigma_m)$ be an instance of $\IRMD$ with $T$ players, so that $m = T \alpha n$ and $\sigma_i = (\vecj(i), \vecz(i))$ where $\vecj(i) \in [n]^k$ is a sequence of $k$ distinct elements of $[n]$ and $\vecz(i) \in \Z_q^k$. For each $\sigma_i$ we either generate $0$ or $1$ constraint of $\maxF$ as follows: We sample $f(i)\sim \cD_\cF$ and output the constraint $(f(i),\vecj(i))$ if $\vecz(i) \in S_{f(i)}$ and output no constraint otherwise.
Applying this step independently to each $\sigma_i$ generates an instance $\Psi$ of $\maxF$ with $\tilde{m} \leq m$ constraints on $n$ variables. We make the following claims about $\Psi$.

* $\Pr_{\yes}[\tilde{m}>(1+\epsilon/10)\cdot q^{-(k-1)}\cdot m]=o(1)$ and $\Pr_{\no}[\tilde{m}<(1-\epsilon/10)\cdot q^{-(k-1)}\cdot m]=o(1)$, i.e., the number of constraints $\tilde{m}$ does not deviate (in the wrong direction) from its expectation $q^{-(k-1)}\cdot m$ with too high a  probability.

* If $\vecsigma$ is generated from the $\yes$ distribution with hidden vector $\vecx^*$ then with high probability the number of constraints of $\Psi$ satisfied by $\vecx^*$ is  at least $(\omega(\cF)-\varepsilon/10) \cdot q^{-(k-1)}\cdot m$. In particular, $\Pr_{\yes}[\val_\Psi\leq(1-\epsilon/3)\cdot\omega(\cF)]=o(1)$.

* If $\vecsigma$ is generated from the $\no$ distribution with hidden vector $\vecx^*$ then with high probability for every $\vecnu$ the number of constraints of $\Psi$ satisfied by $\vecnu$ is  at most $(\rho(\cF)+\varepsilon/10) \cdot q^{-(k-1)}\cdot m$. In particular, $\Pr_{\no}[\val_\Psi\geq(1+\epsilon/3)\cdot\rho(\cF)]=o(1)$.

With the above claims in hand, it is straightforward to convert $\ALG$ into an $O(s)$-bit communication protocol for $\IRMD$ with advantage at least $1/6$ — the $t$-th player gets the state of $\ALG$ after processing constraints corresponding to the first $t-1$ blocks from the $(t-1)$-th player; generates the constraints corresponding to the $t$-th block of the stream $\vecsigma$, and simulates $\ALG$ on this part of the stream corresponding to $\Psi$, and passes the resulting state on to the $(t+1)$-th player.
The $T$-th player outputs $1$ if $\ALG$ outputs $1$ and $0$ otherwise. It is straightforward to see that if $\ALG$ is correct on every input with probability $2/3$ and Claims (1)-(3) above hold, then the resulting communication protocol achieves advantage at least $1/3 - o(1) \geq 1/6$ on $\IRMD$. Finally, we invoke <ref> and conclude that $s=\Omega(n)$.

We thus turn to proving claims (1)-(3). Given $\sigma_1,\ldots,\sigma_m$ and $\vecnu \in \Z_q^n$, we create a collection of related variables as follows: For $i \in [m]$, let $X_i = 1$ if $\sigma_i$ results in a constraint and $0$ otherwise.  Further, let  $Y_i(\vecnu)=1$ if $X_i=1$ and the resulting constraint is satisfied by the assignment $\vecnu$. (Note all these are random variables depending on $\vecsigma$).
Below, we bound the expectations of the sums of these random variables in the  and  cases, and also argue that these variables are close to their expectations (or at least give bounds on deviating from the expectation in one direction). This will suffice to prove claims (1)-(3) and thus the theorem.

Proof of Claim (1).
We start with $\tilde{m} = \sum_{i=1}^m X_i$

in the  case: In this case $\Exp[X_i] = |S_f|/q^k = q^{-(k-1)}$ (note that $|S_f| = q$ for every $f$). Furthermore the $X_i$'s are independent since $\vecz(i)$'s are uniform and independent of each other. Thus $X$ is sharply concentrated around $q^{-(k-1)}\cdot m$ and we get that $\Pr_{\no}[\tilde{m} \not\in (1 \pm \epsilon/10)\cdot q^{-(k-1)}\cdot m] = o(1)$.

Turning to the  case, since $\vecz(i)$'s are no longer independent, the $X_i$'s are correlated. To enable the analysis, we define a vector $\vecx^*$ to be $\gamma$-good for $\gamma > 0$ if for every $\tau \in \Z_q$ we have $\Pr_{i\in[n]}[\vecx^*_i = \tau] \in (1\pm \gamma)(1/q)$. Note that for every constant $\gamma>0$, the probability that $\vecx^*$ is not $\gamma$-good is $o(1)$. Fix $\vecx^*$ that is $\gamma$-good. We claim that in this case,  $\Exp[X_i\, |\, X_{1:i-1}] \leq q^{-(k-1)} \cdot (1+\gamma+\alpha qk)^k$. To see this note that the effect of conditioning on $X_{1:i-1}$ only affects $X_i$ due to the fact that now
$\vecj(i)$ is chosen from a smaller set of variables and not all of $[n]$. Let $t\in[T]$ denote the block containing $i$ (i.e., $i \in ((t-1)\alpha n,t \alpha n]$).  Let $S$ denote the set of variables that do not participate in the edges $\vecj((t-1)\alpha n + 1),\ldots,\vecj(i-1)$. Note $|S| \geq (1 - k\alpha)n$ and so for every $\tau \in \Z_q$ we have $\Pr_{\ell \in S}[\vecx^*_\ell = \tau] \leq (1+\gamma+\alpha k q)/q$. We conclude that the probability $\Pr[\vecx^*|_{\vecj(i)} \in S_f\, |\, X_{1:i-1}] \leq |S_f|\cdot ((1+\gamma+\alpha k q)/q)^k = q^{-(k-1)} \cdot (1+\gamma+\alpha qk)^k$. Setting $\gamma = \epsilon/(100k)$ and
using $\alpha \leq \epsilon/(100k^2q)$, we conclude $\Exp[X_i\, |\, X_{1:i-1}] \leq q^{-(k-1)} \cdot (1+\epsilon/(50k))^k \leq q^{-(k-1)} \cdot (1+\epsilon/20)$. Applying <ref> we conclude that here again we get that $\Pr_{\yes}[\tilde{m} = \sum_i X_i > (1+\epsilon/10) q^{-(k-1)}m] = o(1)$.

Proof of Claim (2).
Now we analyze the number of satisfiable constraints of the resulting instance $\Psi$ in the  case, where we argue that $\vecx^*$ satisfies a large fraction of constraints with high probability. Again with probability $1-o(1)$ we have that $\vecx^*$ is $\gamma$-good. Now an argument similar to the one in the analysis of $X$ in the  case shows that for every $\vecb\in\Z_q^k$, $\Pr[\vecx^*|_{\vecj(i)} = \vecb\, |\, Y_{1:i-1}] \geq (1-\epsilon/50)\cdot q^{-k}$. Fix $f(i)$ and let $T = S_{f(i)} \cap f(i)^{-1}(1)$. Note by definition of $\omega(\cF)$ that $|T| \geq \omega(\cF)\cdot q$.
The event that the $i$-th constraint is satisfied by $\vecx^*$ is equivalent to the event that $\vecx^*_{\vecj(i)} \in T$ and the probability of this event, conditioned on $Y_{1:i-1}$ is at least $|T| \cdot (1-\epsilon/50)\cdot q^{-k} \geq (1-\epsilon/50) \cdot \omega(\cF) \cdot q^{-(k-1)}$. Using <ref> we conclude again that
$\Pr[Y(\vecx^*) = \sum_{i=1}^m Y_i(\vecx^*) \leq (1-\epsilon/10)\cdot \omega(\cF)\cdot q^{-(k-1)}\cdot m] = o(1)$. Combining this with the lower bound on $\tilde{m}$ from Claim (1) we conclude that $\Pr[\val_\Psi \leq (1-\epsilon/3)\cdot \omega(\cF)] = o(1)$.

Proof of Claim (3).
Finally we analyze the number of satisfiable constraints in the  case. Fix $\vecnu \in \Z_q^k$ and let $\cD\in\Delta(\Z_q)$ be the distribution obtained by sampling a uniformly random $\ell\in[n]$ and outputting $\vecnu_\ell$. By <ref> we have that $\Exp_{f \sim \cD_\cF, \vecb \sim \cD^k}[f(\vecb)] \leq \rho(\cF)$. We use this to prove that for every $i \in [m]$, $\Exp[Y_i(\vecnu)|Y_{1:i-1}(\vecnu)] \leq (1+\epsilon/50)\cdot \rho(\cF)\cdot q^{-(k-1)}$.

First, as in the proof for Claim (2) we have that the total variation distance between $\vecb \sim \cD^k$ and $\{\vecnu_{\vecj(i)}| Y_{1:i-1}(\vecnu)\}$ is at most
$k^2 \alpha$. (In particular, this is upper bounded by the probability that $k$ uniformly and independently chosen elements of $[n]$ either collide or fall in a set of size at most $k (\alpha n - 1)$.) We conclude that the probability that the $i$-th “potential constraint” (given by $(f(i),\vecj(i))$) is satisfied is at most $\rho(\cF) + k^2\alpha$. Next, note that the event $X_i = 1$ (i.e., the $i$-th constraint is chosen in $\Psi$) is independent of $Y_i(\vecnu)$ since in the  case $\vecz(i)\in \Z_q^k$ is uniform and independent of all other random variables. We conclude that $\Exp[Y_i(\vecnu)|Y_{1:i-1}(\vecnu)] \leq (1+\epsilon/50)\cdot \rho(\cF)\cdot q^{-(k-1)}$. Finally, we apply <ref> again to conclude that
$\Pr[Y(\vecnu) = \sum_{i=1}^m Y_i(\vecnu) > (1 + \epsilon/10)\cdot \rho(\cF)\cdot q^{-(k-1)}\cdot m] \leq c^{-m}$ where $c>1$ depends on $q,k,\cF,\alpha,\epsilon$ but not on $T$ or $n$. Thus by setting $T$ large enough, we can bound $c^{-m} \leq q^{-2n}$. This allows us to use the union bound to conclude that the probability that there exists $\vecnu \in \Z_q^n$ such that $Y(\vecnu) > (1+\epsilon/10)\cdot\rho(\cF)\cdot q^{-(k-1)}\cdot m$ is at most $q^{-n} = o(1)$. Combining with the lower bound on $\tilde{m}$ from Claim (1) we get that with probability $1 - o(1)$ we have $\val_{\Psi} \leq (1+\epsilon/3)\cdot\rho(\cF)$ in this case.

This concludes the proofs of the claims and thus the proof of <ref>.

<ref> follow immediately from <ref> as we show below.

The theorem follows from the fact that for a wide family $\omega(\cF) = 1$ and in this case <ref> asserts that a $\rho(\cF) + \epsilon$ approximation requires linear space.

The theorem follows from the fact that for every non-zero function $f$ we have $\omega(f) \geq 1/q$ and
so for every family $\cF$ also we have $\omega(\cF) \geq 1/q$. Thus <ref> asserts that a $\rho(\cF)\cdot q + \epsilon$ approximation requires linear space, where $\rho(\cF)$ approximation is trivial.

§.§ Some examples

We now give some examples illustrating the power of <ref>. Our first example is the familiar $q$-coloring problem.

Example 1 ($\textsf{Max-}q\textsf{Col}$).
Let $k=2$ and $q\geq2$. Let $\cF=\{f:\Z_q^2\to\{0,1\}\}$ where $f(u,v)=1$ if and only if $u \ne v$. The “Max $q$-Coloring” problem is defined to be  $\textsf{Max-}q\textsf{Col}=\textsf{Max-CSP}(\cF)$. It is easy to verify $\rho(\cF) = 1 - 1/q$ and $\omega(\cF) = 1$. We thus conclude by <ref> that $\textsf{Max-}q\textsf{Col}$ is approximation resistant.

Next we turn to the Unique Games Problem.

Example 2 ($\textsf{Max-}q\textsf{UG}$).
Let $k=2$ and $q\geq2$. Let $\cF=\{f:\Z_q^2\to\{0,1\}\, |\, f^{-1}(1)\text{ is a bijection}\}$. The “$q$-ary Unique Games” problem is defined to be  $\textsf{Max-}q\textsf{UG}=\textsf{Max-CSP}(\cF)$. We show below that $\rho(\cF)=1/q$. We also show that there exists $\cF' \subseteq \cF$ such that
$\rho(\cF') = 1/q$ and $\omega(\cF') = 1$. Applying <ref> to $\cF'$ we get that $1/q + \epsilon$ approximating $\textsf{Max-CSP}(\cF')$ requires linear space and the same holds for $\textsf{Max-}q\textsf{UG}=\textsf{Max-CSP}(\cF)$ by monotonicity.

We define the family $\cF'$ to be $\cF' = \{f_a | a \in \Z_q\}$ where $f_a(u,v) = 1$ if and only if $u=v+a$. Let $\cD = \textsf{Unif}(\Z_q)$. For every $f \in \cF$ we have that
$\Exp_{(u,v) \sim \cD^2}[f(u,v)] = 1/q$. So for every $\cD_\cF \in \Delta(\cF)$ we have $\Exp_{f \sim \cD_\cF} \Exp_{(u,v) \sim \cD^2}[f(u,v)] = 1/q$.
This proves $\rho(\cF),\rho(\cF') \geq 1/q$. To get the upper bound we let $\cD_\cF$ be uniform over $\cF'$. For every $(u,v) \in \Z_q^2$ we have $\Exp_{f \sim \cD_\cF} [f(u,v)] = 1/q$ and so for every distribution $\cD \in \Delta(\Z_q^k)$ (which is more than we need) we have $\Exp_{f \sim \cD_\cF} \Exp_{(u,v) \sim \cD}[f(u,v)] \leq 1/q$. This proves $\rho(\cF'),\rho(\cF) = 1/q$ (since $\cD_\cF$ is supported on $\cF'$).

Now turning to $\omega(\cF')$, note that for every $f_a \in \cF'$ we have $\{(b+a,b) | b \in \Z_q\} \subseteq f_a^{-1}(1)$. Thus $\omega(f_a) \geq \omega_{(a,0)}(f_a) = 1$. It follows that $\omega(\cF') = 1$.

Our third example talks about constraints that are general linear systems.

Example 3 ($\textsf{Max-Lin}_{k,r,q}$).
For $k\geq 2$ and prime $q$ and $0 \leq r < k$, we define $\textsf{Max-Lin}_{k,r,q} = \maxF$ for $\cF = \cF_{k,r,q} = \{f_{A,\vecb}:\Z_q^k\to\{0,1\} | A \in \Z_q^{r\times k},\vecb \in \Z_q^{k}\}$ where $f_{A,\vecb}(x) = 1$ if and only if $Ax = Ab$. (Thus constraints are systems of satisfiable linear equations with solutions of dimension at least $k-r$.)
Let $\cF'_{k,r,q} = \{f_{A.\vecb}\in \cF_{k,r,q} | A\cdot 1 = 0\}$.
It is easy to verify that for every $k,r,q$, $\rho(\cF'_{k,r,q}) \geq \rho(\cF_{k,r,q}) \geq q^{-r}$. By choosing $\cD_\cF'$ to be uniform over $f_{A,\vecb}$ with full rank matrices $A$ satisfying $A\cdot 1 = 0$, we get $\rho(\cF_{k,r,q}), \rho(\cF'_{k,r,q}) = q^{-r}$.  For $r < k$, we also get $\omega(\cF') = 1$ and thus, applying <ref> to $\cF'$ we get that $\textsf{Max-CSP}(\cF')$ is approximation-resistant. The same holds for $\textsf{Max-}q\textsf{UG}=\textsf{Max-CSP}(\cF)$ by monotonicity.[We believe this system is not approximation resistant for $r=k$. This is proved for $q=2$ in <cit.>. The case of general $q$ may not have been explicitly resolved in previous work.]

Finally we mention one more problem. This problem arises in the work of Singer, Sudan and Velusamy [14] who use it to show the approximation resistance of the “maximum acyclic subgraph” problem to $o(\sqrt{n})$ space algorithms. We suspect the improved space lower bound should improve their work to rule out $o(n)$ space algorithms.

Example 4 ($\textsf{Max-Less-Than}_{q}$).
For $k=2$ and $q\geq 2$ we define $\cF = \{<_q\}$ where $<_q : \Z_q^2 \to \{0,1\}$ is given by $<_q(u,v) = 1$ if and only if $u < v$.
It is possible to show $\rho(\cF) = \frac12(1-1/q)$. Also $\omega_{(0,1)}(<_q) = 1-1/q$ and this can be used to show that $\omega(\cF) = 1 - 1/q$. By <ref> it follows that $1/2+\epsilon$-approximating $\maxF$ requires linear space.

§ LOWER BOUND ON THE COMMUNICATION COMPLEXITY

In this section we prove a linear lower bound on the communication complexity of  (<ref>). Our proof is via a hybrid argument which starts with all players receiving inputs from the  distribution, and switching the players' input distribution one at a time starting with Player 1 to the  distribution.
We state a key “hybrid lemma” (<ref>) which asserts that any one step of switching does not alter the distribution of the message output by the switched player.
To state our lemma we recall some notations and set up a few new ones. Let $\alpha,n,k,q,T,m=\alpha n\in\N$ denote the usual parameters of . Recall that the player $t$ gets as input a matrix $A_{t,\vecc_t}\in\Z_q^{(k-1)m\times n}$ corresponding to a $k$-uniform hypermatching $M_t$ consisting of $m$ hyperedges folded over the center vector $\vecc_t$ and a vector $\vecw_t \in \Z_q^{(k-1)m}$. For notational convenience, we will separate the input $A_{t,c_t}$ into a matrix $A_t \in \Z_q^{(k-1)m\times n}$ and the center $\vecc_t$. For a sequence of objects $O_1,O_2,\dots,O_T$, we denote $O_{1:t}=\{O_1,O_2,\dots,O_t\}$ for every $t\in[T]$. With this notation we have that the message $S_t$ sent by the $t$-th player is a function of $A_{1:t},\vecc_{1:t},\vecw_t$ and $S_{1:t-1}$.[Note that even though the $t$-th player does not have access to $A_{1:t-1},\vecc_{1:t-1}$, and $S_{1:t-2}$, allowing them to see these only makes our lower bound stronger.] Next, note that by Yao's principle [16], we may assume that the messages sent by the players in $\IFRMD$ are all deterministic.
Namely, a protocol for $\IFRMD$ can be specified by deterministic message functions $r_1,r_2,\dots,r_T$ so that $S_t=r_t(A_{1:t},\vecc_{1:t},S_{1:t-1},\vecw_t)$ denotes the message sent by the $t$-th player. The communication complexity of a protocol is defined as the largest output length of $r_t$.
When $(A_{1:T},\vecc_{1:T},\vecw_{1:T})$ is drawn from the  distribution (resp. the  distribution), we denote $S_{1:T}^Y$ (resp. $S_{1:T}^N$) to be the resulting messages. Without loss of generality $S_T$ is just a bit “`Yes/No” indicating the output of the protocol. Thus, to prove <ref> we need to show that $S^Y_T$ and $S^N_T$ are close in total variation distance. For the induction we prove the much stronger statement that  $(A_{1:T},\vecc_{1:T},S_{1:T}^Y)$ and $(A_{1:T},\vecc_{1:T},S_{1:T}^N)$ are close in total variation distance, i.e.,

\[
\|(A_{1:T},\vecc_{1:T},S_{1:T}^Y)-(A_{1:T},\vecc_{1:T},S_{1:T}^N)\|_{tvd}\leq\delta \, .
\]

The following lemma provides the key step in this analysis. Roughly it says that if the first $t-1$ players's inputs are according to the  distribution then the $t$-th player's output on the  input is typically distributed very similarly to the output on the  distribution (even conditioned on all previously announced hypermatchings, centers and messages). Formally, the lemma identifies a sequence of events $\cE_1\supset\cE_2\supset\cdots\supset\cE_T$ such that (i) $\cE_t$ enforces a “typicality” restriction on the messages and inputs that the $t$-th player receives and (ii) if the messages and input received by the $t$-th player are typical then the player cannot distinguish whether its input is sampled from the  distribution or the  distribution (assuming all previous players' inputs were from the  distribution).

For every $q,k\in\N$, there exists $\alpha_0\in(0,1/k)$ such that for every $\alpha\in(0,\alpha_0]$, $T\in\N$, and $\delta\in(0,1)$, there exist $n_0\in\N$, and $\tau\in(0,1)$ such that for every $n\geq n_0$ the following holds:

Let $\Pi=(r_1,\dots,r_T)$ be a deterministic protocol for $\IFRMD$ where each message function $r_t$ outputs a message of at most $\tau n$ bits.
Let $x\sim\Unif(\Z_q^n)$ and let $M_1,\dots,M_T$ be independent random hypermatching of size $\alpha n$ over $[n]$. Let $(A_t,\vecc_t)$ be an independent random folded encoding of $M_t$ for all $t\in[T]$. Let $S_t^Y$ and $S_t^N$ be the Yes and No message of the $t$-th player defined previously for message function $r_t$ for all $t\in[T]$.
Then there exists a sequence of events $\cE_1\supset\cE_2\supset\cdots\supset\cE_T$ such that (i) $\cE_t$ only depends on $(A_{1:t},\vecc_{1:t})$ and $S^Y_{1:t-1}$, (ii) $\Pr[\cE_1]\geq1-\delta/T$, (iii) $\Pr[\overline{\cE}_{t}\, |\, \cE_{t-1}]\leq\delta/T$ for all $t=2,3,\dots,T$, and (iv) for every fixed $(A_{1:t},\vecc_{1:t})$ and $S^Y_{1:t-1}$ satisfying $\cE_t$, one has

\begin{equation}\label{eq:hybrid}
\|S^Y_t-r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},U_t)\|_{tvd}\leq\delta/T,
\end{equation}

where $U_t\sim\Unif(\Z_q^{(k-1)\alpha n})$.

The proof of <ref> will be provided in <ref>.
<ref> follows almost immediately from <ref> as shown in <ref>. In the rest of this section and the following sections we prove <ref>. Here we give an overview of this part of the proof.

The general idea behind the proof of <ref> is to argue that information about $\vecx^*$ “leaked” by the messages of the first $t-1$ players (i.e., $S_{1:t-1}$) is not sufficient for the $t$-th player to distinguish between the case where $\vecw_t = A_{t,c_t} \vecx^*$ (the  case) and the case where $\vecw_t$ is uniform. The earlier proofs of this type (in particular as in [11]) simply counted the total information gleaned about $\vecx^*$ which is bounded by the total communication. Such proofs are inherently limited to achieving only a $\sqrt{n}$ lower bound. To go further, as in [10], one needs to argue about the structure of the information learned about $\vecx^*$, and in particular note that no player sees $\vecx^*$ directly, and the $t'$-th player only sees $A_{t',c_{t'}}\cdot \vecx^*$. (In particular no coordinate of $\vecx^*$ is revealed directly, though the sum of many pairs of coordinates are directly revealed.) Thus the information about $\vecx^*$ comes from a “reduced space” and we would like to capture and exploit the structural restriction imposed by this restriction. Information-theoretic tools seem to fail to capture this restriction and the key to the work of [10] is to give a Fourier analytic condition, that they call “boundedness”, that captures this restriction.

The boundedness condition applies to what we call the “posterior distribution” of $\vecx^*$, i.e., the distribution of $\vecx^*$ conditioned on the first $t$ messages. This distribution turns out to be the uniform distribution over a set $B_t \subseteq \Z_q^n$ (see <ref>). The boundedness condition places restrictions on the Fourier spectrum of the indicator function of this set. (See <ref>.) To use this condition we need three ingredients elaborated below, which we abstract as lemma statements in this section and prove in later section. Given these three lemmas the proof of <ref> follows and is given in <ref>.

The first ingredient we need is that boundedness of $B_{t-1}$ does imply that the $t$-th player is unable to distinguish between its input being from the  distribution or the  distribution. This is stated as <ref>. Next we need to show that given information about $A_{t,c_t}\vecx^*$, the posterior distribution of $\vecx^*$ is indeed bounded, and we assert this in <ref>. Note that this also serves as the base case of our induction. Finally we argue that if $B_{t-1}$ is bounded, then for most matchings $A_{t}$ (and every center $\vecc_t$ of $A_t$) the resulting set $B_t$ is bounded. This is asserted in <ref>. See also <ref> for a pictorial overview for the proof structure of <ref>.

In the rest of this section, after showing that <ref> implies <ref> in <ref>, we introduce the posterior sets and discuss their basic properties in <ref>, we introduce boundedness and state the three lemmas above in <ref>, and finally conclude with the proof of <ref> in <ref>.

§.§ Proof of Theorem <ref>

We now show how the lemma suffices to prove <ref>. The proof is analogous to the proof of Lemma 6.3 in [10]. We remark that the lemma is not immediate and effectively depends on the fact that players can jointly sample from the  distribution on their own. (Note the players can't jointly sample from the $\yes$ distribution since these samples are correlated by the hidden vector $\vecx^*$. So the proof is inherently asymmetric visavis the treatment of the  and  distributions.)

For the sake of contradiction, assume that there exists a protocol $\Pi=(r_1,\dots,r_T)$ that solves IFRMD with advantage more than $\delta$ and less than $\tau n$ bits of communication for some $n\geq n_0$. In what follows, we will show that $\|(A_{1:T},\vecc_{1:T},S^Y_{1:T})-(A_{1:T},\vecc_{1:T},S^N_{1:T})\|_{tvd}\leq\delta$, which implies that the advantage of the protocol cannot be greater than $\delta$, hence producing a contradiction.

For every $q,k\in\N$, we set $\alpha_0\in(0,1/k)$ and $\tau_0\in(0,1)$ as in <ref>.
For every $\alpha\in(0,\alpha_0]$, $T\in\N$, and $\delta' =\delta/2$, we set $n_0\in\N$ and $\tau\in(0,1)$ as in <ref>.

Let $\cE_1 \supset \cE_2 \supset \cdots \supset \cE_T$ be the sequence of events guaranteed by <ref> such that $\Pr\left[\overline{\cE_t}\, |\, \cE_{t-1}\right]\leq\delta'/T$ for $t=2,3\dots, T$. Note that by the properties of these events, with probability at least $1-\delta'$, we have $\|S^Y_t-r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},U_t)\|_{tvd}\leq\delta'/T$ for all $t\in[T]$. We use $\|\cdot\|_{tvd,\cE_t}$ to denote the total variation distance of distributions conditioned on $\cE_t$. We inductively show that for every $t\in[T]$,

\[
\|(A_{1:t},\vecc_{1:t},S^Y_{1:t})-(A_{1:t},\vecc_{1:t},S^N_{1:t})\|_{tvd,\cE_t}\leq  \frac{t\delta'}{T}. \tag{Induction hypothesis}
\]

First, we prove the base case $t=1$. Recalling that $S_0^Y=S_0^N$, we have

\begin{align*}
\|(A_1,\vecc_1,S_1^Y)-(A_1,\vecc_1,S_1^N)\|_{tvd,\cE_1}&=\|(A_1,\vecc_1,S_1^Y)-(A_1,\vecc_1,r_1(M_1,\vecc_1,S_0^N,U_1))\|_{tvd,\cE_1}\\
&=\|(A_1,\vecc_1,S_1^Y)-(A_1,\vecc_1,r_1(M_1,\vecc_1,S_0^Y,U_1))\|_{tvd,\cE_1} \, .
\end{align*}

Observe that for every fixed $A_1,\vecc_1$ and $S^Y_0$ satisfying $\cE_1$, we have $\|S_1^Y-r_1(M_1,\vecc_1,S_0^Y,U_1)\|_{tvd}\le \frac{\delta'}{T}$, where the randomness is over $S_1^Y$ and $U_1$. It follows from <ref> that
\[\|(A_1,\vecc_1,S_1^Y)-(A_1,\vecc_1,r_1(M_1,\vecc_1,S_0^Y,U_1))\|_{tvd,\cE_1} \le \frac{\delta'}{T},\]

which completes the base case.

Next, we tackle the induction step. For every $t=2,\dots,T$, we have

\begin{multline*}
\| (A_{1:t},\vecc_{1:t},S^Y_{1:t})-(A_{1:t},\vecc_{1:t},S^N_{1:t})\|_{tvd,\cE_t} \\% \le \|(A_{1:t},\vecc_{1:t},S_{1:t}^Y)-(A_{1:t},\vecc_{1:t},S_{1:t-1}^Y,r_t(A_{1:t},\vecc_{1:t},S^Y_{t-1},U_t))\|_{tvd,\cE_t}\\
= \|(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},r_t(A_{1:t},\vecc_{1:t},S^Y_{t-1},A_{t ,\vecc_t} \vecx^*))-(A_{1:t},\vecc_{1:t},S^N_{1:t-1},r_t(A_{1:t},\vecc_{1:t},S^N_{t-1},U_t))\|_{tvd,\cE_t}\, .
\end{multline*}

Let us define $Q_{t-1}^Y = (A_{1:t-1},\vecc_{1:t-1},S^Y_{1:t-1})$  and $Q_{t-1}^N = (A_{1:t-1},\vecc_{1:t-1},S^N_{1:t-1})$.
Then, we can rewrite the above expression for total variation distance in terms of the new notation as follows:

\begin{multline}\label{eqn:tvd_substitution}
\|(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},r_t(A_{1:t},\vecc_{1:t},S^Y_{t-1},A_{t ,\vecc_t} \vecx^*))-(A_{1:t},\vecc_{1:t},S^N_{1:t-1},r_t(A_{1:t},\vecc_{1:t},S^N_{t-1},U_t))\|_{tvd,\cE_t} \\
= \|(Q_{t-1}^Y,A_t,\vecc_t,r_t((Q_{t-1}^Y,A_t,\vecc_t,A_{t ,\vecc_t} \vecx^*))-(Q_{t-1}^N,A_t,\vecc_t,r_t(Q_{t-1}^N,A_t,\vecc_t,U_t))\|_{tvd,\cE_t} \, .
\end{multline}

We now apply <ref> to <ref>. Applying this lemma with $X^1 = Q_{t-1}^Y$, $X^2 = Q_{t-1}^N$, $Z^1=(A_t,\vecc_t,A_{t ,\vecc_t} \vecx^*)$, $Z^2=((A_t,\vecc_t,U_t))$, and $f$ as the function that maps the tuple $(X,(B,C))$ to $(B,r_t(X,B,C))$, we get

\begin{align}\label{eqn:conditionalTVD}
&\|(Q_{t-1}^Y,A_t,\vecc_t,r_t(Q_{t-1}^Y,A_t,\vecc_t,A_{t ,\vecc_t} \vecx^*))-(Q_{t-1}^N,A_t,\vecc_t,r_t(Q_{t-1}^N,A_t,\vecc_t,U_t))\|_{tvd,\cE_t} \nonumber \\
\le\ &\|Q_{t-1}^Y- Q_{t-1}^N\|_{tvd,\cE_t} + \| (Q_{t-1}^Y,A_t,\vecc_t,r_t(Q_{t-1}^Y,A_t,\vecc_t,A_{t ,\vecc_t} \vecx^*))-(Q_{t-1}^Y,A_t,\vecc_t,r_t(Q_{t-1}^Y,A_t,\vecc_t,U_t))\|_{tvd,\cE_t} \nonumber \\
=\ &\|Q_{t-1}^Y- Q_{t-1}^N\|_{tvd,\cE_{t-1}} +  \| (Q_{t-1}^Y,A_t,\vecc_t,r_t(Q_{t-1}^Y,A_t,\vecc_t,A_{t ,\vecc_t} \vecx^*))-(Q_{t-1}^Y,A_t,\vecc_t,r_t(Q_{t-1}^Y,A_t,\vecc_t,U_t))\|_{tvd,\cE_t} \, ,
\end{align}

where the last equality follows from the fact that $\cE_t \subset \cE_{t-1}$ and condition (i) of <ref> which states that $\cE_{t-1}$ only depends on $(A_{1:t-1},\vecc_{1:t-1})$ and $S^Y_{1:t-2}$.

Now, by applying the induction hypothesis, we have that
\begin{equation}\label{eqn:induction}\|Q_{t-1}^Y- Q_{t-1}^N\|_{tvd,\cE_{t-1}} \le  \frac{(t-1)\delta'}{T}.
\end{equation}

Next, we bound the second term on the right hand side of (<ref>), i.e.,

\[\| (Q_{t-1}^Y,A_t,\vecc_t,r_t(Q_{t-1}^Y,A_t,\vecc_t,A_{t ,\vecc_t} \vecx^*))-(Q_{t-1}^Y,A_t,\vecc_t,r_t(Q_{t-1}^Y,A_t,\vecc_t,U_t))\|_{tvd,\cE_t},\]

by applying condition (iv) from <ref>. According to this condition, for every fixed $(A_{1:t},\vecc_{1:t})$ and $S^Y_{1:t-1}$ satisfying $\cE_t$, we have

\begin{equation*}
\|r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},A_{t ,\vecc_t} \vecx^*)-r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},U_t)\|_{tvd}\leq\frac{\delta'}{T},
\end{equation*}

where $U_t\sim\Unif(\Z_q^{(k-1)\alpha n})$. Thus, by <ref>, it follows that
\begin{equation}\label{eqn:tvd}\| (Q_{t-1}^Y,A_t,\vecc_t,r_t(Q_{t-1}^Y,A_t,\vecc_t,A_{t ,\vecc_t} \vecx^*))-(Q_{t-1}^Y,A_t,\vecc_t,r_t(Q_{t-1}^Y,A_t,\vecc_t,U_t))\|_{tvd,\cE_t} \le \frac{\delta'}{T}\, .\end{equation}

Combining <ref>, we have

\[
\|(A_{1:t},\vecc_{1:t},S^Y_{1:t})-(A_{1:t},\vecc_{1:t},S^N_{1:t})\|_{tvd,\cE_t}\le \frac{\delta't}{T},
\]

which completes the induction.

Substituting $t=T$, we conclude that
\[\|(A_{1:T},\vecc_{1:T},S^Y_{1:T})-(A_{1:T},\vecc_{1:T},S^N_{1:T})\|_{tvd,\cE_T}\le \delta'.
\]

Finally, by removing the conditioning on $\cE_T$, we have

\begin{align*}
|(A_{1:T},\vecc_{1:T},S^Y_{1:T})-(A_{1:T},\vecc_{1:T},S^N_{1:T})\|_{tvd} &\le |(A_{1:T},\vecc_{1:T},S^Y_{1:T})-(A_{1:T},\vecc_{1:T},S^N_{1:T})\|_{tvd,\cE_T} + \Pr[\overline{\cE_T}]\\
&\le \delta'+\delta' \leq \delta.
\end{align*}

This implies that $\Pi$ cannot have advantage more than $\delta$, which contradicts the assumptions of the theorem statement. Therefore, we conclude that any protocol for $\IFRMD$ with advantage $\delta$ requires $\tau n$ bits of communication, as desired.

§.§ Posterior sets and functions

The main challenge in proving <ref> lies in the condition (iv), i.e., requiring the closeness of the Yes message (i.e., $S^Y_t=r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},A_{t,\vecc_t}\vecx^*)$) and the hybrid No message (i.e., $r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},U_t)$).
Intuitively, if $\vecx^*\sim\Unif(\Z_q^n)$ and is independent of the other arguments, then $A_{t,\vecc_t}\vecx^*$ is uniformly distributed over $\Z_q^{(k-1)\alpha n}$ and hence $S^Y_t$ follows the same distribution as $r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},U_t)$. However, $\vecx^*$ is correlated[In particular, $\vecx^*$ has to be consistent with the previous messages $S^Y_{1:t-1}$.] with the previous messages $S^Y_{1:t-1}$ so the above ideal situation would not happen in general. Nevertheless, we are able to analyze the conditional distribution of $A_{t,\vecc_t}\vecx^*$ on the previous messages by explicitly characterizing the posterior distribution of $\vecx^*$ after receiving the messages from the first $t-1$ players. That is, the conditional distribution of $A_{t,\vecc_t}\vecx^*$ can be described by first sampling $\vecx^*$ from the posterior distribution and then applying $A_{t,\vecc_t}$.

For every fixed $A_{1:t},\vecc_{1:t}$ and $S_{1:t}$, we would like to identify a distribution $\cD_t$ over $\Z_q^n$ such that $\cD_t$ is the conditional distribution of $\vecx^*$ given messages $S_{1:t}$. Note that by the choice of the No case, the conditional distribution of $\vecx^*$ given messages $S_{1:t}$ is simply the uniform distribution over $\Z_q^n$. Thus, we only need to worry about the Yes case.

Under the setting described above, for each $t$ and fixed $A_{1:t}$, $\vecc_{1:t}$, and $S_{1:t}$, define

* (Reduced posterior set) $B_{r,t}\subseteq\Z_q^{(k-1)m}$ be the set of possible values of $z_t=A_{t,\vecc_t}\vecx$ that leads to message $S_t$; Note that $B_{r,t}$ should be thought of as a function on $A_t$, $\vecc_t$, and $S_t$ in the sense that $B_{r,t}=g_t^{-1}(S_t)$ where $g_t(\cdot)=r_t(A_{1:t},\vecc_{1:t},S_{1:t-1},\cdot)$. Let $q$ be the indicator function of $B_{r,t}$.

* (Posterior set and function) Let

\[
B_t := \{\vecx\in\Z_q^n\, |\, A_{t,\vecc_t}\vecx\in B_{r,t}\} \, .
\]

Also, let $\mathbf{1}_{B_t}:\Z_q^n\to\{0,1\}$ be the indicator function of $B_t$.

* (Aggregated posterior set and function) Let

\[
B_{1:t}:=\{\vecx\in\Z_q^n\, |\, A_{t',\vecc_{t'}}\vecx\in B_{r,t'},\ \forall t'=1,\dots,t\}=\bigcap_{t'=1}^tB_{t'} \, .
\]

Also, let $\mathbf{1}_{B_{1:t}}:\Z_q^n\to\{0,1\}$ be the indicator function of $B_{1:t}$. Namely, $\mathbf{1}_{B_{1:t}}=\prod_{t'=1}^t\mathbf{1}_{B_{t'}}$.

Now, we show that $\one_{B_{1:t}}$ captures the posterior distribution (i.e., the conditional distribution) of $\vecx$ given messages $S_1, S_2, \dots, S_t$:

For every $t\in[T]$, the conditional distribution of $\vecx$ given messages $S_1,S_2,\dots,S_{t}$ is exactly given by $\one_{B_{1:t}}(\vecx)/\|\one_{B_{1:t}}\|_1$.
In particular, for fixed $A_{1:t}$, $\vecc_{1:t}$, and $S_{1:t-1}^Y$, we have $S^Y_t= r_t(A_{1:t},\vecc_{1:t},S_{1:t-1}^Y,A_{t,\vecc_t}\vecx^*)$, where $\vecx^*\sim\Unif(B_{1:t})$.

Wlog, let us focus on the case of $t=T$. The proof is done by some direct manipulations of Bayes rule.
By definition, the conditional probability of $\vecx$  given messages $S_1,S_2,\dots,S_T$ would be

\begin{align*}
&\Pr_{\vecx^*,A_{1:T},\vecc_{1:T}}\left[\vecx^*=\vecx\, \mid\, A_{t,\vecc_t}\vecx^*\in B_{r,t}\ \forall t\in[T]\right]\\
=\, &\frac{\Pr_{\vecx^*,A_{1:T},\vecc_{1:T}}\left[\vecx^*=\vecx\wedge A_{t,\vecc_t}\vecx^*\in B_{r,t}\ \forall t\in[T]\right]}{\Pr_{\vecx^*,A_{1:T},\vecc_{1:T}}\left[A_{t,\vecc_t}\vecx^*\in B_{r,t}\ \forall t\in[T]\right]}\\
=\, &\frac{\Pr_{\vecx^*,A_{1:T},\vecc_{1:T}}\left[A_{t,\vecc_t}\vecx^*\in B_{r,t}\ \forall t\in[T]\, \mid\, \vecx^*=\vecx\right]\cdot\Pr_{\vecx^*}[\vecx^*=\vecx]}{\Pr_{\vecx^*,A_{1:T},\vecc_{1:T}}\left[A_{t,\vecc_t}\vecx^*\in B_{r,t}\ \forall t\in[T]\right]}\\
=\, &\frac{\Pr_{\vecx^*}[\vecx^*=\vecx]}{\Pr_{\vecx^*,A_{1:T},\vecc_{1:T}}\left[A_{t,\vecc_t}\vecx^*\in B_{r,t}\ \forall t\in[T]\right]}\cdot\prod_{t=1}^T\Pr_{\vecx^*,A_t,\vecc_t}\left[A_{t,\vecc_t}\vecx^*\in B_{r,t}\, \mid\, \vecx^*=\vecx\right] \\
=\, &\frac{q^{-n}}{\Pr_{\vecx^*,A_{1:T},\vecc_{1:T}}\left[A_{t,\vecc_t}\vecx^*\in B_{r,t}\ \forall t\in[T]\right]} \cdot \prod_{t=1}^T\Pr_{A_t,\vecc_t}\left[A_{t,\vecc_t}\vecx\in B_{r,t} \right].
\end{align*}

As the above quantity is proportional to $\mathbf{1}_{B_{1:T}}(\vecx)$, we conclude that the conditional probability of $\vecx$  given messages $S_1,S_2,\dots,S_T$ is given by $\mathbf{1}_{B_{1:T}}(\vecx)/\|\mathbf{1}_{B_{1:T}}\|_1$.

Next, by definition we have $S^Y_T=r_T(A_{1:T},\vecc_{1:T},S_{1:T-1}^Y,A_{t,\vecc_T}\vecx^*)$ where $\vecx^*\sim\Unif(\Z_q^n)$. Thus, the conditional distribution of $S^Y_T$ on $A_{1:T}$, $\vecc_{1:T}$, and $S_{1:T-1}^Y$ is

\begin{align*}
&\Pr[S^Y_T=S\, |\, A_{1:T},\vecc_{1:T},S_{1:T-1}^Y] = \frac{\Pr[S^Y_T=S,A_{1:T},\vecc_{1:T},S_{1:T-1}^Y]}{\Pr[A_{1:T},\vecc_{1:T},S_{1:T-1}^Y]}\\
=\ &\frac{\Pr_{\vecx^*\sim\Unif(\Z_q^n)}[S=r_T(A_{1:T},\vecc_{1:T},S_{1:T-1}^Y,A_{t,\vecc_T}\vecx^*),A_{1:T},\vecc_{1:T},S_{t}^Y=r_t(A_{1:t},\vecc_{1:t},S_{1:t-1}^Y,A_{t,\vecc_t}\vecx^*)\ \forall t\in[T-1]]}{\Pr[A_{1:T},\vecc_{1:T},S_{1:T-1}^Y]}\\
=\ &\frac{\Pr_{\vecx^*\sim\Unif(\Z_q^n)}[S=r_T(A_{1:T},\vecc_{1:T},S_{1:T-1}^Y,A_{t,\vecc_T}\vecx^*),A_{1:T},\vecc_{1:T},\vecx^*\in B_{1:T}]}{\Pr[A_{1:T},\vecc_{1:T},S_{1:T-1}^Y]} \, .
\end{align*}

Namely, $S^Y_t=r_t(A_{1:t},\vecc_{1:t},S_{1:t-1}^Y,A_{t,\vecc_t}\vecx^*)$, where $\vecx^*\sim\Unif(B_{1:t})$.

Note that we have a characterization of the posterior distribution of $\vecx^*$, the following corollary shows that <ref> (i.e., the condition (iv) of <ref>) can be simplified to bounding the total variation distance between the posterior distribution and the uniform distribution.

Let $r_t,S^Y_{1:t-1},A_{1:t},\vecc_{1:t},B_{1:t},U_t$ be defined as before, we have

\[
\|r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},A_{t,\vecc_t}\vecx^*)-r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},U_t)\|_{tvd}\leq\|(A_{t,\vecc_t}\vecx^*)-U_t\|_{tvd}
\]

where $\vecx^*\sim\Unif(B_{1:t})$.

By <ref>, we have

\[
\]

where $\vecx^*\sim\Unif(B_{1:t})$. Note that when we fix $A_{1:t}$, $\vecc_{1:t}$, and $S^Y_{1:t-1}$ (hence $B_{1:t}$ is also fixed), by data processing inequality (see item 2 of <ref>) we have

\[
\|r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},A_{t,\vecc_t}\vecx^*)-r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},U_t)\|_{tvd}\leq\|(A_{t,\vecc_t}\vecx^*)-U_t\|_{tvd} \, .
\]

Namely, <ref> (i.e., the condition (iv) of <ref>) can be replaced with $\|(A_{t,\vecc_t}\vecx^*)-U_t\|_{tvd}\leq\gamma/T$, i.e., after applying a random folded hypermatching matrix $A_{t,\vecc_t}$ to the posterior distribution $\Unif(B_{1:t})$, the distribution of the resulting string is close to the uniform distribution $\Unif(\Z_q^{(k-1)\alpha n})$.

Finally, the following lemma shows that when the amount of communication is small, the posterior set is large with high probability.

Let $\Pi=(r_1,\dots,r_T)$ be a deterministic protocol for $\IFRMD$ where each message function $r_t$ outputs a message of length at most $s$ bits for some $1\leq s\leq n$. Let $B_t$ be the posterior set defined in <ref> for every $t\in[T]$. For every $\delta\in(0,1)$ and $t\in[T]$, we have $|B_t|\geq \delta\cdot q^{n-s}$ with probability at least $1-\delta$ over the randomness of $\vecx\in\Z_q^n$.

Fix a hypermatching $M$ and centers $\vecc$, the $t$-th message function induces a partition $P_1\cup P_2\cup\cdots\cup P_{2^{s}}$ of $\Z_q^n$. For each $\vecx\in\Z_q^n$, we define $P(\vecx)$ to be the part that contains $\vecx$, i.e, if $\vecx\in P_i$, then $ P(\vecx)=P_i$. Note that

\[
\Exp_{\vecx\in\Z_q^n}\left[\frac{1}{|P(\vecx)|}\right] = \sum_{i=1}^{2^s}\frac{\Pr_{\vecx\in\Z_q^n}[\vecx\in P_i]}{|P_i|} = \sum_{i=1}^{2^{s}}\frac{|P_i|\cdot q^{-n}}{|P_i|}=\frac{2^{s}}{q^n}\leq q^{s-n} \, .
\]

By Markov's inequality, we have $|P(\vecx)|<\delta\cdot q^{n-s}$ with probability at most $\delta$ as desired.

§.§ Fourier analytic conditions

In this subsection, we define and analyze Fourier-analytic properties of the posterior set $B$ and show that these properties are sufficient for the condition (iv) (i.e., <ref>) of <ref>.

Recall that given a matching $M = (e_1,\ldots,e_m)$ and centers $\vecc = (c_1,\ldots,c_m)$, $A_\vecc$ is the $\vecc$-centered folded encoding of $M$. We are going to define three properties for sets $B$ in $\Z_q^n$.
First, we say a set $B\subseteq\Z_q^n$ is $(M,\vecc)$-restricted if $B$ is restricted to a union of shifted null spaces of $A_{\vecc}$.

[Restricted set]definitionrestricted
Let $M$ be a $k$-hypermatching of size $m$ and $\vecc$ be centers. We say a set $B\subseteq\Z_q^n$ is $(M,\vecc)$-restricted if there exists a (“reduced”) set $B_r \subseteq \Z_q^{(k-1)m}$ such that $B = \{\vecx \in \Z_q^n \, |\, A_{\vecc}\vecx \in B_r\}$.

Next, we say a set $B$ is bounded if the Fourier spectrum of the indicator function $\mathbf{1}_B$ can be properly bounded in an appropriate range of the spectrum. This is analogous to Definition 4.3 in [10]. First, we introduce some notation:

\begin{equation}
U_{C,s}(h) := \begin{cases}
1, \quad &h = 0 \\
\left(\frac{C\sqrt{s n}}{h}\right)^{h/2},     &1\leq h\leq s \\
\left(\frac{2q^2e^2 n}{h}\right)^{h/2},     &h>s.
\end{cases}. \label{eq:ucs-def}
\end{equation}

[Bounded set]definitionbounded
Let $n,q\in\mathbb{N}$, $0\leq s\leq n$, $C>0$, and $B\subset\Z_q^n$. We say $B$ (as well as its indicator function $\mathbf{1}_B$) is $(C,s)$-bounded if, for every $h\in[s]$,

\begin{equation}\label{eq:boundedness}
\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu\|_0=h}}\frac{q^{n}}{|B|}\left|\widehat{\mathbf{1}_B}(\vecu)\right|\leq U_{C,s}(h).
\end{equation}

As we keep track of posterior sets that are inductively refined, we will need the entire Fourier spectrum of the corresponding indicator functions to be bounded from above by the function $U_{C,s}$ (for appropriate $C,s > 0$), which is defined piecewise on the low, medium, and high regimes. This allows us to show that $A_\vecc \vecx$ is close to the uniform distribution on $\Z_q^{(k-1)\alpha n}$ when $\vecx$ is drawn from such a posterior set $B \subset \Z_q^n$ (see <ref>). However, the upper bound given by $U_{C,s}(h)$ in the high regime $h > s$ is guaranteed automatically as long as $B$ is large enough (see <ref>). Thus, we only need to keep track of the Fourier spectrum for weights in the middle regime; hence, the $(C,s)$-boundedness property that we maintain inductively only concerns Fourier weights in this regime.

More specifically, if a set $B \subset \Z_q^n$ is $(C,s)$-bounded and satisfies $|B| \geq q^{n-s}$, then by <ref>, we have that

\[
\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu\|_0=h}} \frac{q^n}{|B|}\left|\widehat{\one_B}(\vecu)\right| \leq U_{C,s}(h)
\]

for all $0\leq h \leq n$.

Finally, in what follows we will show that the intersection of a bounded set with a “restricted set” is also bounded and this will be the core of our induction. To do this we need to understand the Fourier behavior of restricted sets. It turns out that restricted sets satisfy a property stronger than being bounded, which we term “reduced”-ness below.

[Reduced set]definitionreduced
Let $n,q\in\mathbb{N}$, $0\leq s\leq n$, $C>0$, and $B\subset\Z_q^n$. Let $M$ be a $k$-hypermatching. We say $B$ (as well as its indicator function $\mathbf{1}_B$) is $(M,C,s)$-reduced if the following hold.

* For every $\vecu\in\Z_q^n$, if there exists $i\in[n]$ such that $u_i=1$ but $i$ is not contained in $M$, then $\widehat{\mathbf{1}_B}(\vecu)=0$.

* For every $\vecu\in\Z_q^n$, if there exists a hyperedge $e_i$ of $M$ such that $\langle \vecu, \vece_i \rangle \not\equiv 0 \bmod{q}$, then $\widehat{\mathbf{1}_B}(\vecu)=0$.

* For every $h\in\{1,\dots,s\}$ and $\vecv\in\Z_q^n$,

\[
\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu+ \vecv\|_0=h}}\frac{q^{n}}{|B|}\left|\widehat{\mathbf{1}_B}(\vecu)\right|\leq U_{C,s}(h) \, .
\]

There are two key lemmas about these Fourier analytic conditions. The first lemma establishes the base case of the induction toward showing the aggregated posterior set being $(C,s)$-bounded (for some $C=O(1)$ and $s=\Omega(n)$). In fact, we show a stronger guarantee in which every posterior set $B_t$ is $(M_t,C,s)$-reduced.

[Base case]lemmaboundednessbasecase

For every $q,k\geq2$, $\alpha\in(0,1/k)$, there exists a constant $C$ such that
for every  $k$-hypermatching $M$ on $[n]$ of size $m\leq \alpha n$, suppose $n\in\N$ is large enough and $0<b\leq s\leq n/32$, then the following holds. Let $B\subseteq\Z_q^n$. If (i) there exists a sequence of centers $\vecc$ such that $B$ is $(M,\vecc)$-restricted and (ii) $|B| \geq q^{n-b}$, then $B$ is $(M,C,s)$-reduced.

The proof of <ref> is postponed to <ref>.
(We note that the proof yields that $C\geq 2 \zeta^2 e k^2 q^{3k}$ where $\zeta$ is the constant from <ref>.)

Recall from <ref> that the condition (iv) in <ref> are implied by showing $A_{\vecc}\vecx$ is close to the uniform distribution over $\Z_q^{(k-1)m}$ with high probability over to choice of $A_{\vecc}$ where $\vecx$ is sampled uniformly from the posterior set $B_{1:t}$. The second key lemma shows that $A_{\vecc}\vecx^*$ is indeed close to uniform when the posterior set is bounded.

[Boundedness implies closeness to uniformity]lemmaboundednessuniform
For every $q,k\geq2$ and $\delta \in (0,1/2)$, there exists $\alpha_0 = \alpha_0(k,q)$ such that for every $\alpha\in (0,\alpha_0)$, $C>0$, there exists $\tau_0=\tau_0(q,k,\alpha,\delta,C)$ such that the following holds for any $\tau\in (0,\tau_0)$ and sufficiently large $n$:

Let $B\subset \Z_q^n$ be a $(C,s)$-bounded set with $|B| \geq q^{n-b}$, for $4\log(3/\delta)\leq b \leq s\leq \tau n$. Let $M$ be a random $k$-hypermatching of size $\alpha n$ and $\vecc$ be a sequence of centers for $M$ and let $A_{\vecc}$ denote the $\vecc$ centered folded encoding and $M$. Then, with probability at least $1-\delta$ over the choice of $M$, we have that for every $\vecz_0\in\Z_q^{(k-1)\alpha n}$, we have

\[
1-\delta<q^{(k-1)\alpha n}\Pr_{\vecx\sim\Unif(B)}[A_{\vecc}\vecx=\vecz_0] < 1+\delta \, .
\]

As a consequence, we also have

* $\|(A_{\vecc}\vecx)-U\|_{tvd}\leq\delta$ where $\vecx\sim\Unif(B)$ and $U\sim\Unif(\Z_q^{(k-1)\alpha n})$.

* For every non-negative function $f$ over
$\Z_q^{(k-1)\alpha n}$,

\[
(1-\delta)\le \frac{\mathbb{E}_{\vecx\sim \Unif(B)}\left[f(A_c\vecx)\right]}{\mathbb{E}_{\vecz\sim \Unif(\Z_q^{(k-1)\alpha n})}\left[f(\vecz)\right]} \le (1+\delta) \, .
\]

The proof of <ref> is postponed to <ref>.

Our final lemma of this section asserts that if $\one_{B_{1:t}}$ is $(C,s)$-bounded, then $f_{1:t+1}$ is $(O(C),s)$-bounded with high probability.

For every $q,k\in\N$ there exist $\alpha_0\in(0,1/k)$ and $C_0>0$ such that for every $\alpha\in(0,\alpha_0]$, $C>C_0$, and $\delta\in(0,1/2)$, there exist $C'>0$, $n_0\in\N$, and $\tau_0\in(0,1)$ such that the following holds.
For every $n\geq n_0$,  every $0<b,b',s<\tau_0 n$, and every $B\subset\Z_q^n$ that satisfies $|B| \geq q^{n-b}$ and is $(C,s)$-bounded, let $M$ be a uniformly random $k$-hypermatching of size at most $\alpha n$, with probability at least $1-4\delta$ over the randomness of $M$, for every $(M,C_0,s)$-reduced set $B'\subset\Z_q^n$ with $|B'|\geq q^{n-b'}$ and $|B\cap B'|\geq(1-\delta)\cdot|B|\cdot|B'|/q^n \geq q^{n-s}$, we have $B\cap B'$ is $(C',s)$-bounded.

<ref> is proved in <ref>. In our inductive application of the lemma above,
we  set $B\gets B_{1:t-1}$ and $B'\gets B_t$ for every $t\in\{2,3,\dots,T\}$ to get that all the $B_t$'s are bounded and this is the core of the proof of <ref>.

§.§ Proof of Lemma <ref>

For every $q,k\in\N$, we choose $\alpha_0'$ to be the minimum of the $\alpha_0$'s from the induction step (i.e., <ref>) and the “boundedness implies uniformity” lemma (i.e., <ref>). We set $C_0$ according to <ref> and for every $\alpha\in(0,\alpha_0']$, $T\in \N$, and $\delta\in(0,1)$, we invoke <ref> with $\delta'=\delta/10T$ and $C=C_0$ to get $\tau_0=\tau_0(q,k,\alpha,\delta',C_0)>0$ and set $s=\tau_0 n$.  Let $\tau>0$ be a small constant. (We will explicitly fix this quantity later.) Let $b=\tau n+\log_q(10/\delta')$. We choose $\tau$ such that $2Tb<s=\tau_0 n$. Let $C_1=C_0$. We define $\cE_1$ to be the event that $|B_1|\geq q^{n-2b}$ and $B_1$ is $(C_1,s)\text{-bounded}$, where $B_1$ refers to the posterior set defined in <ref>. By the “posterior set is large” lemma (i.e., <ref>) and the “base case” lemma (i.e., <ref>) we have $\Pr[\overline{\cE_1}]\leq\delta'/10\leq\delta/T$ as desired. This satisfies condition (ii) of <ref>. See <ref> for a pictorial overview of the proof.

Next, for each $t\in\{2,3,\dots,T\}$, let $\cE_t=\cE_1\cap\cdots\cap\cE_{t-1}\cap\cE'_t$ where $\cE'_t$ denotes the event that the aggregate posterior set $B_{1:t}$ is large, i.e., $|B_{1:t}|\geq q^{n-2tb}$ and $B_{1:t}$ is $(C_t,s)\text{-bounded}$, where $C_t>0$ is a constant that will be inductively chosen later. Note that by construction $\cE_t$ only depends on $(A_{1:t},\vecc_{1:t})$ and $S_{1:t-1}^Y$ and hence satisfies condition (i) of the lemma. To show that $\cE_t$ happens with high probability conditioned on $\cE_{t-1}$, note that by the “posterior set is large” lemma (i.e., <ref>) and the “base case” lemma (i.e., <ref>), we have $|B_t|\geq q^{n-b}$ and $B_t$ is $(M_t,C_0,s)$-reduced with probability at least $1-\delta'$. Moreover, the event $\cE_{t-1}$ implies that $B_{1:t-1}$ is $(C_{t-1},s)$-bounded and hence if we set $\tau<\tau_0(q,k,\alpha,\delta',C_{t-1})$, by the “boundedness implies uniformity” lemma (i.e., <ref>), $\Z_q^{(k-1)\alpha n}$, we have the following claim.

When $2Tb<s$, conditioned on $\cE_{t-1}$, with probability at least $(1-\delta')$ over the choice of $M_t$, the set $B_{1:t}$ satisfies

\[
|B_{1:t}|\geq(1-\delta')\cdot|B_{1:t-1}|\cdot|B_t|/q^n \, .
\]

By the “boundedness implies uniformity” lemma (i.e., <ref>), $\Z_q^{(k-1)\alpha n}$, we have

\begin{equation}\label{eqn:close_to_uniform}
(1-\delta')\le \frac{\mathbb{E}_{x\sim \Unif(B_{1:t-1})}\left[f(A_{t,c_t}x)\right]}{\mathbb{E}_{z\sim \Unif(\Z_q^{(k-1)\alpha n})}\left[f(z)\right]} \le (1+\delta')\,
\end{equation}

for every non-negative function $f$.
Set $f$ to be the indicator function of $B_{r,t}$ (recall that $B_{r,t}$ is the “reduced posterior set” from <ref>) and apply <ref>, we have

\[ \mathbb{E}_{x\sim \Unif(B_{1:t-1})}\left[\one_{B_{r,t}}(A_{t,c_t}x)\right] = \frac{|B_{1:t}|}{|B_{1:t-1}|}\, ,\]

\[ \mathbb{E}_{z\sim \Unif(\Z_q^{(k-1)\alpha n})}\left[\one_{B_{r,t}}(z)\right] = \frac{|B_{r,t}|}{q^{(k-1)\alpha n}} = \frac{|B_t|}{q^n}\, .\]

We have

\begin{align*}
\frac{|B_{1:t}|}{q^n} &= \frac{|B_{1:{t-1}}|}{q^n} \cdot  \mathbb{E}_{x\sim \Unif(B_{1:t-1})}\left[\one_{B_{r,t}}(A_{t,c_t}x)\right] \\
&\ge (1-\delta') \frac{|B_{1:{t-1}}|}{q^n} \cdot \mathbb{E}_{z\sim \Unif(\Z_q^{(k-1)\alpha n})}\left[\one_{B_{r,t}}(z)\right]\\
&= (1-\delta') \frac{|B_{1:{t-1}}|}{q^n} \cdot \frac{|B_t|}{q^n} \, .
\end{align*}

Hence $|B_{1:t}|=|B_{1:t-1}\cap B_t|\geq(1-\delta')\cdot|B_{1:t-1}|\cdot|B_t|/q^n\geq q^{n-2tb}\geq q^{n-s}$, where the last inequality is due to $2Tb<s$.

Thus, by invoking the “induction step” lemma (i.e., <ref>) on $B_{1:t-1}$ and $B_t$ with $C=C_{t-1}$, there exists a constant $C_t$ such that that $B_{1:t}=B_{1:t-1}\cap B_t$ is $(C_t,s)$-bounded with probability at least $1-4\delta'$. Namely, we have $\Pr[\overline{\cE_t}\, |\, \cE_{t-1}]\leq5\delta'\leq\delta/T$. This satisfies condition (iii).

Finally, for every $t\in[T]$, if we set $\tau<\tau_0(q,k,\alpha,\delta',C_{t-1})$, by the “boundedness implies uniformity” lemma (i.e., <ref>), we know that $\|(A_{\vecc}\vecx^*)-U_t\|_{tvd}\leq\delta'$ where $\vecx^*\sim\Unif(B_{1:t})$ $U_t\sim\Unif(\Z_q^{(k-1)\alpha n})$. As $S_{1:t}^Y=r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},A_{t,\vecc}\vecx^*)$ where $\vecx^*\sim\Unif(B_{1:t})$, by the data processing inequality we have $\|S^Y_t-r_t(A_{1:t},\vecc_{1:t},S^Y_{1:t-1},U_t)\|_{tvd}\leq\delta/T$ as desired. This satisfied condition (iv).

To conclude, we set $\tau>0$ to be a small constant that satisfies $2Tb<\tau_0 n$ and $\tau<\tau_0(q,k,\alpha,\delta',C_{t-1})$ for all $t\in[T]$ where $C_t$ is inductively chosen as described above. This completes the proof of <ref>.

A pictorial overview of the proof of <ref>.

§ ANALYSIS OF BOUNDED FUNCTIONS

In this section, we provide the complete proof for the three important lemmas in <ref>: the “base case” lemma (i.e., <ref>), the “boundedness implies uniformity” lemma (i.e., <ref>), and the “induction step” lemma (i.e., <ref>).
We first establish useful structure on the Fourier coefficients of restricted sets (posterior set is a special case of restricted set) in <ref>. Next, we prove useful properties for the Fourier analytic conditions in <ref>. Finally, we prove the three lemmas in <ref>, <ref>, and <ref> respectively.

§.§ Fourier coefficients of the posterior function

Given a $k$-hypermatching $M = (e_1,\ldots,e_m)$ and centers $\vecc = (c_1,\ldots,c_m)$ we say that a set $B \subseteq \Z_q^n$ is $(M,\vecc)$-restricted if there exists a (“reduced”) set $B_r \subseteq \Z_q^{(k-1)m}$ such that $B = \{\vecx \in \Z_q^n | A_{\vecc}\vecx \in B_r\}$, where $A_\vecc$ is the $\vecc$-centered folded encoding of $M$. In this section we aim to prove that large restricted sets are bounded.
Recall that given a $k$-hypermatching $M = (e_1,\ldots,e_{m})$ on vertex set $[n]$ with $m=\alpha n$ edges and sequence of centers $\vecc = (c_1,\ldots,c_{m})$ with $c_i \in e_i \subseteq [n]$, the $\vecc$-centered folded representation of $M$ was denoted $A_{\vecc} \in \Z_q^{(k-1)m \times n}$. We say that a set $B \subseteq \Z_q^n$ is $(M,\vecc)$-restricted if there exists a (“reduced”) set $B_r \subseteq \Z_q^{(k-1)m}$ such that $B = \{\vecx \in \Z_q^n | A_{\vecc}\vecx \in B_r\}$. For our next lemma we will also need a variant of this matrix named the $\vecc$-centered projection induced by  $M$, which we denote $\widetilde{A}_\vecc \in \Z_q^{(k-1)m \times n}$, which is simply the matrix $A_\vecc$ with the columns corresponding to $c_1,\ldots,c_{m}$ zeroed out. (In $A_\vecc$ each of these columns has $(k-1)$ $-1$'s. See <ref>.) With this definition in place we can now relate the Fourier coefficients of the indicator of a restricted set to its image.

An example of $A_\vecc,\tilde{A}_\vecc,A^{(1)}_\vecc,\tilde{A}^{(1)}_\vecc$ with $m=1$, $n=7$, $k=4$, $e_1=\{1,3,5,7\}$ and $c_1=\{5\}$.

Recall that we use $\vece_i \in \Z_q^n$ to denote the indicator vector of hyperedge $e_i$ (see <ref>).

Let $M$ be a $k$-hypermatching of size $m$ and $\vecc$ be a sequence of centers. Let $A_\vecc$ be the folded representation of $M$ and $\widetilde{A}_\vecc$ be the  projection induced by $M$. Furthermore, let $B \subseteq \Z_q^n$ be an $(M,\vecc)$-restricted set with $B_r \in \Z_q^{(k-1)m}$ satisfying $B = \{\vecx \in \Z_q^n | A_\vecc \vecx \in B_r\}$. Let $\one_B$ denote the indicator function of $B$. Then for every $\vecu \in \Z_q^n$ we have:

\[
\widehat{\one_B}(\vecu)=\begin{cases}
0     , \quad &\text{if $\vecu$ contains a node not in $M$.}\\
0     ,  \quad &\text{if $\exists i \in [m]$ such that $\langle \vecu, \vece_i \rangle \not\equiv 0 \pmod{q}$}\\
\widehat{\mathbf{1}}_{B_r}(\widetilde{A}_\vecc  \vecu), \quad &\text{otherwise.}
\end{cases}.
\]

From the definition of the Fourier coefficient we have $\widehat{\one_B}(\vecu) = \tfrac{1}{q^n}\sum_{\vecx \in \Z_q^n} \one_B(\vecx) \omega^{\vecu^\top \vecx}$ where $\omega=e^{2\pi i/q}$ being the primitive $q$-th root of unity. Using the fact that $B$ is restricted, we get

\[
\widehat{\one_B}(\vecu)= \frac{1}{q^n} \sum_{\vecx \in \Z_q^n} \one_B(\vecx) \cdot\omega^{\vecu^\top \vecx}
= \frac{1}{q^{n}} \sum_{\substack{\vecz\in \Z_q^{(k-1)m}}}\sum_{\substack{\vecx\in\Z_q^n\\A_\vecc \vecx = \vecz}} \one_{B_r}(\vecz) \cdot \omega^{\vecu^\top \vecx}
= \frac{1}{q^{n}} \sum_{\substack{\vecz\in B_r}}\sum_{\substack{\vecx\in\Z_q^n\\A_\vecc \vecx = \vecz}} \omega^{\vecu^\top \vecx}.
\]

We now fix $\vecz \in B_r$ and explore the final term $\sum_{{\vecx\in\Z_q^n, A_\vecc \vecx = \vecz}} \omega^{\vecu^\top \vecx}$. Let $\vecz = (\vecz^{(1)},\ldots,\vecz^{(m)})$ where $\vecz^{(i)} \in \Z_q^{k-1}$. Also let $A_\vecc^{(1)},\ldots,A_\vecc^{(m)} \in \Z_q^{(k-1)\times n}$ denote the blocks of $A_\vecc$ corresponding to the $m$ edges. Now, think of $\Z_q^n$ as a free module over $\Z_q$ and consider the direct sum decomposition $\Z_q^n = W^{(0)} \oplus \cdots \oplus W^{(m)}$ where for $i \in [m]$,  $W^{(i)}$ is the sub-module of $\Z_q^n$ generated by $e_i$, $W^{(0)}$ is the sub-module generated by $[n]-(\cup_i e_i)$, and “$\oplus$” denotes the direct sum of modules. Let us write $\vecx = \vecx^{(0)} + \cdots + \vecx^{(m)}$ where for $i \in \{0,\ldots,m\}$, $\vecx^{(i)} \in W^{(i)}$.
Similarly write $\vecu = \vecu^{(0)} + \cdots + \vecu^{(m)}$.
Since $(\vecu^{(i)})^\top \vecx^{(j)} = 0$ if $i \ne j$ we have $\vecu^\top \vecx = \sum_{i=0}^m (\vecu^{(i)})^\top\vecx^{(i)}$.
Note also that $\vecz = A_\vecc \vecx$ if and only if $\vecz^{(i)} = A_\vecc^{(i)} \vecx^{(i)}$ for every $i \in [m]$. Using this notation, we have

\[
\sum_{\substack{\vecx\in\Z_q^n\\A_\vecc \vecx = \vecz}} \omega^{\vecu^\top \vecx} = \left(\sum_{\vecx^{(0)}\in W^{(0)}} \omega^{(\vecu^{(0)})^\top \vecx^{(0)}}\right)\cdot \prod_{i=1}^m
\left(\sum_{\substack{\vecx^{(i)}\in W^{(i)} \\ A_\vecc^{(i)}\vecx^{(i)} = \vecz^{(i)}}} \omega^{(\vecu^{(i)})^\top \vecx^{(i)}}\right) \, . \]

Now note that if $\vecu^{(0)} = 0$ then the first term is $|W^{(0)}| = q^{n-km}$, else it is zero. Similarly for $i\in [m]$, there are exactly $q$ vectors $\vecx^{(i)}\in W^{(i)}$ such that $A_\vecc^{(i)} \vecx^{(i)} = \vecz^{(i)}$ (which are additive shifts of each other on coordinates in $e_i$). Concretely, these two solutions are of the form $(\tilde{A}_\vecc^{(i)})^\top\vecz^{(i)}+a^k$ for some $a\in\Z_q$. So we have

\[
\sum_{\vecx^{(i)}\in W^{(i)}:A_\vecc^{(i)}\vecx^{(i)} = \vecz^{(i)}} \omega^{(\vecu^{(i)})^\top \vecx^{(i)}}=\sum_{ a\in\Z_q}\omega^{(\vecu^{(i)})^\top (\tilde{A}_\vecc^{(i)})^\top\vecz^{(i)}+(\vecu^{(i)})^\top a^k}=\omega^{(\vecu^{(i)})^\top (\tilde{A}_\vecc^{(i)})^\top\vecz^{(i)}}\sum_{ a\in\Z_q}\omega^{a\cdot\|\vecu^{(i)}\|_1} \, .
\]

\[
\sum_{ a\in\Z_q}\omega^{a\cdot\|\vecu^{(i)}\|_1}  = \begin{cases}
0     &  \text{if }\|\vecu^{(i)}\|_1\not\equiv0\bmod{q}\\
q     & \text{otherwise}.
\end{cases}.
\]

Putting all the above together we get

\[
\sum_{{\vecx\in\Z_q^n\\A_\vecc \vecx = \vecz}} \omega^{\vecu^\top \vecx}=\begin{cases}
0     \quad &\text{if $\vecu$ contains a node not in $M$.}\\
0     \quad &\text{if $\exists i \in [m]$ such that $\langle \vecu, \vece_i \rangle \not\equiv 0 \bmod{q}$}\\
q^{n-(k-1)m}\cdot\omega^{(\widetilde{A}_\vecc  \vecu)^\top \vecz} \quad &\text{otherwise.}
\end{cases}.
\]

Summing up over all $\vecz \in \Z_q^{(k-1)m}$ and normalizing yields the lemma.

§.§ Properties of the Fourier analytic conditions

First, recall that we define a set being restricted in <ref>. Observe that the restrictedness of a set is independent to the choice of centers.

Let $\vecc = (c_1,\ldots,c_m)$ and $\vecc' = (c'_1,\ldots,c'_m)$ be two sequences of centers for the same matching $M$. Then a set $B \subseteq \Z_q^n$ is
$(M,\vecc)$-restricted if and only if it is $(M,\vecc')$-restricted.

Let $e_i^{(t)} = ((e_i^{(t)})_1, \dots, (e_i^{(t)})_k = c_t)$ (for $t=1,2,\dots,m$) be the ordering of hyperedges corresponding to centering $\vecc$, and let ${e'}_i^{(t)} = (({e'}_i^{(t)})_1, \dots, ({e'}_i^{(t)})_k = c'_t)$.

Given a permutation $\pi: [k] \to [k]$, let $P_\pi$ be a $(k-1)\times (k-1)$ matrix defined as follows: For $1\leq i,j \leq k-1$, let

\[
(P_\pi)_{i,j} = \begin{cases} 1 &\text{if $j=\pi(i)$}\\ -1 &\text{if $j=\pi(k)$}\\ 0 &\text{otherwise} \end{cases}.
\]

For $t=1,2,\dots, m$, let $\pi_t:[k]\to [k]$ be the permutation defined by $({e'}_i^{(t)})_j = (e_i^{(t)})_{\pi(j)}$, and let $\pi'_t: [k]\to[k]$ be the permutation defined by $(e_i^{(t)})_j = ({e'}_i^{(t)})_{\pi(j)}$. Then, it is not hard to see that $A_{\vecc'} = Q \cdot A_\vecc$ and $A_\vecc = Q' \cdot A_{\vecc'}$

\[
Q = \begin{pmatrix} P_{\pi_1} & & & \\ & P_{\pi_2} & & \\ & & \ddots & \\ & & & P_{\pi_m} \end{pmatrix}, \qquad\qquad Q' = \begin{pmatrix} P_{\pi'_1} & & & \\ & P_{\pi'_2} & & \\ & & \ddots & \\ & & & P_{\pi'_m} \end{pmatrix},
\]

and $QQ' = Q'Q = I$, the $(k-1)m\times (k-1)m$ identity matrix.

Now, suppose $B\subseteq \F_2^n$ is $(M,\vecc)$-restricted. Let $B_r \subseteq \Z_q^{(k-1)m}$ be the corresponding reduced set satisfying $B = \{\vecx \in \Z_q^n \mid A_\vecc \vecx \in B_r\}$. Then, let $B_r' = \{Q\vecy \mid \vecy \in B_r\}$.

Note that if $\vecx \in B$, then $A_{\vecc'} \vecx = Q(A_\vecc \vecx) \in B_r'$. Similarly, if $A_{\vecc'} \vecx \in B_r'$, then there is some $\vecy\in B_r$ such that $A_{\vecc'} \vecx = Q\vecy$, and so, $A_\vecc \vecx = Q' A_{\vecc'} \vecx = Q' Q \vecy = \vecy \in B_r$, implying that $\vecx \in B$. It follows that $B$ is $(M,\vecc')$-restricted with reduced set $B'_r$.

In an analogous fashion, it follows that if $B$ is $(M,\vecc')$-restricted, then $B$ is also $(M,\vecc)$-restricted. This completes the proof.

Recall the notion of bounded sets from <ref>.

If $C > e$, then $U_{C,s}(h)$ is monotonically increasing in $h \in [1,s]$.

Recall that the function $f(x) = x^{1/x}$ is decreasing in the interval $(e,\infty)$  (since $f'(x) = x^{1/x} \cdot \frac{1-\ln x}{x^2}$ is negative for $x > e$). Note that $U_{C,s}(h) = x^{\frac{C\sqrt{sn}}{2x}}$ for $x = \frac{C\sqrt{sn}}{h}$. Moreover, for $h\leq s$, we have $x \geq \frac{C\sqrt{sn}}{s} \geq C > e$. Hence, it follows from monotonically decreasing property of $f$ that $U_{C,s}(h)$ is monotonically increasing in the described interval, as desired.

Recall the definition of a set being reduced from <ref>.

Note that if a set $B$ is $(M,C,s)$-reduced then $B$ is also $(C,s)$-bounded. Given these definitions, there are three tasks left to complete the proof of <ref>. First, show in <ref> that if the aggregated posterior set $B_{1:T}$ is $(C,s)$-bounded for some $C=O(1)$ and $s=\Omega(n)$, then it will satisfy the conditions needed in <ref> with high probability. Next, we show the posterior set $B_{1:T}$ is indeed bounded by induction. In <ref> we analyze the base case and show that every posterior set $B_t$ is $(M_t,C',s)$-reduced for some $C'=O(1)$. The induction step is much more involved where we show that the intersection of a $(C,s)$-bounded set (e.g., $B_{1:t}$) and a $(M,C',s)$-reduced set (e.g., $B_{t+1}$) is $(C'',s)$-bounded with high probability (over the randomness of $M$) for some $C''=O(1)$. The analysis for the induction step is postponed to <ref>.

§.§ Proof of the “base case” lemma

In this subsection, we prove the “base case” lemma (<ref>), which shows that every posterior set $B_t$ is $(M_t,C,s)$-reduced for some constant $C$. We include the statement again below for convenience.

To see how the above lemma connects to posterior sets, think of $B$ as $B_t$, $M$ as $M_t$, and $\vecc$ as $\vecc_t$. Note that condition (i) of <ref> holds by the definition of $B_t$. As for condition (ii), it holds when the message $S_t$ is typical and we know by averaging argument that this is the case with high probability (see <ref> for more details).

To prove this lemma, we need to put together a few ingredients. First, <ref> which tells us that being restricted is independent of the choice of centers. We also recall Parseval's lemma in this context.

For every $B \subseteq \Z_q^n$ we have $\sum_{\vecv \in \Z_q^n} \widehat{\mathbf{1}_B}(\vecv)^2 \leq |B|/q^n$.

(<ref> follows from <ref> by noticing that $\sum_{\veca \in \Z_q^n} \one_{B}(\veca) = |B|$.)
Recall that the $(C,s)$-bounded criterion bounds the sum of Fourier coefficients with a fixed weight at most $s$. As we also need to bound the sum of Fourier coefficients of high weight, this can be guaranteed from Parseval's inequality as shown in the following lemma.

Suppose $B \subset \Z_q^n$ satisfies $|B| \geq q^{n-b}$ for some $b\in\N$. Then, for every $\vecv\in\Z_q^n$ and $b < h \leq n$, we have

\[
\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu+\vecv\|_0=h}} \frac{q^n}{|B|}\left|\widehat{\one_B}(\vecu)\right| \leq \left(\frac{2q^2e^2 n}{h}\right)^{h/2}.
\]

Note that by <ref>, we have
$\sum_{\vecu\in S_h}\left|\widehat{\mathbf{1}_B}(\vecu)\right|^2 \leq |B|/q^n.$

\[
\left|\left\{\vecu\in\Z_q^n \, |\, \|\vecu+\vecv\|_0=h\right\}\right|\leq (q-1)^h\cdot\binom{n}{h}\leq\left(\frac{qen}{h}\right)^h
\]

and the Cauchy-Schwarz inequality we get

\begin{align*}
\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu+\vecv\|_0=h}}\frac{q^n}{|B|}\left|\widehat{\one_B}(\vecu)\right|
& \leq  \frac{q^n}{|B|} \sqrt{(|B|/q^n) \cdot (qen/h)^h} \\
& =  \sqrt{(q^n/|B|) \cdot (qen/h)^h} \\
& \leq \sqrt{q^b  (qen/h)^h} & (\because |B|\geq q^{n-b}) \\
& \leq \sqrt{q^h  (qen/h)^h} & (\because h>b)\\
& =  (2q^2e^2 n/h)^{h/2}.
\end{align*}

We now turn to the proof of Lemma <ref>. The overall proof follows the outline of [10], but we require extra care in our case, and the proof crucially depends on the ability to recenter (<ref>) and a slightly more careful probabilistic analysis.

The first two conditions of $(M,C,s)$-reducedness are immediate corollaries of <ref>. So in the rest of the proof we focus on showing for every $h\in\{1,\dots,s\}$ and $\vecv\in\Z_q^n$,

\[
\sum_{\substack{\vecu\in\Z_q^n\\\|\vecu+\vecv\|_0=h}}\frac{q^{n}}{|B|}\left|\widehat{\mathbf{1}_B}(\vecu)\right|\leq U_{C,s}(h) \, . \tag{Goal of~\autoref{lem:boundedness base case}}
\]

Fix an arbitrary $\vecv\in\Z_q^n$. For each $h\in\{1,\dots,s\}$, let $S_h = S_{\vecv,h} = \{\vecu\, |\, \|\vecu + \vecv\|_0 = h\}$, i.e., the set of Fourier coefficients in the above summation.

Next, we are only interested in the subset of $S_h$ that gives non-zero contribution in the summation. Recall by <ref> that
$\widehat{\one_B}(\vecw) = 0$ if $\supp(\vecw) \not\subseteq \supp(M)$, or if there exists $i \in [\alpha n]$ such that $\langle \vecw, \vece_i \rangle \not\equiv 0 \bmod{q}$.

\[
T_{\vecv,h,M} = \{\vecu \in \Z_q^n \, |\, \|\vecu+\vecv\|_0 = h, \supp(\vecu) \subseteq \supp(M), \langle \vecu, \vece_i \rangle \equiv 0 \bmod{q} \ \forall i \in [\alpha n]\},
\]

denote this set of vectors which contains the non-zero Fourier coefficients. Roughly, our approach below is to (1) give an upper bound on the size of the set $T_{\vecv,h,M}$ and (2) bound the sum of the squares of the coefficients in this set. Once we have both these bounds, we can apply Cauchy-Schwartz to conclude the desired bound. Before we undertake these steps, we make some simplifications and some refinements.

Step 0: Regular condition of $\vecv$.
First note that we can assume $\supp(\vecv) \subseteq \supp(M)$. If this is not the case, consider the vector $\widetilde{\vecv}$ given by $\widetilde{v_i} = v_i$ if $i \in \supp(M)$ and $\widetilde{v_i} = 0$ otherwise. Also, let $a = |\{i \, |\, \text{$v_i \neq 0$ and $i \not\in\supp(M)$} \}|$ be the number of nodes in the support of $\vecv$ that are untouched by the matching $M$. Then note that $T_{\vecv,h,M} = T_{\tilde{\vecv},h-a,M}$. If we show that $(q^n/|B|)\cdot \sum_{\vecu \in T_{\tilde{\vecv},h-a,M}} |\widehat{\one_B}(\vecu)| \leq U_{C,s}(h-a)$ then, by the monotonicity of $U_{C,s}(\cdot)$ in the interval $[1,s]$ (see <ref>), it follows that $(q^n/|B|)\cdot \sum_{\vecu \in T_{\vecv,h,M}} |\widehat{\one_B}(\vecu)| \leq U_{C,s}(h)$. Thus, from now on, we assume $\supp(\vecv) \subseteq \supp(M)$.

Step 1: A partition of $T_{\vecv,h,M}$.
We now further refine $T_{\vecv,h,M}$, i.e., the set of non-zero Fourier coefficients. For an integer $\ell$, let $T_{\vecv,h,\ell,M} = \{\vecu \in T_{\vecv,h,M} \, |\, \#\{i\in[\alpha n] \, |\, e_i \cap \supp(\vecu+\vecv) \not=\emptyset\} = \ell\}$ be the set $\vecu\in T_{\vecv,h,\ell,M}$'s such that the support of $\vecu+\vecv$ touches exactly $\ell$ edges. Since $\vecv,h$ and $M$ will be fixed in the rest of this proof, we simplify the notation and refer to this set as $T_\ell$. Note that $h/k \leq \ell \leq h$. Thus, the quantity we are interested in this lemma can be upper bounded as follows.

\[
\frac{q^n}{|B|} \sum_{\vecu\in S_h}\left|\widehat{\one_B}(\vecu)\right|  =
\frac{q^n}{|B|} \sum_{\vecu\in T_{\vecv,h,M}} \left|\widehat{\one_B}(\vecu)\right|  = \sum_{\ell = h/k}^{h} \frac{q^n}{|B|} \sum_{\vecu\in T_{\ell}} \left|\widehat{\one_B}(\vecu)\right|  \leq \sum_{\ell = h/k}^{h} \frac{q^n}{|B|} \sqrt{ |T_{\ell}| \sum_{\vecu\in T_{\ell}} \widehat{\one_B}(\vecu)^2}
\]

where the first equality is due to <ref>, the second equality is due to the partition, and the last inequality is by Cauchy-Schwarz inequality. The reason why we partition $T_{\vecv,h,M}$ into $T_\ell$'s is that the Fourier square-mass within $T_\ell$ and the cardinality of $T_\ell$ can be properly upper bounded respectively.

Step 2: Upper bound the Fourier square-mass within $T_\ell$.
To upper bound the Fourier square-mass within $T_\ell$, we utilize the fact that the posterior set $B$ is independent to the choice of center $\vecc$ (i.e., <ref>) and a hypercontractivity inequality.

We remark that the fact that the exponent of $b$ below is $h-\ell$ (as opposed to the more trivial $h$, or $h(k-1)/k$) is crucial to our proof and ensures we eventually get a linear space lower bound. In turn this bound is obtained by using a random center $\vecc$ and this randomization is permitted at the analysis stage by <ref>.

There exists a constant $\zeta_1$ such that if $|B|\geq q^{n-b}$ for some $b\in\N$ then for every $1\leq\ell< h\leq b$, we have

\[
\sum_{\vecu \in T_\ell} \widehat{\one_{B}}(\vecu)^2 \leq k^{\ell} \left(\frac{|B|}{q^{n}}\right)^2 \left(\frac{\zeta_1 \cdot b}{h-\ell}\right)^{h-\ell} \, .
\]

The proof of this claim uses <ref> to relate the Fourier coefficients of the function $\one_B$ to those of $\one_{B_r}$. But note that the “reduced set” $B_r$ depends on the choice of the center. Furthermore the weight of the Fourier coefficient in the reduced space depends on how the centers overlap with $\supp(\vecu+\vecv)$. Specifically we have that for centers $\vecc$, $\vecc$, $\|\widetilde{A}_{\vecc}(\vecu+\vecv)\|_0 = \|\vecu+\vecv\|_0 - t$, where $t = |\{i \in [\alpha n] \, |\, c_i \in \vecu + \vecv\}|$ is the number of centers contained in $\vecu+\vecv$. Note that $t \leq \ell$ since the number centers in $\supp(\vecu + \vecv)$ can not exceed the number of edges touching this set. The crux of the  proof of this claim is that we if choose the centers randomly and then there is a positive probability that all centers (of the edges that touch $\supp(\vecu+\vecv)$) are in $\supp(\vecu+\vecv)$. We argue the formal details below.

For a random center $\vecc$, let $A_{\vecc}$ denote the $\vecc$-centered folded encoding of $M$, and let $B_{r,\vecc}=\{A_\vecc\vecx \, |\, \vecx\in B \} \subseteq \Z_q^{(k-1)\alpha n}$. Note that the random center $\vecc$ here is for the analysis purpose and in general might be different from the center used in the communication game. Nevertheless, due to <ref> the choice of center does not affect the analysis. For $\vecu \in T_\ell$, let $I_\vecu(\vecc) =1$ if $c_i \in \supp(\vecu+\vecv)$ for every $i\in[\alpha n]$ with $e_i\cap\supp(\vecu+\vecv)\neq\emptyset$ and $0$ otherwise. Note that $\Pr_{\vecc}[I_\vecu(\vecc)=1] \geq k^{-\ell}$. Now consider the following expression:

\begin{align*}
\Exp_{\vecc} \left[\sum_{\substack{\vecw \in \Z_q^{(k-1)\alpha n}\\ \|\vecw+\widetilde{A}_\vecc\cdot \vecv\|_0 = h-\ell}} \widehat{\one_{B_{r,\vecc}}}(\vecw)^2 \right]
& \geq \Exp_{\vecc} \left[\sum_{\vecu \in T_{\ell}} I_\vecu(\vecc)\cdot \widehat{\one_{B}}(\vecu)^2 \right] & (\because~\autoref{lem:fourier coeff of set})\\
& = \sum_{\vecu \in T_{\ell}} \left(\widehat{\one_{B}}(\vecu)^2 \Exp_{\vecc} \left[ I_\vecu(\vecc)  \right]\right) & (\because B\text{ and }T_{\ell}\text{ are independent to }\vecc)\\
& \geq k^{-\ell} \sum_{\vecu \in T_{\ell}} \widehat{\one_{B}}(\vecu)^2 \, . & (\because \Pr_{\vecc}[I_\vecu(\vecc)=1] \geq k^{-\ell})
\end{align*}

On the other hand, note that $|B_{r\vecc}|=|B|\geq q^{n-b}$ and hence by <ref>, for every $\vecc$ we have

\begin{align*}
\sum_{\substack{\vecw \in \Z_q^{(k-1)\alpha n}\\ \|\vecw+\tilde{A}_\vecc\cdot \vecv\|_0 = h-\ell}} \widehat{\one_{B_{r,\vecc}}}(\vecw)^2 &\leq \left(\frac{|B_{r,\vecc}|}{q^{(k-1)\alpha n}}\right)^2 \left(\frac{4b}{h-\ell}\right)^{h-\ell} \, ,
\end{align*}

where $\zeta_1 = \zeta$ is the constant from <ref>.
Also, note that since $B$ is $(M,\vecc)$-restricted, we have $|B|=|\{\vecx\in\Z_q^n\ |\ A_\vecc\vecx\in B_{r,\vecc}\}|=|B_{r,\vecc}|\cdot q^{n-\textsf{rank}(A_\vecc)}$. As $\textsf{rank}(A_\vecc)=(k-1)\alpha n$, the above inequality becomes

\begin{align*}
\sum_{\substack{\vecw \in \Z_q^{(k-1)\alpha n}\\ \|\vecw+\tilde{A}_\vecc\cdot \vecv\|_0 = h-\ell}} \widehat{\one_{B_{r,\vecc}}}(\vecw)^2 &\leq
\left(\frac{|B|}{q^{n}}\right)^2 \left(\frac{\zeta_1 \cdot b}{h-\ell}\right)^{h-\ell} \, .
\end{align*}

Putting the two inequalities together we get

$$\sum_{\vecu \in T_\ell} \widehat{\one_{B}}(\vecu)^2 \leq k^{\ell} \left(\frac{|B|}{q^{n}}\right)^2 \left(\frac{\zeta_1\cdot b}{h-\ell}\right)^{h-\ell},$$

thus proving the claim.

Step 3: Upper bound the cardinality of $T_\ell$.
Next, we turn to bounding the size of the set $T_\ell$. To do so we explore the structure of the vectors in $T_{\ell}$. We start with some notation. Let
$E = \{i\in[\alpha n] \, |\,  \langle \vecv, \vece_i \rangle \equiv 0 \pmod{q}\}$
and $O = \{i\in[\alpha n] \,  \langle \vecv, \vece_i \rangle \not\equiv 0 \pmod{q} \}$. Given a vector $\vecu$, we define $W_e = W_e(\vecu) = (\vecu+\vecv) \odot \left(\sum_{i\in E} \vece_i\right)$ and $W_o = W_o(\vecu) = (\vecu+\vecv) \odot \left(\sum_{i\in O} \vece_i\right)$, where $\odot$ is used to denote the Hadamard product (entrywise product) of two vectors.
Let $\eta$ denote the number of edges touched by $W_e$ and let $o$ denote the number of edges touched by $W_o$.
Note the following conditions hold when $\vecu \in T_\ell$.

If $\vecu \in T_\ell$, then all the following conditions hold: (1) $|O| \leq h$, (2) $\eta + o = \ell$, and (3) $\eta\leq h/2$.

We prove each of the individual claims below:

* Note that $\langle \vecu + \vecv, \vece_i \rangle \not\equiv 0 \pmod{q}$ for every $i\in O$, since $\langle \vecu, \vece_i \rangle \equiv 0 \pmod{q}$ and $\langle \vecv, \vece_i \rangle \not\equiv 0 \pmod{q}$. Therefore, $|\supp(\vecu+\vecv) \cap e_i| \geq 1$ for every $i\in O$, implying that $|O| \leq \sum_{i\in O} |\supp(\vecu+\vecv) \cap e_i| \leq \|\vecu+\vecv\|_0 = h$.

* Since $\vecu + \vecv$ touches $\ell$ edges, $\eta + o = \ell$.

* Note that $\langle \vecu + \vecv, \vece_i \rangle \equiv 0 \pmod{q}$ for every $i\in E$, since $\langle \vecu, \vece_i \rangle \equiv 0 \pmod{q}$ and $\langle \vecv, \vece_i \rangle \equiv 0 \pmod{q}$. Therefore, if $i\in E$ is touched by $W_e$ (i.e., $W_e \odot \vece_i \neq \mathbf{0}$), then it follows that $W_e$ touches it in at least two points, i.e., $|\supp(W_e\odot \vece_i)| \geq 2$ (see <ref>). Combined with the fact that $|\supp(W_e)| \leq \|\vecu+\vecv\|_0 = h$, we obtain $\eta \leq h/2$, as desired.

Upper bound the cardinality of $T_\ell$. In this example, $q=3, k=5, m=5$, and $\vecv$ is specified by integers in red. Note that $E=\{2,3,5\}$ and $O=\{1,4\}$. Next, we consider $h=8,\ell=4$ and a $\vecu\in T_\ell$ specified by integers in  blue. Note that by definition we have $\eta=o=2$. In particular, the tuple $(W_e(\vecu),W_o(\vecu))$ is described on the right and $\vecu+\vecv$ is specified by integers in  green. It is immediate to see that $(W_e(\vecu),W_o(\vecu),\vecv)$ uniquely specifies $\vecu$ because one can subtract $W_e(\vecu)$ and $W_o(\vecu)$ by $\vecv$ to get the value of $\vecu$ in those coordinates. In the rest of the coordinates, $\vecu$ has the same values as $\vecv$. Moreover, observe that every hyperedges in $W_e(\vecu)$ should contain at least $2$ non-zero points because both $\vecu$ and $\vecv$ sum up to $0$ mod $q$ within those hyperedges.

We use these to bound
$|T_\ell|$. Recall that each $\vecu\in T_\ell$ is uniquely specified by the pair $(W_e,W_o)$ (see <ref>) and it therefore suffices to count the number of distinct choices of $(W_e,W_o)$. First, we see that the number of possibilities for $W_o$ is at most $(q^k)^{|O|} \leq q^{kh}$ (by the first item of <ref>). Now, having fixed $W_o$ and $o$, consider the number of possibilities of $W_e$. We may choose $W_e$ by picking a set $F\subseteq E$ with $\eta$ edges, and then picking $|\supp(W_e)| = h - |\supp(W_o)|$ elements from the union of the edges in $F$, each of which is given a value in $\Z_q \setminus \{0\}$. Note that $F$ can be chose in at most $\binom{|E|}{\eta} \leq \binom{\alpha n}{\eta}$ ways, after which $W_e$ can be chosen in $\leq q^{k\eta}$ ways. Finally, note that by the second and the third item of <ref> we have $\eta\leq\min\{\ell,h/2\}$. Putting these together, we obtain

\begin{align}
|T_\ell| &\leq \sum_{\eta=0}^{\min\{\ell, h/2\}} \left\{q^{kh} \binom{\alpha n}{\eta} q^{k\eta}\right\} \nonumber\\
&\leq \ell \cdot \max_{0 \leq \eta \leq \min\{\ell,h/2\}} \left\{q^{kh} (e \alpha n/\eta)^\eta q^{k\eta}\right\} \nonumber\\
&\leq \min_{\eta\in\{\ell,h/2\}} \left\{q^{kh} (e \alpha n/\eta)^\eta q^{k\eta}\right\}. \label{eq:reducedness base T bound}
\end{align}

Step 4: Proof of <ref>.
The boundedness of $B$ now follows from some straightforward calculations. First, using the fact that $T_{\vecv,h,M}$ contains all the non-zero Fourier coefficients of $S_h$ and further partitioning it with $T_\ell$, we have by Cauchy-Schwarz inequality

\begin{align*}
\frac{q^n}{|B|} \sum_{\vecu\in S_h}\left|\widehat{\one_B}(\vecu)\right|  &=
\frac{q^n}{|B|} \sum_{\vecu\in T_{\vecv,h,M}} \left|\widehat{\one_B}(\vecu)\right|  = \sum_{\ell = h/k}^{h} \frac{q^n}{|B|} \sum_{\vecu\in T_{\ell}} \left|\widehat{\one_B}(\vecu)\right| \leq \sum_{\ell = h/k}^{h} \frac{q^n}{|B|} \sqrt{ |T_{\ell}| \sum_{\vecu\in T_{\ell}} \widehat{\one_B}(\vecu)^2} \,
\intertext{By step 2 (i.e.,~\autoref{clm:random-center}), step 3 (i.e.,~\autoref{eq:reducedness base T bound}), and the fact that $b\leq s$, we further have}
& \leq \sum_{\ell = h/k}^{h} \frac{q^n}{|B|} \sqrt{ \min_{\eta \in\{\ell,h/2\}} \left\{q^{kh} (e \alpha n/\eta)^\eta q^{k\eta}\right\} k^{\ell} \left(\frac{|B|}{q^{n}}\right)^2 \left(\frac{\zeta_1 s}{h-\ell}\right)^{h-\ell} } \,
\intertext{Next, we consider two regimes of $\ell$: (i) $h/k\leq \ell\leq h/2$ and (ii) $h/2+1\leq \ell\leq h$.}
& \leq \sum_{\ell = h/k}^{h/2}  \sqrt{ q^{kh} (e \alpha n/\ell)^\ell q^{k\ell} k^{\ell}  \left(\frac{\zeta_1\cdot s}{h-\ell}\right)^{h-\ell} }
+\sum_{\ell = h/2+1}^h \sqrt{ q^{kh} (2e \alpha n/h)^{h/2} q^{kh/2} k^{\ell} \left(\frac{\zeta_1 s}{h/2}\right)^{h/2} } \\
& \leq \sum_{\ell = h/k}^{h/2}  \sqrt{ q^{kh} (e \alpha n/\ell)^\ell 2^{k\ell} k^{\ell}  \left(\frac{2\zeta_1 s}{h}\right)^{h-\ell} }
+(h/2) (ns/h^2)^{h/4} (2^{3k}k^2 \zeta_1^2 e )^{h/4}  \\
& \leq (q^{3k}e k^2)^{h/4} (ns/h^2)^{h/4} \sum_{\ell = k/h}^{h/2}  \sqrt{ \left(\frac{2\zeta_1 s}n\right)^{h/2-\ell} }
+(h/2) (ns/h^2)^{h/4} (2^{3k}k^2 \zeta_1^2 e )^{h/4}  \\
& \leq (C\sqrt{ns}/h)^{h/2}\\
& = U_{C,s}(h),
\end{align*}

for $C \geq 2 \zeta_1^2 e k^2 q^{3k}$. Thus, we conclude that $B$ is $(M,C,s)$-reduced.

§.§ Proof: Boundedness implies near uniformity

In this section we prove <ref> which is used to prove condition (iv) of <ref>. We restate the lemma below for convenience.

In the following, we denote $m=\alpha n$ for simplicity. Let us start with defining a combinatorial quantity $p(h,k,m,n)$ and showing an upper bound.

Suppose $k, m, n > 0$ are integers. We define  $p(h,k,m,n)$ to be the probability that, for a uniformly random $k$-hypermatching $M$ with $m$ edges, $h$ fixed nodes in $[n]$, say $[h]$, are contained in $M$ and further satisfy the condition that the intersection size of each hyperedge of $M$ with these fixed nodes is either zero or at least two.

For all integers $n,k$, $\alpha\in(0,1/100k)$, $m = \alpha n$, and $0\leq h\leq m$, we have

\[
p(h,k,m,n)\leq \frac{(4h^{1/2} k\alpha^{1/k})^{h}}{n^{h/2}}  \, .
\]

We provide the proof of <ref> in <ref> for completeness.
For completeness we include the proof from [4].

Let $S_h$ denote the set $\{1,2,\dots,h\}$. The probability event we are interested in is captured by two conditions: (i) $M$ containing $S_h$ and (ii) each hyperedge of $M$ either does not touch any vertex in $S_h$ or touches at least $2$ vertices in $S_h$. Thus,

\[
p(h,n)\leq\Pr_M[M\text{ satisfies (i) and (ii)}] \, .
\]

Now, let us denote the number of size $t$ $k$-uniform hypermatchings over $n$ vertices (assuming $tk\leq n$) as

\[
M_k(n,t)=\frac{n^{\underline{tk}}}{(k!)^t\cdot t!}
\]

where $n^{\underline{tk}}=n\cdot(n-1)\cdots(n-tk+1)$ denotes the downward factorial. Next, let $u$ be the number of hyperedges that touch $S_h$ and use $u$ to partition the probability space. Observe that due to condition (ii), $u$ only takes value within $h/k$ to $h/2$. Thus, the number of $M$ satisfying (i) and (ii) is at most

\begin{equation}\label{eq:matching 1}
\sum_{u=h/k}^{h/2}\binom{n-h}{uk-h}\cdot M_k(uk,u)\cdot M_k(n-uk,\alpha n-u)
\end{equation}

where $\binom{n-h}{uk-h}$ is the set of vertices outside $S_h$ that are touched by the hyperedges that touch $S_h$, $M(uk,u)$ counts the number of size $u$ $k$-uniform hypermatchings that touch $S_h$, and $M(n-uk,\alpha n-u)$ counts the number of ways to choose the remaining part (that does not touch $S_h$) of the $k$-uniform hypermatching.

Note that <ref> is an overestimation. Nevertheless, in the following we show that this is sufficient for the desired upper bound.

\begin{align*}
p(h,n)&\leq\frac{\sum_{u=h/k}^{h/2}\binom{n-h}{uk-h}\cdot M_k(uk,u)\cdot M_k(n-uk,\alpha n-u)}{M_k(n,\alpha n)}\\
&\leq\sum_{u=h/k}^{h/2}\frac{n^{uk-h}}{(uk-h)!}\cdot\frac{\frac{(uk)!}{(k!)^u(u!)}\cdot\frac{n^{\underline{k(\alpha n-u)}}}{(k!)^{\alpha n-u}(\alpha n-u)!}}{\frac{n^{\underline{\alpha kn}}}{(k!)^{\alpha n}(\alpha n!)}}\\
&\leq\sum_{u=h/k}^{h/2}\frac{(uk)!}{(uk-h)!}\cdot\frac{n^{uk-h}\cdot n^{\underline{\alpha kn-uk}}}{n^{\underline{\alpha kn}}}\cdot\frac{(\alpha n)!}{(\alpha n-u)!u!}\\
&\leq\sum_{u=h/k}^{h/2}(uk)^h\cdot\left(\frac{1}{1-\alpha k}\right)^{uk}\cdot\frac{1}{n^h}\cdot\frac{(\alpha n)^u}{u!} \,
\intertext{As $\alpha k\leq1/100$, the equation can be further simplified as follows.}
&\leq \frac{(4h^{1/2} k\alpha^{1/k})^{h}}{n^{h/2}} \, .
\end{align*}

This completes the proof of <ref>

The following lemma is an immediate corollary of <ref> and will be useful later in the proof of <ref>.

Suppose $k,q\geq 2$, $\delta\in(0,1/2)$, and $C>0$. Then, there exist $\alpha_0 = \alpha_0(k,q)$ and $\tau_0 = \tau_0(C, k)$ such that for every $\alpha\in(0, \alpha_0]$ and $\tau\in(0, \tau_0 /\alpha^{4/k})$, it follows that for every sufficiently large $n$ and $4\log(3/\delta)\leq s\leq \tau n$, $m = \alpha n$,

\[
\delta^{2h}     &  ,\ 1\leq h\leq s \\
2^{-h/2}    & ,\ s<h\leq km \\
0 & ,\ h > km
\end{array}\right. \, .
\]

\[
\sum_{h=2}^{n}p(h,k,m,n)U_{C,s}(h)\leq\delta^2 \, .
\]