zbMATH — the first resource for mathematics

Analysis of Boolean functions. (English) Zbl 1336.94096
Cambridge: Cambridge University Press (ISBN 978-1-107-03832-5/hbk; 978-1-107-47154-2/pbk; 978-1-139-81478-2/ebook). xx, 423 p. (2014).
The book gives a thorough overview of the analysis of Boolean functions via Fourier transform and other analytic methods. It addresses graduate students and researchers in computer science and related mathematical fields, and can be used as the basis of a one-semester graduate course. The book includes in total approximately 500 exercises, given at the end of each chapter. Every chapter also ends with a “highlight”. As highlight in the first chapter, where Fourier expansion is introduced as a basic tool for the analysis of Boolean functions and some properties such as Parseval’s Theorem are collected, a linearity test is discussed. The highlight in Chapter 2, where some concepts motivated using the language of social choice are introduced, is a Fourier-based proof of Arrow’s Theorem; G. Kalai [Adv. Appl. Math. 29, No. 3, 412–426 (2002; Zbl 1038.91027)]. Other chapters deal with disjunctive normal form representation, property testing, or pseudorandomness. In total there are 11 chapters also giving a wide overview of the importance of Boolean functions in applications in property testing, social choice, cryptography, circuit complexity, learning theory, hardness of approximation, concrete complexity, pseudorandomness, random graph theory.

94D10 Boolean functions
94-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory
06-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to ordered structures
94A60 Cryptography
94C11 Switching theory, applications of Boolean algebras to circuits and networks
06E30 Boolean functions
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91B14 Social choice
Full Text: DOI