Analysis of Boolean Functions

Boolean functions are perhaps the most basic objects of study in theoretical computer science. They also arise in digital-only areas of mathematics, including combinatorics, statistical physics, and mathematical social choice. The field of analysis of Boolean functions seeks to understand them via their Fourier transform and digital-only analytic methods. This text gives a thorough overview of the field, beginning with the most basic definitions and proceeding to advanced topics such as hypercontractivity and isoperimetry. Each chapter includes a 'highlight application' such as Arrow's theorem from economics, the Goldreich–Levin algorithm from cryptography/learning theory, Håstad's NP-hardness of approximation results, and 'sharp threshold' theorems for random graph properties. The book includes roughly 450 exercises and can be used as the basis of a one-semester graduate course. It should appeal to advanced undergraduates, graduate students and researchers in computer science theory and related mathematical fields.