Analysis of Boolean Functions
(2021)cite arxiv:2105.10386Comment: First edition originally published April 2014, in hardcover book format by Cambridge University Press, and electronically on the author's website. This arXiv version corrects 100+ typos and errors, but is otherwise essentially the same.Abstract
The subject of this textbook is the analysis of Boolean functions. Roughly
speaking, this refers to studying Boolean functions $f : \0,1\^n \0,1\$
via their Fourier expansion and other analytic means. Boolean functions are
perhaps the most basic object of study in theoretical computer science, and
Fourier analysis has become an indispensable tool in the field. The topic has
also played a key role in several other areas of mathematics, from
combinatorics, random graph theory, and statistical physics, to Gaussian
geometry, metric/Banach spaces, and social choice theory.
The intent of this book is both to develop the foundations of the field and
to give a wide (though far from exhaustive) overview of its applications. Each
chapter ends with a "highlight" showing the power of analysis of Boolean
functions in different subject areas: property testing, social choice,
cryptography, circuit complexity, learning theory, pseudorandomness, hardness
of approximation, concrete complexity, and random graph theory.
The book can be used as a reference for working researchers or as the basis
of a one-semester graduate-level course. The author has twice taught such a
course at Carnegie Mellon University, attended mainly by graduate students in
computer science and mathematics but also by advanced undergraduates, postdocs,
and researchers in adjacent fields. In both years most of Chapters 1-5 and 7
were covered, along with parts of Chapters 6, 8, 9, and 11, and some additional
material on additive combinatorics. Nearly 500 exercises are provided at the
ends of the book's chapters.
Description
[2105.10386] Analysis of Boolean Functions
