Some announcements: First, the book serialization will start back up again on Monday; stay tuned. Second, 22 videos from the Simons Symposium are now available. Third, there will be a special issue of Theory of Computing devoted to analysis of Boolean functions (see below announcement); please submit your good papers!
The journal Theory of Computing is soliciting papers for a special issue dedicated to the Analysis of Boolean Functions. This topic plays a crucial role in the theory of computing and has significant applications to other areas of mathematics, to statistical physics, and to economics.
In the past decade, several important themes have emerged in the analysis of Boolean functions, including the dichotomy between “juntas” and “low-influence” functions, noise stability and sensitivity, Gaussian analysis, probabilistic invariance principles, small-set expansion, and regularity lemmas. Progress in the field has led to several breakthrough applications over the last few years, in areas such as inapproximability, communication complexity, threshold phenomena, extremal combinatorics, and percolation theory.
The idea of this special issue was conceived at the Simons Symposium “Analysis of Boolean Functions“ held at Caneel Bay, US Virgin Islands, February 5-11, 2012. This workshop joins a number of recent workshops bringing together researchers in the area (1, 2, 3, 4, 5, 6). Further activity is planned for fall 2013 when the Simons Institute will devote a special semester to Real Analysis in Computer Science.
Please indicate your intention to submit a paper for this special issue in advance in an email to special issue editor Ryan O’Donnell, odon… [at] cs.cmu.edu. To submit a paper for the special issue, please follow the
standard procedures for submission to ToC and indicate in the cover letter that you would like the paper considered for the special issue. Write “ToC submission BOOLEAN” in the Subject line. The submission deadline is
December 1, 2012 January 15, 2013.
Elchanan Mossel and Ryan O’Donnell
Special Issue editors
Editor, Theory of Computing