This graduate-level 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, the Goldreich-Levin algorithm, hardness of approximation, and 'sharp threshold' theorems for random graphs.
Inhaltsverzeichnis
1. Boolean functions and the Fourier expansion; 2. Basic concepts and social choice; 3. Spectral structure and learning; 4. DNF formulas and small-depth circuits; 5. Majority and threshold functions; 6. Pseudorandomness and F2-polynomials; 7. Property testing, PCPPs, and CSPs; 8. Generalized domains; 9. Basics of hypercontractivity; 10. Advanced hypercontractivity; 11. Gaussian space and invariance principles.
Klappentext
This graduate-level text gives a thorough overview of the analysis of Boolean functions, beginning with the most basic definitions and proceeding to advanced topics.