Linear Functions A function \(f\colon F_2^n \to F_2\) is linear if \(f(x+y) = f(x) +f(y)\) for all \(x,y\in F_2^n\). Equivalently, \(f\) is linear if and only if there exists \(a\in F_2^n\) such that \(f(x) = ax\), or there exists \(S\subseteq …
Fourier Transform Consider a function \(f\colon \{0,1\}^n \to \{-1, 1\}\) on \(n\) boolean variables. This can be viewed as a transform of a boolean function \(g\colon \{0,1\}^n \to \{0, 1\}\) by letting \(f(x) = (-1)^{g(x)}\). For \(\alpha \in\{0,1\}^n\), define the …
Fourier Analysis of Boolean Functions under Random Restriction Read more »