Project IV 2024-2025: Analysis of Boolean functions

Description

Imagine you are in a room with a light bulb that is controlled by many switches. Each switch can be either in an ‘on’ or ‘off’ position, and the combination of all these switches determines whether the light bulb is lit or not. Let's say you want to understand how this system works, and how the switches interact with each other. Natural questions could be:

• (Sensitivity) Which switch (or switches) has the most influence on the light? If you flip just one switch, does the light change? This is like asking which switch is the most sensitive in changing the state of the light bulb.

• (Monotonicity) If you turn on more switches, does the light always stay on, or can it go off?

The analysis of Boolean functions is essentially the study of switch configurations in an abstract setting. This has become an indispensable tool in many areas such as:

• Computer science (coding theory, complexity theory, cryptography etc.).

• Discrete mathematics (extremal and additive combinatorics) and number theory.

• Economics and political science (social choice theory).

• Functional analysis (geometry of Hilbert/Banach space).

• Statistical physics (percolation and other probability models).

The goal of this project is to explore various techniques in the study of Boolean functions (Fourier analysis on hypercubes, influence and noise stability, hypercontractivity, invariance principles, etc.) and how they may be applied in different problems.