CS229BR - Analysis of Boolean Functions (Fall 2022)

Course information

Instructor: Chin Ho Lee (he/him) (chlee@seas.harvard.edu)
TF: Juspreet Singh Sandhu (jus065@g.harvard.edu)
Lectures: Tuesdays and Thursdays 3:45pm-5:00pm
Location: SEC 1.402
Office hours:
  Chin: Mondays and Thursday 1-2pm @ SEC LL1.201, or by appointment
  Juspreet: Tuesdays 1-2pm @ SEC 3.317 (Theory lounge)
Canvas: Link
Discussion: Ed
Homework submisson: HotCRP

Follow this Google calendar for the most updated schedule.

Course description

Boolean functions are basic objects of study in theoretical computer science. This course will cover fundamental concepts and techniques in the analysis of Boolean functions, including influence and noise sensitivity, random restrictions, polynomial approximation, and hypercontractivity. We will see applications to various areas in theoretical computer science and mathematics, including circuit complexity, pseudorandomness, learning theory, and combinatorics.

Announcement

Evaluation

40% - 3-4 Problem sets
50% - 1 Project
10% - Peer-grading

Textbook

We will follow the textbook by Ryan O'Donnell, available for free here. For material not covered by Ryan's book, notes and references will be provided. You are encouraged to scribe your own notes, though this is not required.

Lectures

Number Date Topics Notes References
1 9/6 Introduction, Fourier expansion Ed Chapters 1.1, 1.2, 1.3
2 9/8 Basic identities, Linearity testing Ed Chapters 1.4 + Theorem 1.27, 1.6
3 9/13 Linearity testing, Social choice theory Ed Chapters 2.1
4 9/15 Influence Ed Chapters 2.2
5 9/20 Total Influence, Sensitivity, Noise Stability Ed Chapters 2.3, 2.4
6 9/22 Low-degree functions Ed Chapters 3.1, 3.2
7 9/27 Learning low-degree functions Ed Chapters 3.4, 3.3, 3.5
8 9/29 Goldreich-Levin theorem, Kushilevitz-Mansour algorithm Ed Chapters 3.5, 4.1
9 10/4 Random restrictions, Switching Lemma Chapters 4.3, 4.4
10 10/6 Switching Lemma Ed
11 10/11 Multi-Switching Lemma Ed
12 10/13 Multi-Switching Lemma, Low-degree concentration of DNF Ed Chapter 4.4
13 10/18 Low-degree concentration of AC0 Ed Chapter 4.5
14 10/25 Bonami's lemma Ed Chapter 9.1
15 10/27 Hypercontractivity, Small-set expansion Ed Chapters 9.2, 9.5
16 11/1 Level-k inequality, FKN theorem Ed Chapters 9.1, 9.5
17 11/3 KKL theorem Ed Chapters 9.6
18 11/8 PRGs, k-wise independence Ed
19 11/10 bounded independence plus noise Ed
20 11/15 Polarizing random walk Ed
21 11/17 Polarizing random walk, Fourier growth Ed

Homework

You are required to typeset your solution using LaTeX. Overleaf is a popular online LaTeX editor. For each problem set, you will also do some peer-grading.

You are allowed to discuss homework questions with others in the class, only after spending some time on them on your own. You must write down your own solutions, without consulting others while you are writing them.

Project

The project consists of a proposal, a report and a presentation. You can work in groups of size at most 2, except when you group contains an undergraduate student who is enrolled in the class, then your group can be of size 3. Your project report should be about 8-page long. If it exceeds 8 pages, the first 8 pages will be read but the rest may not.

The topics are open-ended. You should cover some new material on the topic that is not in Ryan O'Donnell's book. Here are some suggestions:
  1. survey a research area and focus on how the analysis of Boolean functions is used;
  2. learn about a technical lemma in a paper, present it in the simplest way as possible;
  3. attack a research problem. If you succeed, congratulations, write a paper and present it. If not, summarize your attempts. A list of open problems can be found here.
I will suggest some topics and readings, but you are encouraged to choose a topic that excites you the most, or ask your advisors for suggestions.

Tentative Topics

Basics
- Influence, Sensitivity
Learning
- Low-degree algorithm
- Goldreich-Levin theorem
Circuits
- Random restrictions
- Switching Lemmas
Hypercontractivity
- Low-degree functions
- Isoperimetric inequalities
- Junta theorems
Pseudorandomness
- Bounded independence, small-bias space
- Bounded independence plus noise
- Fractional pseudorandom generators
Monotone functions
- Sunflower lemma
- Threshold phenomena

Resources

An exhaustive list of resources prepared by Li-yang Tan is available here.