About
Analysis of Boolean functions is an area focused on the study of Boolean-valued functions on the hypercube {0,1}n, 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, pseudorandomness, 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 multilinear functions, and are thus naturally extended to the solid cube [0,1]n 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.
This program will bring together researchers from different areas, with the aim of introducing promising new techniques to the TCS toolbox and seeking new connections among 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.
