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.

Reviewer: Wilfried Meidl (Linz)

##### MSC:

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 |