The Fourier expansion for realvalued boolean functions dates back to Walsh [Wal23] who introduced a complete orthonormal basis for $L^2([0,1])$ consisting of $\pm 1$valued functions, constant on dyadic intervals.
[...]


The Fourier expansion for realvalued boolean functions dates back to Walsh [Wal23] who introduced a complete orthonormal basis for $L^2([0,1])$ consisting of $\pm 1$valued functions, constant on dyadic intervals. [...] [...] In linear algebra there are two equivalent definitions of what it means for a function to be linear: Definition 29 A function $f : {\mathbb F}_2^n \to {\mathbb F}_2$ is linear if either of the following equivalent conditions hold: $f(x+y) = f(x) + f(y)$ for all $x, y \in {\mathbb [...] For variety’s sake, in this section we write the Hamming cube as ${\mathbb F}_2^n$ rather than $\{1,1\}^n$. In developing the Fourier expansion, we have generalized from booleanvalued boolean functions $f : {\mathbb F}_2^n \to \{1,1\}$ to realvalued boolean functions $f : {\mathbb F}_2^n \to {\mathbb R}$. Booleanvalued functions arise more often in [...] As we have seen, the Fourier expansion of $f : \{1,1\}^n \to {\mathbb R}$ can be thought of as the representation of $f$ over the orthonormal basis of parity functions $(\chi_S)_{S \subseteq [n]}$. In this basis, $f$ has $2^n$ “coordinates”, and these are precisely the Fourier coefficients of $f$. The “coordinate” of $f$ [...] For $x \in \{1,1\}^n$, the number $\chi_S(x) = \prod_{i \in S} x_i$ is in $\{1,1\}$. Thus $\chi_S : \{1,1\}^n \to \{1,1\}$ is a boolean function; it computes the logical parity, or exclusiveor (XOR), of the bits $(x_i)_{i \in S}$. The parity functions play a special role in the analysis of boolean functions: [...] The Fourier expansion of a boolean function $f : \{1,1\}^n \to \{1,1\}$ is simply its representation as a real, multilinear polynomial. (Multilinear means that no variable $x_i$ appears squared, cubed, etc.) For example, suppose $n = 2$ and $f = {\textstyle \min_2}$, the “minimum” function on $2$ bits: [...] This is a book about boolean functions, \begin{equation*} f : \{0,1\}^n \to \{0,1\}. \end{equation*} Here $f$ maps each length$n$ binary vector, or string, into a single binary value, or bit. Boolean functions arise in many areas of computer science and mathematics. Here are some examples: [...] 

Copyright © 2014 Ryan O'Donnell  All Rights Reserved 
Recent comments