Testing Boolean predicates

If a Boolean function $f\colon {0,1}^n \to {0,1}$ satisfies $f(x \oplus y) = f(x) \oplus f(y)$ w.p. $1–\epsilon$, then it is close to a function satisfying this condition for all $x,y$, a classical result in theoretical computer science known as “linearity testing”.

We prove a general theorem which includes as special cases linearity testing and other related results such as AND testing, Kalai’s quantitative Arrow’s theorem, and Friedgut and Regev’s result on almost intersecting families.

Joint work with Yaroslav Alekseev appearing in FOCS 2026 (under the title “Approximate Polymorphisms”).