Analysis of Boolean Functions

Chow’s Theorem was proved by independently by Chow [Cho61] and by Tannenbaum [Tan61] in 1961; see also [Elg61]. The generalization to PTFs (Theorem 6) is due to Bruck [Bru90], as is Theorem 8 and Exercise 13. Theorems 2 and 7 are from [GL94] and may be called the Gotsman–Linial Theorems; this work also contains the Gotsman–Linial Conjecture and Exercise 11. The Conjecture Conjecture following Theorem 1 should be considered folklore. Corollary 11 was proved by Bruck and Smolensky [BS92]; they also essentially proved Theorem 10 (but see [SB91]). Exercise 13 is usually credited to Krause and Pudlák [KP97]. The upper bound in Exercise 4 is asymptotically sharp [Zue89]. Exercise 15 is from [OS08a].

Theorem 2.32 and Proposition 2.57, discussed in Section 2, were essentially proved by Titsworth in 1962 [Tit62] (see also [Tit63]). More precisely, Titsworth solved a version of the problem from Exercise 7. His motivation was in fact the construction of “interplanetary ranging systems” for measuring deep space distances; e.g. the distance from Earth to Venus. The connection between ranging systems and boolean functions was suggested by his advisor, Golomb. Titsworth [Tit62] was also the first to compute the Fourier expansion of $\mathrm{Maj}_n$. His approach involved generating functions and contour integration. Other approaches have used special properties of binomial coefficients [Bra87] or of Kravchuk polynomials [Kal02]. The asymptotics of $\mathbf{W}^{k}[\mathrm{Maj}_n]$ described in Section 3 may have first appeared in [Kal02], with the error bounds being from [O'D03]. Kravchuk polynomials were introduced in [Kra29].

The Berry–Esseen Theorem is due independently to Berry [Ber41] and Esseen [Ess42]. Shevtsova [She10a] has the record for the smallest known constant $B$ that works therein: $.56$, as mentioned in our theorem statement. The nonuniform version described in Exercise 32 is due to Bikelis [Bik66]. The multidimensional version Theorem 33 stated in Exercise 34 is due to Bentkus [Ben04]. Sheppard proved his formula in 1899 [She99]. The results of Theorem 15 may have appeared first in [O'D04,O'D03].

The Level-1 Inequality should probably be considered folklore; it was perhaps first published in [Tal96] and we have followed his proof. The first half of the $\frac{2}{\pi}$ Theorem is from [KKMO07]; the second half is from [MORS10]. The previous best closeness result for the FKN Theorem had $\delta/2$ in place of our $\delta/4$. That result was from [FKN02]; their proof (like ours) relies on having a separate proof of closeness $O(\delta)$. Kindler and Safra [KS02] (see also [Kin02]) gave a self-contained proof of the $\delta/2$ bound relying only on the Hoeffding bound. The result of Exercise 6 is from [KKMO07]; Exercise 40 was suggested by Servedio.

Peres’s Theorem was published in 2004 [Per04] but was mentioned by Benjamini, Kalai, and Schramm [BKS99], who proved the worse upper bound $O(\delta^{1/4})$. The proof we presented is a simplification due to Gopalan, and incorporates an idea of [DHK+10,HKM10a]. These latter two works are responsible for the best known bounds in the direction of the Gotsman–Linial Conjecture, mentioned at the end of Section 5 (in particular, for Exercise 43).