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 »