15-859S 2007:

Analysis of Boolean Functions (original) (raw)

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)

• Homework 1
• Homework 2
• Homework 3
• Homework 4
• Homework 5

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 F3n (scribe: Ryan O'Donnell)
• Lecture 28: Szemeredi's Regularity Lemma for F2n; testing "triangle"-freeness in F2n(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:
• Rutgers class by Guy Kindler
• Georgia Tech class by Subhash Khot
• Hebrew U. class by Irit Dinur and Ehud Friedgut
• University of Washington class by Nati Linial
• Berkeley class by Elchanan Mossel Additional useful reading includes the survey on threshold phenomena and influence by Gil Kalai and Muli Safra, and Daniel Štefankovič's master's thesis.