that $$\begin{aligned}
f(x) = f'(x)\wedge 
{\left(g(x)\oplus \bigoplus_{i\in S_k}^{\phantom{a}} x_i\right)},\end{aligned}$$ where $g\colon\zoon\to\zoo$ is the function such that $g(x)=1$ if and only if $b_k$ is the $(k+1)$st least significant bit of the integer $\sum_{i=0}^{k-1} 2^i
\sum_{j\in S_i} x_j.$ As a result, Lemma \[lem:random-xor\] shows that $\Prob[E_2]\geq 1-2^{-n+H(\epsilon)n +2\zeta n}.$ This bound, along with (\[eqn:inductive-assumption\]), settles (\[eqn:claim-rephrased\]) and thereby completes the induction.

We have reached the main result of this section.

\[thm:RESHETO\] Fix an integer $k\geq0$ and reals $\epsilon,\zeta\in(0,1/2).$ Choose integers $w_1,w_2,\dots,w_n$ uniformly at random from $\{0,1,\dots,2^{k+1}-1\}.$ For $s\in\ZZ,$ define $f_s\colon\zoon\to\zoo$ by $$\begin{aligned}
f_s(x)=1\qquad\Leftrightarrow\qquad \sum_{i=1}^n w_ix_i\equiv 
s\pmod{2^{k+1}}.
\label{eqn:f_s}\end{aligned}$$ Then with probability at least $1-(k+1)2^{-n+H(\epsilon)n+2\zeta n+k+1}$ over the choice of $w_1,w_2,\dots,w_n,$ one has $$\begin{aligned}
&\ABS{\hat f_s(T) - \frac{\delta_{T,{\varnothing}}}{2^{k+1}}} \leq
2^{-\zeta n}, 
        &&\abs{T}\leq \epsilon n, \quad s\in\ZZ.\end{aligned}$$

In view of the modular counting in (\[eqn:f\_s\]), it suffices to prove the theorem for $s\in\{0,1,\dots,2^{k+1}-1\}.$ The functions $f_s$ have the following equivalent definition: pick sets $S_0,S_1,\dots,S_k\in\Pcal(\oneton)$ uniformly at random and define $$\begin{aligned}
f_s(x)=1\qquad\Leftrightarrow\qquad \sum_{i=0}^k2^i\sum_{j\in
S_i} x_j \equiv s\pmod{2^{k+1}}.\end{aligned}$$ The proof is now complete by Lemma \[lem:resheto\] and the union bound over $s.$

Zeroing out Correlations by a Change of Distribution {#sec:change-of-distribution}
====================================================

Recall the setting of the previous section, where we fixed integers $w_1,w_2,\dots,w_n$ at random from 