The most obvious spectral property of a truly random function $\boldsymbol{f} : \{1,1\}^n \to \{1,1\}$ is that all of its Fourier coefficients are very small (as we saw in Exercise 5.8).
[...]


The most obvious spectral property of a truly random function $\boldsymbol{f} : \{1,1\}^n \to \{1,1\}$ is that all of its Fourier coefficients are very small (as we saw in Exercise 5.8). [...] 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 [...] 

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