CS 252: Analysis of Boolean Functions

(More to be added as the quarter progresses. Drop me a line if you have a suggestion for a course or paper that I've missed.)

## General Resources

Surveys, lecture and scribe notes, videos, open problem compendiums, etc.-
__Some topics in the Analysis of Boolean functions__, Ryan O'Donnell

__A brief introduction to Fourier Analysis on the Boolean Cube__, Ronald de Wolf

__Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry__, Subhash Khot

__Social choice, computational complexity, Gaussian geometry, and Boolean functions__, Ryan O'Donnell

__Program in Real analysis in Computer Science__, Simons Institute

__Scribe notes for a course at UC Berkeley__, taught by Elchanan Mossel

__Scribe notes for a course at UW Seattle__, taught by Nati Linial

__Scribe notes for a course at Hebrew University__, taught by Irit Dinur and Ehud Friedgut

__Scribe notes for a course at CMU__, taught by Ryan O'Donnell

__Scribe notes for a course at UW Madison__, taught by Dieter van Melkebeek

__Scribe notes for a course at Weizmann__, taught by Guy Kindler

__Lecture notes for a course at Cambridge__, taught by Tom Sanders

__Videos of a course at CMU__, taught by Ryan O'Donnell

__Scribe notes for a ten-lecture minicourse__, taught by Ryan O'Donnell

__Lecture notes for a course at NYU__, taught by Oded Regev

__Lecture notes for a course at McGill__, taught by Hamed Hatami

__Lecture notes for a course at the Technion__, taught by Yuval Filmus

__Lecture notes for a course at UCSD__, taught by Shachar Lovett

__Analysis of Boolean functions: advances and challenges__, video of a talk by Gil Kalai

__Open problems in Analysis of Boolean Functions__, Ryan O'Donnell

__Real Analysis in Computer Science: A collection of open problems__, Simons Institute

## References and supplementary reading material

- Lectures on Influence, sensitivity, and noise stability
__Collective coin flipping, robust voting schemes and minima of Banzhaf values__, Michael Ben-Or and Nathan Linial

__Noise sensitivity of Boolean functions with applications to percolation__, Itai Benjamini, Gil Kalai, Oded Schramm

__Computational applications of noise sensitivity__, Ryan O'Donnell

__Tight bounds on the average sensitivity of__, Kazuyuki Amano*k*-CNF

__Nati's influence__, blogpost by Gil Kalai

- Lectures on Halfspaces
__On the characterization of threshold functions__, Chao-Kong Chow

__The noise stability of weighted majority__, Yuval Peres

__The Chow parameters problem__, Ryan O'Donnell and Rocco Servedio

__Learning intersections and thresholds of halfspaces__, Adam Klivans, Ryan O'Donnell, Rocco Servedio

__Spectral properties of threshold functions__, Craig Gotsman and Nathan Linial

__The correct exponent for the Gotsman-Linial conjecture__, Daniel Kane

__The average sensitivity of an intersection of halfspaces__, Daniel Kane

__Slicing the hypercube__, Michael Saks

- Lectures on Decision trees and query complexity
__Every decision tree has an influential variable__, Ryan O'Donnell, Michael Saks, Oded Schramm, Rocco Servedio

__Decision trees and influence: an inductive proof of the OSSS inequality__, Homin Lee

__The influence lower bound via query elimination__, Rahul Jain and Shengyu Zhang

__Learning monotone decision trees in polynomial time__, Ryan O'Donnell and Rocco Servedio

__Boolean decision trees: Problems and results, old and new__, Michael Saks

__The need for structure in quantum speedups__, Scott Aaronson and Andris Ambainis

- Lectures on Boolean circuits
__Computational limitations for small-depth circuits__, Johan Håstad

__The average sensitivity of bounded-depth circuits__, Ravi Boppana

__Constant depth circuits, Fourier transform, and learnability__, Nathan Linial, Yishay Mansour, Noam Nisan

__An__, Yishay Mansour*O*(*n*^{loglog n}) learning algorithm for DNF under the uniform distribution

__A switching lemma primer__, Paul Beame

__The switching lemma__, lecture notes by Ryan O'Donnell

__The switching lemma__, blogpost by Parikshit Gopalan

__Tight bounds on the Fourier spectrum of AC__, Avishay Tal^{0}

__The entropy-influence conjecture__, blogpost by Gil Kalai - Lectures on Hardness amplification
__Hard-core distributions for somewhat hard problems__, Russell Impagliazzo

__On Yao's XOR lemma__, Oded Goldreich, Noam Nisan, and Avi Wigderson

__Hardness amplification within NP__, Ryan O'Donnell

__Boosting and hard-core set construction__, Adam Klivans and Rocco Servedio

__The Impagliazzo hard-core set theorem__, blogpost by Luca Trevisan - Lectures on Learning under the uniform distribution
__A hard-core predicate for all one-way functions__, Oded Goldreich and Leonid Levin

__Learning decision trees using the Fourier spectrum__, Eyal Kushilevitz and Yishay Mansour

__Learning functions of__, Elchanan Mossel, Ryan O'Donnell, Rocco Servedio*k*relevant variables

__Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem__, Gregory Valiant

__Agnostically learning halfspaces__, Adam Kalai, Adam Klivans, Yishay Mansour, Rocco Servedio

__Agnostically learning decision trees__, Parikshit Gopalan, Adam Kalai, Adam Klivans

__Learning Boolean functions under the uniform distribution via the Fourier transform__, Johannes Köbler and Wolfgang Lindner

__The junta problem__, blogpost by Dick Lipton and Ken Regan

__Learning juntas__, blogpost by Parikshit Gopalan

- Lectures on Property testing
__Self-testing/correcting with applications to numerical problems__, Manuel Blum, Michael Luby, Ronitt Rubinfeld

__Linearity testing in characteristic two__, Mihir Bellare, David Coppersmith, Johan Håstad, Marcos Kiwi, Madhu Sudan

__Testing juntas nearly optimally__, Eric Blais

__Sublinear algorithms in learning and testing__, scribe notes for a course taught by Rocco Servedio

__The art of uninformed decisions: A primer to property testing__, Eldar Fischer

__Testing properties of Boolean functions__, Eric Blais

- Lectures on Hypercontractivity
__Étude des coefficients Fourier des fonctions de__, Aline Bonami*L*^{p}(G)

__The influence of variables on Boolean functions__, Jeff Kahn, Gil Kalai, Nathan Linial

__On Russo's approximate zero-one law__, Michel Talagrand

__Boolean functions with low average sensitivity depend on few coordinates__, Ehud Friedgut

__Hypercontractivity and its applications__, Punyashloka Biswal - Lectures on Limit theorems and Gaussian analysis
__Geometric bounds on the Ornstein-Uhlenbeck velocity process__, Christer Borell

__Optimal inapproximability results for MAX‐CUT and other 2‐variable CSPs?__, Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell

__Noise stability of functions with low influences: Invariance and optimality__, Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz

__Gaussian noise sensitivity and Fourier tails__, Guy Kindler, Naomi Kirshner, Ryan O'Donnell

__The central limit theorem__, lecture notes by Terence Tao

__Invariance principles in theoretical computer science__, video of a talk by Ryan O'Donnell

__Computational applications of invariance principles__, Raghu Meka

__Alan Turing and the central limit theorem__, Sandy Zabell