CS 294-92: Analysis of Boolean Functions

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.

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 2020

Time and Place: Tuesday, Thursday 5:00-6:30 PM -- 310 Soda Hall

Instructor: Avishay Tal, Soda 635, atal "at" berkeley.edu

Office Hours: Monday 1:30-3:30 PM

TA: Orr Paradise, Soda 626, orrp "at" eecs.berkeley.edu

Office Hours: Wednesday 2:30-3:30 PM (or fix an appointment by email). Please send questions/topics in advance.

Grading: Homeworks - 40% (4 assignments), Participation in class - 10%, Final Project & Presentation - 50%. Scribe - an exempt from one problem set and 10%.

Problem Sets:

Homework 1 - Due Monday, Feb 10.
Homework 2 - Due Friday, Feb 28.
Homework 3 - Due Tuesday, Mar 31.
Homework 4 - Due Tuesday, May 5.

Discussions: Piazza

HW submissions: Gradescope

Topics (not necessarily in that order):

Property Testing:

- Linearity Testing [Blum-Luby-Rubinfeld]

Influence and Hypercontractivity:

- Arrow's Theorem (Kalai's Proof)

- Bonami-Beckner Theorem

- The Influence of Variables on Boolean Functions [Kahn-Kalai-Linial]

- Friedgut's Junta Theorem

Learning Theory:

- The Goldreich-Levin Algorithm (stemming from cryptography)

- Learning Shallow Circuits [Linial-Mansour-Nisan]

- Learning DNFs and Mansour's conjecture

- Learning Juntas [Mossel-O'Donnell-Servedio]

Circuit Complexity:

- Random Restrictions

- Parity not in AC0: the Switching Lemma [Håstad]

- Shrinkage of De Morgan Formulae [Håstad]

Pseudo-randomness:

- Small-biased distributions [Naor-Naor]

- Pseudo-randomness for low-degree functions [Bogdanov-Viola, Lovett, Viola].

- Pseudo-randomness based on random restrictions [Ajtai-Wigderson, Gopalan-Meka-Reingold-Trevisan-Vadhan, Steinke-Reingold-Vadhan]

- Fractional pseudo-random generators and polarizing random walks [Chattopadhyay-Hatami-Hosseini-Lovett]

Hardness-of-Approximation:

- The unique-games conjecture and its implications.

The Invariance Principle:

- Central limit theorems [Berry–Esseen]

- "Majority is Stablest" [Mossel-O'Donnell-Oleszkiewicz]

Query Complexity:

- The decision tree model, and its randomized, quantum, and non-deterministic analogs

- The sensitivity theorem [Huang]

- The polynomial method for quantum lower bounds [Beals-Buhrman-Cleve-Mosca-de Wolf]

Lectures:

For each lecture - see 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
Jan 23 - BLR linearity testing - Chapters 1.5-1.6
Jan 28 - Social Choice, Influences, Effects, Derivatives - Chapters 2.1, 2.2 - Lecture notes
Jan 30 - Influences, Effects, Isoperimetric Inequalities - Chapters 2.2, 2.3 - Lecture notes
Feb 4 - Noise Stability, Arrow's Theorem - Chapters 2.4, 2.5 - Lecture notes
Feb 6 - Spectral Concentration and Low-Degree Learning - Chapters 3.1-3.4 - Lecture notes (Scribe: Alex Yu)
Feb 11 - Goldreich-Levin Algorithm - Chapter 3.5 - Lecture notes (Scribe: Alex Yu)
Feb 13 - Learning Juntas - [Mossel-O'Donnell-Servedio'04], [Valiant'12]
Feb 18 - DNFs, Random Restrictions - Chapters 3.3, 4.1, 4.3 - Lecture notes (Scribe: Nagaganesh Jaladanki)
Feb 20 - Fourier Concentration of DNFs - Chapter 4.4 - Lecture notes (Scribe: Antares Chen)
Feb 25 - Proof of the Switching Lemma - Thapen's Notes - Lecture notes (Scribe: YiNuo Zhang)
Feb 27 - AC0 Circuits + Intro to Pseudorandomness - Chapter 4.5 + Chapters 6.1 - Lecture notes (Scribe: James Bartusek)
Mar 3 - Pseudorandomness - small-biased distributions - Chapters 6.3 + 6.4 - Lecture notes (Scribe: Luis Barroso-Luque)
Mar 5 - Pseudorandomness - fooling low-degree polynomials, Fractional PRGs - Chapter 6.5 + CHHL'18 - Lecture notes (Scribe: Yunchao Liu)
Mar 10 - LTFs and Central Limit Theorems - Chapters 5.1, 5.2 - Lecture notes (Scribe: Wen Zhang)
Mar 12 - Noise Stability of the Majority Function and LTFs - Chapters 5.2, 5.5 - Lecture notes (Scribe: Yimeng Wang)
Mar 17 - Hypercontractivity - Bonami's Lemma - Chapter 9 - Lecture notes (Scribe: Emily Hsiao)
Mar 19 - Hypercontractivity - KKL Thm, Friedgut's Junta Lemma - Chapter 9- Lecture notes (Scribe: David Mao)
Mar 31 - Dictator Testing & PCPPs - Chapter 7 - Lecture notes (Scribe: Wilson Wu)
Apr 2 - Hardness of Approximation from UGC - Chapter 7 - Lecture notes (Scribe: Jeff Xu)
Apr 7 - The Invariance Principle - Chapter 11
Apr 9 - Majority is Stablest & Hardness of Max-CUT - Chapter 11 - Lecture notes (Scribe: Michael Whitmeyer)
Apr 14 - Query Complexity - [Buhrman, de Wolf'00] - Lecture notes (Scribe: Vishnu Iyer)
Apr 16 - The Sensitivity Theorem - [Huang'19] - Lecture notes (Scribe: Jonathan Shafer)
Apr 21 - Presentations # 1
Apr 23 - Presentations # 2
Apr 28 - Presentations # 3
Apr 30 - Presentations # 4