Analysis of Boolean Functions

This lecture introduces the Fourier expansion for Boolean functions, a foundational concept, and derives basic formulas relevant to its application in theoretical computer science.

This session explores probability densities and convolution in the context of Boolean functions, culminating in an examination of the Blum-Luby-Rubinfeld (BLR) linearity testing algorithm.

This lecture connects Boolean function analysis to social choice theory, exploring the concept of influences and their implications for collective decision-making processes.

This session delves into noise stability for Boolean functions and its relation to Arrow's Impossibility Theorem, demonstrating profound connections between robust computation and social choice.

This lecture investigates spectral concentration phenomena in Boolean functions and its utility in learning algorithms, specifically examining how spectral properties aid in function approximation.

This session covers the concept of restrictions on Boolean functions and details the Goldreich-Levin Theorem, a cornerstone result in cryptography for extracting hard-core predicates.

This lecture focuses on Disjunctive Normal Form (DNF) formulas, exploring their properties and relevance in the analysis of Boolean functions, including complexity and learning aspects.

This session meticulously examines the Linial-Mansour-Nisan (LMN) Theorems, crucial results that relate the complexity of Boolean functions to their Fourier spectrum.

This lecture explores the properties of Majority functions and Linear Threshold Functions (LTFs), linking them to the Central Limit Theorem (CLT) for approximating sums of random variables.

This session further develops the understanding of Linear Threshold Functions (LTFs) by analyzing their noise stability properties, a critical aspect for robust computation and learning.

This lecture introduces the Level-1 inequality and the precise 2/π Theorem, exploring their roles in characterizing the Fourier spectrum of Boolean functions, particularly for 'reasonable' random variables.

This session presents Bonami's Lemma and the pivotal KKL (Kahn-Kalai-Linial) Theorem, which establishes a fundamental lower bound on the influence of variables in Boolean functions.

This lecture introduces dictator testing, a crucial technique in property testing, and presents the Friedgut-Kalai-Naor (FKN) Theorem concerning functions with small influences.

This session introduces Probabilistically Checkable Proofs of Proximity (PCPPs), an advanced concept extending PCPs to property testing for proximity to a specific language or property.

This lecture explores Constraint Satisfaction Problems (CSPs), examining their structure, complexity, and how Boolean function analysis can be applied to understand their solvability and hardness.

This session rigorously presents Håstad's hardness theorems, landmark results demonstrating the optimality of certain approximation algorithms for fundamental CSPs.

This guest lecture details UG-hardness results derived from dictator tests, showcasing how these concepts contribute to proving the inapproximability of specific optimization problems.

This lecture focuses on the Hypercontractivity Theorem, a powerful tool in probability and functional analysis with broad applications in theoretical computer science and spectral graph theory.

This session covers invariance theorems, which elucidate how the structure of Boolean functions can be preserved under certain transformations, providing insights into their robustness and universality.

This final lecture presents the seminal "Majority Is Stablest" Theorem, demonstrating that the Majority function is maximally stable against noise, a key result in robust statistics and theoretical computer science.