CS 294-92: Analysis of Boolean Functions (Spring 2023)

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 as well as 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. 

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 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%.

Problem Sets:

Discussions: Ed

HW submissions: Gradescope

Lectures Schedule:

For each lecture - see the relevant chapters in O'Donnell's book + additional resources + lecture notes.

Spring Break

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