Chapter 1 notes

The Fourier expansion for real-valued 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.

Using the ordering introduced by Paley [Pal32], the $n$th Walsh basis function $w_n : [0,1] \to \{-1,1\}$ is defined by $w_n(x) = \prod_{i=0}^{\infty}r_i(x)^{n_i}$, where $n = \sum_{i=0}^{\infty} n_i 2^i$ and $r_i(x)$ (the “$i$th Rademacher function at $x$”) is defined to be $(-1)^{x_i}$, with $x = \sum_{i=0}^\infty x_i 2^{-(i+1)}$ for non-dyadic $x \in [0,1]$. Walsh’s interest was in comparing and contrasting the properties of this basis with the usual basis of trigonometric polynomials and also Haar’s basis [Haa10].

The first major study of the Walsh functions came in the remarkable paper of Paley [Pal32], which included strong results on the $L^p$-norms of truncations of Walsh series. Sadly, Paley died in an avalanche one year later (at age 26) while skiing near Banff. The next major development in the study of Walsh series was conceptual, with Vilenkin [Vil47] and Fine [Fin49] independently suggesting the more natural viewpoint of the Walsh functions as characters of the discrete group ${\mathbb Z}_2^n$. There was significant subsequent work in the 1950s and 1960s, but it’s somewhat unnatural from our point of view because it relies fundamentally on ordering the Rademacher and Walsh functions according to binary expansions. Bonami [Bon68] seems to have been the first author to take our viewpoint, treating bits $x_1, x_2, x_3, \dots$ symmetrically and ordering Fourier characters $\chi_S$ according to $|S|$ rather than $\max(S)$. She also obtained the first hypercontractivity result for the boolean cube. This proved to be a crucial tool for analysis of boolean functions, as we will see in later chapters. For contemporaneous partial work along Bonami’s lines, see Kiener [Kie69]; for an early survey on Walsh series, see Balashov and Rubinshtein [BR73].

Turning to boolean functions and computer science, the idea of using boolean logic to study “switching functions” (as engineers originally called boolean functions) dates to the late 1930s and is usually credited to Nakashima [Nak35], Shannon [Sha37], and Shestakov [She38]. Muller [Mul54] seems to be the first to have used Fourier coefficients in the study of boolean functions; he mentions computing them while classifying all functions $f : \{0,1\}^4 \to \{0,1\}$ up to certain equivalences. The first publication devoted to boolean Fourier coefficients was by Ninomiya [Nin58], who expanded on Muller’s use of Fourier coefficients for the classification of boolean functions up to various isomorphisms. Golomb [Gol59] independently pursued the same project (his work is the content of Exercise 29); he was also the first to recognize the connection to Walsh series. The use of “Fourier–Walsh analysis” in the study of boolean functions quickly became well known in the early 1960s. Several symposia on applications of Walsh functions took place in the early 1970s, with Lechner’s 1971 monograph [Lec71] and Karpovsky’s 1976 book [Kar76] becoming the standard references. However the use of boolean analysis in theoretical computer science seemed to wane until 1988, when the outstanding work of Kahn, Kalai, and Linial [KKL88] ushered in a new area of sophistication.

The original analysis by Blum, Luby, and Rubinfeld for their linearity test was combinatorial; our proof of Theorem 31 is the elegant analytic one due to by Bellare, Coppersmith, Håstad, Kiwi, and Sudan [BCH+96]. These authors also gave additional analysis improving the results of Theorem 31 and Exercise 27. See also [KLX10] for further slight improvement. In Exercise 1, the sortedness function was introduced by Ambainis [Amb03,LLS06]; the hemi-icosahedron function was introduced by Kushilevitz [NW95]. The fast algorithm for computing the Fourier transform mentioned in Exercise 13 is due to Lechner [Lec63].

2 comments to Chapter 1 notes

Leave a Reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>