Fourier representation
Definition
Every Boolean function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] may be uniquely written as a multivariate polynomial:
[math] f(x) = \sum_{S \subseteq 2^{[n]}} \hat{f}_S \prod_{i \in S} x_i [/math],
where [math]\hat{f}_S[/math] are real numbers called the Fourier coefficients of [math]f[/math].
TODO: Parseval
TODO: The Fourier weight at depth k is... The Fourier weight at depth >= k is...
Properties
- TODO. Start off with relation between Fourier weight and other complexity measures such as circuit size, sensitivity, decision tree depth.
