## Fourier Analysis of Boolean Functions under Random Restriction

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

Tagged with: , ,
Posted in Theory