pdf icon
Volume 9 (2013) Article 16 pp. 579-585
Guest Editors' Foreword

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.

June 10, 2013

Elchanan Mossel
Ryan O'Donnell
Guest Editors

Further resources:

Courses on analysis of Boolean functions:

Other recent and upcoming workshops and semesters on discrete analysis: Key "classical" papers: Further lectures, videos, surveys, and other writings:

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

Download article from ToC site:
[PDF (165K)]    [PS (458K)]    [PS.GZ (170K)]
[Source ZIP]
Keywords: foreword, special issue, Boolean special issue
ACM Classification: G.2, G.3, F.1.3
AMS Classification: 68Q87

[Plain Text Abstract]