15-859S 2007: Analysis of Boolean Functions
Meeting: Tuesdays and Thursdays, 12pm-1:20pm, NSH 3002
Instructor: Ryan O'Donnell ()
Office Hours: WEH 7121, by appointment
Course Blog: http://boolean-analysis.blogspot.com
Homework (solutions available on request)
Lecture Notes (mostly unproofread; I don't vouch for the exact
accuracy of any of them, including the ones I wrote)
- Lecture 1: Intro to boolean
functions; overview of theorems we'll prove (.ppt)
- Lecture 2: Linearity and the Fourier
Expansion (.tex) (scribe: Ryan O'Donnell)
- Lecture 3: The BLR and H?tad Tests;
local testing and decoding (scribe: Samid Hoda)
- Lecture 4: Locally testing Dictatorship
with NAE; PCPPs of doubly-exponential length (scribe: Aaron Roth)
- Lecture 5: Intro to hardness of
approximation; Testing averages, Attenuated Influences, Quasirandomness (scribe: Eric Blais)
- Lecture 6: Unique Games-hardness via
"dictator vs. quasirandom"
tests (scribe: Amitabh Basu)
- Lecture 7: The Goldreich-Levin algorithm
(scribe: Karl Wimmer)
- Lecture 8: Learning under the uniform
distribution (scribe: Moritz Hardt)
- Lecture 9: Learning decisions trees; the
Spectral Norm; beginning learning DNF (scribe: Suresh Purini)
- Lecture 10: Learning DNF in almost
polynomial time, learning AC0, beginning learning juntas (scribe: Elaine
Shi)
- Lecture 11: Learning juntas with
Siegenthaler's Theorem (scribe: Yi Wu)
- Lecture 12: Intro to Social Choice; a
paean to Majority; the probability of Condorcet's Paradox (scribe: Aaron Roth)
- Lecture 13: The Friedgut-Kalai-Naor
Theorem, (2,4)-hypercontractivity (scribe: Amitabh Basu)
- Lecture 14: Influences, Coalitions, and
the Tribes functions (scribe: Karl Wimmer)
- Lecture 15: The noise operator; the
Kahn-Kalai-Linial Theorem and the Friedgut Theorem (scribe: Ryan Williams)
- Lecture 16: The Hypercontractivity
(Bonami-Nelson-Gross-Beckner-...)
Theorem (scribe: Ryan O'Donnell)
- Lecture 17: Hardness Amplification,
Impagliazzo's Hard-Core Set Theorem (scribe: Eric Blais)
- Lecture 18: Hardness Amplification
continued, Noise Sensitivity of Monotone Functions, Recursive Majority (scribe: Moritz Hardt)
- Lecture 19: Noise sensitivity of linear
threshold functions: Peres's
Theorem (scribe: Amitabh Basu)
- Lecture 20: Noise stability of Majority
(scribe: Yi Wu)
- Lecture 21: Proof of the Berry-Esseen
Theorem (scribe: Suresh Purini)
- Lecture 22: The Invariance Principle;
Noise Stability Gaussian Space; Majority Is Stablest proof sketch
(scribe: Elaine Shi)
- Lecture 23: Majority Is Stablest
applications; p-biased Fourier analysis (scribe: Ryan Williams)
- Lecture 24: Russo-Margulis Lemma,
Threshold Phenomena for graph
properties (scribe: Amitabh Basu)
- Guest Lecture 25: Avrim Blum on Blum-Burch-Langford
- Lecture 26: Decision trees and
influences (scribe: Ryan O'Donnell)
- Lecture 27: Fourier analysis over other
fields, Roth's Theorem in F_{3}^{n} (scribe: Ryan
O'Donnell)
- Lecture 28: Szemeredi's Regularity
Lemma for F_{2}^{n}; testing "triangle"-freeness in
F_{2}^{n}
(scribe: Ryan O'Donnell)
- Lecture 29: Open Problems (scribe: Ryan
O'Donnell)
Course Description
In this course we will explore the Fourier analysis of Boolean functions,
f : {0,1}^{n} → {0,1}. The powerful techniques from this
field have application in numerous areas of computer science. We will
spend some time developing the area's basic mathematics; however, the main
focus will be on applications, in CS theory and beyond. The course is at
a graduate level; advanced undergraduates may enroll with permission of
the instructor.
Prerequisites
The main prerequisite is mathematical maturity. Students must be
comfortable with probability, and also with the basics of algorithmic
analysis (big-O notation) and linear algebra.
Evaluation
There will be about 5 problem sets. Additionally,
we will have graded scribe notes, which will have the same worth
as problem sets. Students will probably be required to scribe 2 or 2.5
lectures.
Course Outline
A rough outline of the topics we will cover:
- Intro to Boolean functions: What do they mean to you?
- Property Testing: linearity, dictatorship, probabilistically
checkable proofs
- Learning Theory: Goldreich-Levin algorithm, learning
sparse and low-degree functions, learning DNF formulas
- Voting: influences, coalitions, Kahn-Kalai-Linial Theorem,
rationality
- Noise Stability: hardness amplification, learning halfspaces,
Majority Is Stablest theorem
- Graph properties: sharp thresholds in random graphs,
percolation, decision tree complexity
- Further topics: metric space embeddings, additive number
theory, coding theory, communication complexity
Related Material
There is no text for this course. Students may want to consult the online
notes from related courses at other universities:
Additional useful reading includes the survey on threshold
phenomena and influence by Gil Kalai and Muli Safra, and Daniel
Štefankovič's master's thesis.