integer $k$ with $0\leq k\leq n/2.$ For a set $S\subseteq\oneton,$ define $F_S\colon\zoon\to\zoo$ by $$\begin{aligned}
F_S(x) = f(x) \wedge \left(g(x)\oplus \bigoplus_{i\in S}
x_i\right).\end{aligned}$$ Fix a real $\zeta >0.$ Then with probability at least $1-2^{-n+H(k/n)n +2\zeta n}$ over a uniformly random choice of $S\in\Pcal(\oneton),$ one has $$\begin{aligned}
\ABS{\hat F_S(T) - \frac12 \hat f(T)}  
  \leq 2^{-\zeta n-1}, && |T|\leq k.\end{aligned}$$

Define $\phi\colon\zoon\to[-1/2,1/2]$ by $\phi(x)=f(x)g(x) - \frac12 f(x).$ Define $\Scal\subseteq\Pcal(\oneton)$ by $\Scal = \{ S : \abs{\hat \phi(S)} \geq 2^{-\zeta n-1}\}.$ By Parseval’s identity (\[eqn:parsevals\]), $$\begin{aligned}
\abs{\Scal} \leq 4^{\zeta n}.
\label{eqn:A-B-bound}\end{aligned}$$ Since $F_S(x) = \frac12 f(x) + (-1)^{\sum_{i\in S}x_i}\phi(x),$ we have $$\begin{aligned}
\ABS{\hat F_S(T) - \frac12 \hat f(T)}
 =\abs{\hat \phi(S\oplus T)},
&&S,T\subseteq\oneton.
\label{eqn:F-S-spectrum}\end{aligned}$$

For a uniformly random $S\in\Pcal(\oneton),$ the set $\{S\oplus
T: \abs{T}\leq k\}$ contains any fixed element of $\Pcal(\oneton)$ with probability $2^{-n}\sum_{i=0}^k{n\choose i}.$ By the union bound, we infer that $$\begin{aligned}
\Prob_S[\{S\oplus T:\abs{T}\leq k\}\cap \Scal \ne
\varnothing]
\leq \abs{\Scal}\,2^{-n}\sum_{i=0}^k {n\choose i},\end{aligned}$$ which in view of (\[eqn:entropy-bound\]) and (\[eqn:A-B-bound\]) is bounded from above by $2^{-n+H(k/n)n+2\zeta n}.$ This observation, along with (\[eqn:F-S-spectrum\]), completes the proof.

Using Lemma \[lem:random-xor\] and induction, we now obtain a key intermediate result.

\[lem:resheto\] Fix an integer $k\geq0$ and reals $\epsilon,\zeta\in(0,1/2).$ Choose sets $S_0,S_1,\dots,S_k\in\Pcal(\oneton)$ uniformly at random. Fix any integer $s$ 