The lecture notes from the Barbados Workshop on Computational Complexity, organized by Denis Thérien and presented by Ryan O'Donnell, cover a series of topics in the analysis of boolean functions. The notes are divided into several sections, each focusing on different aspects of boolean function analysis and its applications. 1. **Linearity Testing and Arrow's Theorem**: - **Fourier Expansion**: The notes introduce the Fourier expansion of boolean functions, which expresses a function as a sum of multilinear polynomials over the Fourier basis. This expansion is crucial for understanding the combinatorial properties of boolean functions. - **Blum-Luby-Rubinfeld (BLR) Linearity Test**: The BLR test is a method to determine if a boolean function is close to being linear. The notes provide a proof of the soundness of the BLR test and discuss its implications. - **Voting and Influence**: The notes explore the connection between boolean functions and voting schemes, including the concept of rational outcomes and Arrow's impossibility theorem. A robust version of Arrow's theorem due to Gil Kalai is discussed, which relates the probability of rational outcomes to the noise stability of the function. 2. **Noise Stability and Small Set Expansion**: - **Sheppard’s Formula and $\mathbf{Stab}_\rho(\mathbf{MAJ})$**: The notes derive Sheppard's formula for the noise stability of the majority function and show that it converges to $1 - \frac{2}{\pi} \arccos(\rho)$ as $n \to \infty$. - **The Noisy Hypercube Graph**: The notes introduce the noisy hypercube graph, where edges are weighted by the probability of generating correlated strings. The Majority Is Stablest theorem and the Small Set Expansion theorem are discussed, highlighting the relationship between noise stability and small set expansion. - **Bonami's Lemma**: The notes present Bonami's lemma, which states that low-degree multilinear polynomials of Rademacher random variables are reasonable random variables. This lemma is used to bound the expectation of these polynomials. 3. **KKL and Quasirandomness**: - The notes cover the Kahn-Kalai-Linial (KKL) theorem, which states that any boolean function with large influence on a small set must have a large Fourier coefficient on that set. The notes also discuss the concept of quasirandomness and its connection to boolean functions. 4. **CSPs and Hardness of Approximation**: - The notes introduce constraint satisfaction problems (CSPs) and discuss the hardness of approximation, including the Berry-Esséen theorem and its applications. 5. **Majority Is Stablest**: - The notes present the Majority Is Stablest theorem, which states that for a balanced boolean function, the sum of weights of edges within the set of density 1/2The lecture notes from the Barbados Workshop on Computational Complexity, organized by Denis Thérien and presented by Ryan O'Donnell, cover a series of topics in the analysis of boolean functions. The notes are divided into several sections, each focusing on different aspects of boolean function analysis and its applications. 1. **Linearity Testing and Arrow's Theorem**: - **Fourier Expansion**: The notes introduce the Fourier expansion of boolean functions, which expresses a function as a sum of multilinear polynomials over the Fourier basis. This expansion is crucial for understanding the combinatorial properties of boolean functions. - **Blum-Luby-Rubinfeld (BLR) Linearity Test**: The BLR test is a method to determine if a boolean function is close to being linear. The notes provide a proof of the soundness of the BLR test and discuss its implications. - **Voting and Influence**: The notes explore the connection between boolean functions and voting schemes, including the concept of rational outcomes and Arrow's impossibility theorem. A robust version of Arrow's theorem due to Gil Kalai is discussed, which relates the probability of rational outcomes to the noise stability of the function. 2. **Noise Stability and Small Set Expansion**: - **Sheppard’s Formula and $\mathbf{Stab}_\rho(\mathbf{MAJ})$**: The notes derive Sheppard's formula for the noise stability of the majority function and show that it converges to $1 - \frac{2}{\pi} \arccos(\rho)$ as $n \to \infty$. - **The Noisy Hypercube Graph**: The notes introduce the noisy hypercube graph, where edges are weighted by the probability of generating correlated strings. The Majority Is Stablest theorem and the Small Set Expansion theorem are discussed, highlighting the relationship between noise stability and small set expansion. - **Bonami's Lemma**: The notes present Bonami's lemma, which states that low-degree multilinear polynomials of Rademacher random variables are reasonable random variables. This lemma is used to bound the expectation of these polynomials. 3. **KKL and Quasirandomness**: - The notes cover the Kahn-Kalai-Linial (KKL) theorem, which states that any boolean function with large influence on a small set must have a large Fourier coefficient on that set. The notes also discuss the concept of quasirandomness and its connection to boolean functions. 4. **CSPs and Hardness of Approximation**: - The notes introduce constraint satisfaction problems (CSPs) and discuss the hardness of approximation, including the Berry-Esséen theorem and its applications. 5. **Majority Is Stablest**: - The notes present the Majority Is Stablest theorem, which states that for a balanced boolean function, the sum of weights of edges within the set of density 1/2