The Boolean function $f : \{0,1\}^n\to\{0,1\}$ is one of the most fundamental objects in theoretical computer science. The field of Analysis of Boolean Functions seeks to understand Boolean functions via their Fourier transform and other analytic methods. This field has seen major developments in the 25 years since the watershed paper of Kahn, Kalai, and Linial [KKL88]. It is now an indispensable tool in the theory of computing, with applications in areas as diverse as algorithmic economics [BL85], average-case complexity [O'D04], circuit complexity [LMN93], coding theory [KL95], communication complexity [GKKRW08], computational geometry [MNP07], cryptography [Sie84], derandomization [NN93], genetic algorithms [HW04], inapproximability [Has01], learning theory [Man94], noisy communication [GKS08], property testing [BCHKS96], and quantum computing [BRW08]. Moreover, this area of research has proved to have significant applications in other areas of mathematics that are not as obviously connected with Boolean functions: additive combinatorics [Gre04], Banach spaces [BMW86], extremal combinatorics [ADFS04], Gaussian geometry [Bob97], metric space embeddings [KN06], social choice [Kal02], statistical physics [SS10], and threshold phenomena of random graphs [FriB99].

Over the last decade, a number of powerful themes have emerged in the analysis of Boolean functions: the dichotomy between "juntas" and functions with small influences; noise sensitivity/stability; the "small-set expansion" of the Boolean cube; the role of Gaussian analysis/geometry; probabilistic invariance principles; and regularity lemmas. This deepening understanding of the field has led to quite a few exciting developments in the last five years. To cite just a few examples:

• In the field of inapproximability, two recent STOC "Best Papers": Raghavendra's theory of CSP approximability [Rag10] and Chan's breakthrough on the NP-hardness of Max-kCSP [Cha12].
• In Gaussian geometry, a new proof of Borell's Isoperimetric Inequality [DMN12].
• The developments in percolation theory due to Garban, Pete, and Schramm [GPS10].
• Hatami's characterization of monotone set properties without sharp thresholds [Hat10].
• In concrete complexity, Kane's near resolution of the Gotsman-Linial Conjecture [Kan12].
• In additive combinatorics, Sanders's Quasipolynomial Freiman-Ruzsa Theorem [San12].

In light of these developments, Theory of Computing is devoting a special issue to the field of analysis of Boolean functions. The idea for this special issue was conceived at the Simons Symposium Analysis of Boolean Functions: New Directions and Application held at Caneel Bay, US Virgin Islands, February 5-11, 2012. Submissions were solicited in late 2012; the papers appearing were selected from those submitted, after reviews following the stringent standards of Theory of Computing. The papers will be released individually in upcoming months.

We thank the authors of these papers for their contributions, and the anonymous reviewers for their meticulous and timely work. We would also like to thank Laci Babai, Oded Regev, and Ronald de Wolf for their editorial efforts.

Courses on analysis of Boolean functions:

• Kindler '03
• Kalai '04
• Linial '05
• Dinur and Friedgut '05
• Mossel '05
• O'Donnell '07
• Regev '07
• van Melkebeek '08
• Pansu '10
• Sanders '10
• Gubinelli '11
• Hatami '11
• Grigorescu, Perkins, Piliouras, and Reyzin '12
• Sudakov '12

• Noise Sensitivity and Percolation (Clay Mathematics Institute summer school)
• Analysis and Geometry of Boolean Threshold Functions (Center for Computational Intractability)
• Discrete Harmonic Analysis (Isaac Newton Institute)
• Fourier Entropy-Influence (Winter School, Marne-la-Vallée)
• Analysis of Boolean Functions (Barbados Workshop on Computational Complexity)
• Real Analysis in Computer Science (Simons Institute fall 2013 program)
• Analysis of Boolean Functions: New directions and applications (2012, 2014)

• Étude des coefficients de Fourier des fonctions de L^p(G) (Bonami '70)
• Collective coin flipping, robust voting schemes and minima of Banzhaf values (Ben Or--Linial '85)
• The influence of variables on Boolean functions (Kahn--Kalai--Linial '88)
• Constant depth circuits, Fourier transform, and learnability (Linial--Mansour--Nisan '89); see also [FJS'91]
• Learning decision trees using the Fourier spectrum (Kushilevitz--Mansour '91); see also A hard-core predicate for all one-way functions (Goldreich--Levin '89)
• Spectral properties of threshold functions (Gotsman--Linial '94)
• On Russo's approximate zero-one law (Talagrand '94)
• Linearity testing in characteristic two (Bellare--Coppersmith--Hastad--Kiwi--Sudan '95)
• The Harmonic sieve: a novel application of Fourier analysis to machine learning theory and practice (Jackson '95)
• Every monotone graph property has a sharp threshold (Friedgut--Kalai '96)
• How much are increasing sets positively correlated? (Talagrand '96)
• Some optimal inapproximability results (Hastad '97)
• Noise sensitivity of Boolean functions and applications to percolation (Benjamini--Kalai--Schramm '98)
• Sharp thresholds of graph properties, and the k-sat problem (Friegut(--Bourgain) '99)

• Stefankovic's master's thesis
• Kalai and Safra's survey
• de Wolf's survey in Theory of Computing
• O'Donnell's survey
• Videos from the Isaac Newton Institute workshop
• Tan's notes on the Barbados lectures
• Simons Symposium lectures
• O'Donnell's book/blog, Analysis of boolean functions
• Garban and Steif's monograph
• Video lectures by O'Donnell
• Open problem compendium

List of papers currently accepted for publication in the Special Issue

• Making polynomials robust to noise, by Alexander Sherstov
• Note on low-depth monotone functions, by Daniel Kane
• Hypercontractivity via the entropy method, by Eric Blais and Li-Yang Tan
• Tight Bounds for Monotone Switching Networks via Fourier Analysis, by Siu Man Chan and Aaron Potechin

Table of Contents