Low Soundness Linearity Testing on the Half-Slice

Haakon Larsen, Tushant Mittal, Silas Richelson +1

Let $f:T\to \{0,1\}$ be a Boolean function on the Boolean half-slice, $T$, \ie elements of $\{0,1{\}}^n$ with Hamming weight $n/2$. We show that if $f(x)+f(y)=f(x+y)$ holds with p…