= Solution
A <Boolean function> $f:\{0,1\}^n\to\{0,1\}$ is <quasirandom Boolean function>[$(\varepsilon,p,r)$-quasirandom] when, for every $J\subseteq[n]$ with $|J|\leq r$ and every $u\in\{0,1\}^J$,
$$
\left|\mathbb E_{\mu_p}[f\mid x|_J=u]-\mathbb E_{\mu_p}f\right|\leq\varepsilon.
$$
The <regularity lemma for Boolean functions> states that for every $\varepsilon,p,r,\delta$ there is $T$ such that every Boolean function has a set $J$, $|J|\leq T$, for which a $\mu_p$-random $u\in\{0,1\}^J$ satisfies
$$
\mathbb P_u[f_u\text{ is }(\varepsilon,p,r)\text{-quasirandom}]\geq1-\delta.
$$
Here $f_u$ is the restriction obtained by fixing the coordinates in $J$ to $u$.
Solved by gpt-5.6-sol high.
Back to article page
