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 2023 should fill out the following Google Form.
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.
Semester: Spring 2023
Time and Place: Tuesday, Thursday 12:30-2:00 PM -- 306 Soda Hall (lecture will not be recorded)
Instructor: Avishay Tal, Soda 635, atal "at" berkeley.edu
Office Hours: Thursday 2-3 PM (start at Berkeley time) - 306 Soda Hall (or fix an appointment by email).
TA: Xin Lyu, Soda 634, xinlyu "at" berkeley.edu
Office Hours: Monday 11 AM - 12 PM, 634 Soda Hall
Grading: Homework - 40% (4 assignments), Lecture Scribe - 10%, Final Project & Presentation - 50%.
Homework 1 - Due Monday, Feb 6.
Homework 2 - Due Thursday, Feb 23.
Homework 3 - Due Friday, Mar 17.
Homework 4 - Due Wednesday, Apr 19.
A link to Google Drive's with all PSets and lecture notes for this semester (Spring 2023).
Discussions on Ed
HW submissions on Gradescope
For each lecture - please take a look at the relevant chapters in O'Donnell's book & additional resources & lecture notes.
Jan 17 - The Fourier expansion, orthogonality of characters - Chapters 1.1-1.4 - Lecture Notes (Chase Norman)
Jan 19 - BLR linearity testing - Chapters 1.5-1.6 - Lecture Notes (Amar Shah)
Jan 24 - Social Choice, Influences, Effects, Derivatives - Chapters 2.1, 2.2 - Lecture Notes (Joao Basso)
Jan 26 - Influences, Effects- Chapters 2.2, 2.3 - Lecture Notes (Andrew Lin)
Jan 31 - Isoperimetric Inequalities, Noise Stability, Arrow's Theorem - Chapters 2.4, 2.5 - Lecture Notes (Landon Butler)
Feb 2 - Spectral Concentration and Low-Degree Learning - Chapters 3.1-3.4 - Lecture Notes (Ethan Qiu)
Feb 7 - Goldreich-Levin Algorithm - Chapter 3.5 - Lecture Notes (Erik Jenner)
Feb 9 - Learning Juntas - [Mossel-O'Donnell-Servedio'04], [Valiant'12] - Lecture Notes (David Zhang)
Feb 14 - DNFs, Random Restrictions - Chapters 3.3, 4.1, 4.3 - Lecture Notes (Siddarth Menon)
Feb 16 - Fourier Concentration of DNFs - Chapter 4.4 - Lecture Notes (Elicia Ye)
Feb 21 - Proof of the Switching Lemma - Thapen's Notes - Lecture Notes (Francisca Vasconcelos)
Feb 23 - AC0 Circuits + Intro to Pseudorandomness - Chapter 4.5 + Chapters 6.1 - Lecture Notes (Adwait Godbole)
Feb 28 - Pseudorandomness - small-biased distributions - Chapters 6.3 + 6.4 - Lecture Notes (Eon Lee)
Mar 2 - Pseudorandomness - fooling low-degree polynomials, Fractional PRGs - Chapter 6.5 + CHHL'18 - Lecture Notes (Louis Golowich)
Mar 7 - LTFs and Central Limit Theorems - Chapters 5.1, 5.2. - Lecuter Notes (Ali Shirali)
Mar 9 - Noise Stability of the Majority Function and LTFs - Chapters 5.2, 5.5 - Lecture Notes (Lucas Gretta)
Mar 14 - Hypercontractivity - Bonami's Lemma - Chapter 9 - Lecture Notes (Laurence Lu)
Mar 16 - Hypercontractivity - KKL Thm, Friedgut's Junta Lemma - Chapter 9 - Lecture Notes (Omar Alrabiah)
Mar 21 - Dictator Testing & PCPPs - Chapter 7 - Lecture Notes (Zhixuan Zhou)
Mar 23- Hardness of Approximation from UGC - Chapter 7 - Lecture Notes (Hongxun Wu)
-- Spring Break
Apr 4 - The Invariance Principle - Chapter 11 - Lecture Notes (Xuandi Ren)
Apr 6 - Majority is Stablest & Hardness of Max-CUT - Chapter 11 - Lecture Notes (Bhavesh Kalisetti)
Apr 11 - Query Complexity - [Buhrman, de Wolf'00]
Apr 13 - The Sensitivity Theorem - [Huang'19] - Lecture Notes (David Wu)
Apr 18 - Extremal Combinatorics, The Sunflower Lemma - [Alweiss-Lovett-Wu-Zhang'19] [Rao'19] - Lecture Notes (Shilun Li)
Apr 20 - Threshold Phenomena, Proof of the Kahn-Kalai Conjecture - [Park-Pham'22] [Frankston-Kahn-Narayanan-Park'19] - Lecture Notes (Angelos Pelecanos)
Apr 28 - Presentations # 1 + Open Problems (Meghal Gupta)
Apr 30 - Presentations # 2
RRR Week: More Presentations
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
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