Difference between revisions of "Fourier representation"
(Created page with "== 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]}}...") |
m (→Definition) |
||
| Line 2: | Line 2: | ||
Every Boolean function <math>f:\{-1,1\}^n \to \{-1,1\}</math> may be uniquely written as a multivariate polynomial: | 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 | + | <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>. | where <math>\hat{f}_S</math> are real numbers called the '''Fourier coefficients''' of <math>f</math>. | ||
Revision as of 05:09, 2 October 2018
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 [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.
