Fourier representation

General

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 [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].

The set of functions [math]\{\underset{i\in S}{\prod}x_{i}|S\subseteq\{1,2,...,n\}\}[/math] is an orthonormal basis of the vector space of all boolean functions [math]f:\{-1,1\}^{n}\to\mathbb{R}[/math] with the inner product:

[math]\lt f,g\gt =2^{-n}\underset{x\in\{-1,1\}^{n}}{\sum}f(x)g(x)=\underset{x\sim\{-1,1\}^{n}}{\mathbb{E}}[f(x)g(x)][/math]
Therefore, Parseval's and Plancherel's identities holds:

[math]\lt f,f\gt =\underset{S\in\{1,..,n\}}{\sum}\hat{f}(S)^{2}[/math]

[math]\lt f,g\gt =\underset{S\in\{1,..,n\}}{\sum}\hat{f}(S)\hat{g}(S)[/math]

TODO: Parseval

TODO: The Fourier weight at depth k is... The Fourier weight at depth >= k is...

The Fourier Weight

For [math]f:\{-1,1\}^{n}\to\mathbb{R}[/math] and [math]0\leq k\leq n[/math] the Fourier weight of [math]f[/math] at degree [math]k[/math] (or depht [math]k[/math]) is:

[math]W^{k}[f]=\underset{S\subseteq\{1,...n\},|s|=k}{\sum\hat{f}(S)^{2}}[/math]

For [math]f:\{-1,1\}^{n}\to\{-1,1\}[/math]:

[math]W^{k}[f]=\underset{S\sim2^{\{1,...n\}}}{\mathbb{P}[|S|=k]}[/math]

Properties

• TODO. Start off with relation between Fourier weight and other complexity measures such as circuit size, sensitivity, decision tree depth.