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).

## Leave a Reply