Analysis of Boolean functions is an area focused on the study of Boolean-valued functions on the hypercube {0,1}ⁿ, which has been applied very successfully in several areas in TCS and discrete mathematics. Initiated with the landmark result of Kahn, Kalai and Linial, results in analysis of Boolean functions have played crucial roles in applications in social choice, circuit complexity, communication complexity, learning theory, hardness of approximation, cryptography, threshold phenomena, pseudo-randomness, property testing, query complexity, quantum computing, random graph theory, combinatorics, and geometry. In fact, the interaction between these areas and analysis is so close that often the applications that one has in mind (coming say, from hardness of approximation or quantum computing) raise certain conjectures about Boolean functions, which then lead to further developments on the analytical side. In particular, key concepts such as juntas (functions that depend on a small number of coordinates), noise stability, influences, hypercontractivity, the invariance principle, and random restrictions are central both in analysis as well as in TCS.

Recently, there has been a surge of activity extending the classical study of Boolean functions to other contexts. Most relevant to us are (a) taking this study "beyond the Boolean hypercube’’, which refers to the study of Boolean functions over domains other than the hypercube, and (b) taking this study "inside the Boolean hypercube", which refers to the notion that functions over the hypercube may be viewed as multi-linear functions, and are thus naturally extended to the solid cube [0,1]ⁿ or to Gaussian space. These two branches of study have led to an impressive array of applications, both in the core of TCS as well as in adjacent areas.

The program will bring together researchers from different areas, with the aim of introducing promising new techniques to the TCS toolbox and seeking new connections between TCS, analysis of Boolean functions, and adjacent areas.

Motivating open questions:
1. Fourier analysis was useful to solve the 2-2 conjecture. What are the next steps needed to solve the Unique Games Conjecture?
2. Can high dimensional expanders (HDX) give a robust / versatile general framework for Fourier analysis?
3. The sliding scale conjecture in PCPs.
4. Breaking current barriers in circuit lower bounds (e.g., AC 0 with parity gates)
5. Small space derandomization.
6. Structural conjectures in computational complexity: log-rank conjecture, Mansour’s conjecture, Fourier-Entropy-Influence conjecture, Aaronson-Ambainis conjecture.

Click here to subscribe to our news and events to learn more about this and other events.

Organizers
Nikhil Bansal (University of Michigan), Irit Dinur (Weizmann Institute), Ronen Eldan (Microsoft Research), Jacob Fox (Stanford University), Shachar Lovett (UC San Diego), Dor Minzer (Massachusetts Institute of Technology), Sarah Peluse (University of Michigan), Avishay Tal (UC Berkeley)

Long-Term Participants (tentative, including organizers)
Nima Anari (Stanford University), Nikhil Bansal (University of Michigan), Jop Briët (CWI), David Conlon (California Institute of Technology), Irit Dinur (Weizmann Institute), Ronen Eldan (Microsoft Research), Yuval Filmus (Technion Israel Institute of Technology), Jacob Fox (Stanford University), Johan Håstad (KTH Royal Institute of Technology), Hamed Hatami (McGill University), Gil Kalai (Hebrew University of Jerusalem; IDC Herzliya), Tali Kaufman (Bar-Ilan University), James R. Lee (University of Washington), Noam Lifshitz (Hebrew University of Jerusalem), Shachar Lovett (UC San Diego), Frederick Manners (UC San Diego), Raghu Meka (UCLA), Dor Minzer (Massachusetts Institute of Technology), Dana Moshkovitz (University of Texas at Austin), Ryan O'Donnell (Carnegie Mellon University), Sarah Peluse (University of Michigan), Avishay Tal (UC Berkeley), Madhur Tulsiani (Toyota Technological Institute at Chicago)