CS 252: Analysis of Boolean Functions

## General Information

Instructor:

Classroom: Hewlett Teaching Center 103

Time: Mondays and Wednesdays, 4:30-5:50pm

Office hours: After class and by appointment

__Li-Yang Tan__(Gates 466, liyang@cs.stanford.edu)Classroom: Hewlett Teaching Center 103

Time: Mondays and Wednesdays, 4:30-5:50pm

Office hours: After class and by appointment

## Course description

Boolean functions are among the most basic objects of study in theoretical computer science. This course is about the study of boolean functions from a complexity-theoretic perspective, with an emphasis on analytic methods. We will cover fundamental concepts and techniques in this area, including influence and noise sensitivity, polynomial approximation, hypercontractivity, probabilistic invariance principles, and Gaussian analysis. We will see connections to various areas of theoretical computer science, including circuit complexity, pseudorandomness, classical and quantum query complexity, learning theory, and property testing.

Prerequisites: CS103 and CS109. CS154 or CS161 recommended.

Prerequisites: CS103 and CS109. CS154 or CS161 recommended.

## Textbook

__Analysis of Boolean Functions__, by Ryan O'Donnell. Cambridge University Press, 2014.

See also

__References and supplementary reading material__.

## Tentative List of Topics

- Influence, sensitivity, and noise stability
Combinatorial interpretations; analytic formulas

The noise operator

Simple examples:*k*-CNFs and monotone functions - Halfspaces
Halfspaces and their unique Chow parameters

Peres's noise stability bound

Polynomial threshold functions and the Gotsman-Linial conjecture - Decision trees and query complexity
The O'Donnell-Saks-Schramm-Servedio inequality

Randomized query complexity of monotone graph properties

Quantum query complexity and the Aaronson-Ambainis conjecture - Boolean circuits
Random restrictions and Håstad's switching lemma

Fourier spectrum of DNFs and small-depth circuits

Mansour's conjecture and the Fourier Entropy-Influence conjecture - Hardness amplification
Impagliazzo's hard-core set theorem

Yao's XOR lemma

Amplification within NP and O'Donnell's theorem

Dualities between hardness amplification and boosting - Learning under the uniform distribution
Linial-Mansour-Nisan's low-degree algorithm

Goldreich-Levin's query algorithm

Agnostic learning via the Fourier transform

Learning parities with noise and the junta problem - Property testing
The Blum-Luby-Rubinfeld linearity test

Blais's junta tests -
Hypercontractivity
Bonami's lemma

The Kahn-Kalai-Linial theorem

Friedgut's junta theorem - Limit theorems and Gaussian analysis
The Berry-Esséen central limit theorem

Lindeberg replacement method

The Mossel-O'Donnell-Oleszkiewicz invariance principle

Borell's isoperimetric inequality and Majority Is Stablest - If time permits:
Pseudorandomness: bounded independence and small-bias spaces

Uniform approximation by polynomials: symmetrization and Chebyshev polynomials

Hardness of approximation: Håstad's hardness theorems, the Unique Games conjecture

Social choice: Condorcet's paradox, Arrow's impossibility theorem, Friedgut-Kalai-Naor

Additive combinatorics: the polynomial Freiman-Ruzsa conjecture

Sharp threshold phenomena: Friedgut's, Bourgain's, and Hatami's sharp threshold theorems

...

## Evaluation

Students taking the course for a letter grade:
• Course project and in-class presentation

• Scribing one lecture

Students taking the course for CR:
• Scribing one lecture

• Brief overview of a research paper, or scribing one lecture

In-class discussions will be an important component of this course, and hence attendance will be expected.
## References and supplementary reading material

Please follow

__this link__.