A function \(f\colon \{0,1\}^n\to \{0,1\}\) is a dictator function if there exists \(i\in [n]\) such that \(f(x) = x_i\). That is, the function is completely determined by its \(i\)-th input. A function \(f\colon \{0,1\}^n\to \{ \pm 1\}\) is a dictator …
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 »