Pointwise correctness under less than quarter noise

If another linear function $m\mathrm{\ne }\mathrm{\ell }$ had distance less than $1\mathrm{/}4$ from $f$, each point where $\mathrm{\ell }\mathrm{\ne }m$ would be a disagreement of at least one of them with $f$. Counting these points gives $\mathrm{dist}(\mathrm{\ell },m)\le \mathrm{dist}(\mathrm{\ell },f)+\mathrm{dist}(f,m)<1\mathrm{/}2$, contradicting their exact half-distance. Thus the nearby linear function is unique.

Let $E=\{z:f(z)\mathrm{\ne }\mathrm{\ell }(z)\}$, of size $\delta 2^n$. For fixed $x$, both $y$ and $x+y$ are uniform, since translation is a bijection. Thus each event $y\in E$, $x+y\in E$ has probability $\delta$. The indicator of their union is at most their indicator sum, so with probability at least $1-2\delta$ neither event occurs. Independence of these two locations is unnecessary.

On that event the output is $\mathrm{\ell }(y)+\mathrm{\ell }(x+y)=\mathrm{\ell }(x)$ by linearity. The sampling and calls are exactly those of the corrector. For $x=0$, the two queried values are identical and their sum is always zero, which equals $\mathrm{\ell }(0)$. For $n=0$, the hypothesis forces $\delta =0$ on the singleton cube; the same algorithm uses zero random bits. Zero noise gives success one for every point; the excluded endpoint $\delta =1\mathrm{/}4$ would give only the lower bound one half.