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:

Discussions on Ed

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.

 -- Spring Break

RRR Week: More Presentations