CS 294-92: Analysis of Boolean Functions (Spring 2025)
Description:
Boolean functions are central objects of study in theoretical computer science and combinatorics. Analysis of Boolean functions, and in particular Fourier analysis, has been a successful tool in the areas of circuit lower bounds, hardness of approximation, social choice, threshold phenomena, pseudo-randomness, property testing, learning theory, cryptography, quantum computing, query complexity, and others.
These applications are derived by understanding fundamental, beautiful concepts in the study of Boolean functions, such as influence, noise-sensitivity, approximation by polynomials, hyper-contractivity, and the invariance principle (connecting the discrete Boolean domain with the continuous Gaussian domain).
We will study these foundational concepts of Boolean function and their applications to diverse areas in TCS and combinatorics.
Undergraduate students who wish to take this class in Spring 2025 should fill out the following Google Form.
Textbook:
The course will be mainly based on the wonderful book by Ryan O'Donnell. The book is available for free download via this link, or available for purchase on Amazon.
In addition, we will highlight some recent exciting results that are not covered in the book.
General Information:
Semester: Spring 2025
Time and Place: Tuesday, Thursday 11:00A-12:30P -- 310 Soda Hall
Instructor: Avishay Tal, Soda 635, atal "at" berkeley.edu
Office Hours: Tuesday 1:30-2:30 pm @ 635 Soda.
Grading: Homework - 40% (4 assignments), Lecture Scribe - 10%, Final Project & Presentation - 50%.
Problem Sets:
HW1 -- Due Monday, Feb 10.
HW2 - Due Monday, Feb 24.
HW3 - Due Monday, Mar 17.
HW4 - Due Monday, Apr 7.
HW submissions on Gradescope
Lectures Schedule (tentative):
For each lecture - please take a look at the relevant chapters in O'Donnell's book & additional resources & lecture notes.
Jan 21 - The Fourier expansion, orthogonality of characters - Chapters 1.1-1.4 -- notes (Joyce Lu)
Jan 23 - BLR linearity testing - Chapters 1.5-1.6 -- notes (Austin Pechan)
Jan 28 - Social Choice, Influences, Effects, Derivatives - Chapters 2.1, 2.2 -- notes (Vivien Goyal)
Jan 30 - Influences, Effects- Chapters 2.2, 2.3 -- notes (Patrick Bales)
Feb 4- Isoperimetric Inequalities, Noise Stability, Arrow's Theorem - Chapters 2.4, 2.5 -- notes (Prastik Mohanraj)
Feb 6 - Spectral Concentration and Low-Degree Learning - Chapters 3.1-3.4
Feb 11 - Goldreich-Levin Algorithm - Chapter 3.5 -- notes (Thomas Culhane)
Feb 13 - Learning Juntas - [Mossel-O'Donnell-Servedio'04], [Valiant'12] -- notes (Timothe Kasriel)
Feb 18 - DNFs, Random Restrictions - Chapters 3.3, 4.1, 4.3 -- notes (Qinggao Hong)
Feb 20 - Fourier Concentration of DNFs - Chapter 4.4 -- notes (Lucas Ericsson)
Feb 25 - Proof of the Switching Lemma - Thapen's Notes
Feb 27 - Finish Mansour's Theorem + AC0 Circuits - Chapter 4.4, 4.5
Mar 4 - Pseudorandomness - small-biased distributions - Chapters 6.1, 6.3, 6.4
Mar 6 - Pseudorandomness - fooling low-degree polynomials, Fractional PRGs - Chapter 6.5 + CHHL'18
Mar 11 - LTFs and Central Limit Theorems - Chapters 5.1, 5.2.
Mar 13 - Noise Stability of the Majority Function and LTFs - Chapters 5.2, 5.5
Mar 18 - Hypercontractivity - Bonami's Lemma - Chapter 9
Mar 20 - Hypercontractivity - KKL Thm, Friedgut's Junta Lemma - Chapter 9
-- Spring Break
Apr 1 - Dictator Testing & PCPPs - Chapter 7
Apr 3- Hardness of Approximation from UGC - Chapter 7
Apr 8 - The Invariance Principle - Chapter 11
Apr 10 - Majority is Stablest & Hardness of Max-CUT - Chapter 11
Apr 15 - Query Complexity - [Buhrman, de Wolf'00]
Apr 17 - The Sensitivity Theorem - [Huang'19]
Apr 22 - Extremal Combinatorics, The Sunflower Lemma - [Alweiss-Lovett-Wu-Zhang'19] [Rao'19]
Apr 24 - Threshold Phenomena, Proof of the Kahn-Kalai Conjecture - [Park-Pham'22] [Frankston-Kahn-Narayanan-Park'19]
Apr 29 - Presentations # 1
May 1 - Presentations # 2
RRR Week: More Presentations
Resources and Other Courses:
Analysis and TCS: new frontiers -- Simons Institute program -- Summer 2023
Open Problems by Ryan O'Donnell (2012)
Open Problems - Simons Institute program on Real Analysis in Computer Science (2014)
Theory of Computing - Special Issue on Analysis of Boolean Functions
Videos from Real Analysis in Computer Science `Boot Camp' at the Simons Institute (2013):
Inapproximability of Constraint Satisfaction Problems - Johan Håstad - 5 talks
Analytic Methods for Supervised Learning - Adam Klivans - 4 talks
Introduction to Analysis on the Discrete Cube - Krzysztof Oleszkiewicz - 4 talks
Videos about Fourier concentration and random restriction-based PRGs:
PRGs for Small Space via Fourier Analysis
Pseudorandom Generators from Polarizing Random Walks
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Fourier tails for Boolean functions and their applications
Other Courses:
Dor Minzer - MIT (2021)
Yuval Filmus - Technion (2021)
Li-Yang Tan - Stanford (2018)
Shachar Lovett - UCSD (2017)
Hamad Hatami - McGill (2014)
Oded Regev - NYU (2012)
Ryan O'Donnell - CMU (2012)
Guy Kindler - Weizmann (2008)
Ryan O'Donnell - CMU (2007)
Irit Dinur and Ehud Friedgut - HUJI (2005)
Ryan O'Donnell - AOBF - Mini-Course (2012) Scribe Notes by Li-Yang Tan