[...]


[...] The history of the Hypercontractivity Theorem is complicated. [...] The origins of the orthogonal decomposition described in Section 3 date back to the work of Hoeffding [Hoe48] (see also [vMis47]). [...] The study of property testing was initiated by Rubinfeld and Sudan [RS96] and significantly expanded by Goldreich, Goldwasser, and Ron [GGR98]; the stricter notion of local testability was introduced (in the context of errorcorrecting codes) by Friedl and Sudan [FS95]. The first local tester for dictatorship was given by Bellare, Goldreich, and Sudan [BGS95,BGS98] (as [...] The ${\mathbb F}_2$polynomial representation of a boolean function $f$ is often called its algebraic normal form. It seems to have first been explicitly introduced by Zhegalkin in 1927 [Zhe27]. [...] Chow’s Theorem was proved by independently by Chow [Cho61] and by Tannenbaum [Tan61] in 1961; see also [Elg61]. [...] [...] The fact that the Fourier characters $\chi_{\gamma} : {\mathbb F}_2^n \to \{1,1\}$ form a group isomorphic to ${\mathbb F}_2^n$ is not a coincidence; the analogous result holds for any finite abelian group and is a special case of the theory of Pontryagin duality in harmonic analysis. We will see further examples of this in Chapter [...] The mathematical study of social choice began in earnest in the late 1940s; see Riker [Rik61] for an early survey or the compilation [BGR09] for some modern results. [...] 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. [...] 

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