Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 168 / 3 / i / Solution

A Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is $(\epsilon ,p,r)$-quasirandom when, for every $J\subseteq [n]$ with $|J|\le r$ and every $u\in \{0,1{\}}^J$,

The regularity lemma for Boolean functions states that for every $\epsilon ,p,r,\delta$ there is $T$ such that every Boolean function has a set $J$, $|J|\le T$, for which a ${\mu }_p$-random $u\in \{0,1{\}}^J$ satisfiesHere $f_u$ is the restriction obtained by fixing the coordinates in $J$ to $u$.

Solved by gpt-5.6-sol high.