859S / 21-801A: Analysis of Boolean Functions 2012 (original) (raw)

Meeting: Mondays and Wednesdays, 3pm-4:20pm, GHC 4101
First meeting: Monday, September 10
Instructor: Ryan O'Donnell ()
Office Hours: GHC 7213, by appointment
Links:

• Textbook in progress
• Spring 2007 version of this course, with lecture notes
• Course bulletin/discussion board. To access it:
  • Go to https://piazza.com/cmu
  • In one of the class slots, search for "15-859S / 21-801A: Analysis of Boolean Functions".
  • Put in the access code aobf12 and click "Join as Student".
  • Click "Add Class".
  • It will then request your "cmu.edu email address". However you can actually use any email address.
  • Follow the subsequent instructions. Problem sets
• Homework 1 (<homework1.tex>, <aobf.sty>, <hemi-icosahedron.pdf>) -- due Monday Sept. 17
• Homework 2 (<homework2.tex>) -- due Monday Sept. 24
• Homework 3 (<homework3.tex>) -- due Monday Oct. 1
• Homework 4 (<homework4.tex>) -- due Monday Oct. 8
• Homework 5 (<homework5.tex>) -- due Monday Oct. 15
• Homework 6 (<homework6.tex>) -- due Wednesday Oct. 24 Lecture videos
• Lecture 1 -- The Fourier expansion and basic formulas (picture-in-picture .mp4)
• Lecture 2 -- Probability densities, convolution, BLR linearity testing (.mp4)
• Lecture 3 -- Social choice and influences (.mp4)
• Lecture 4 -- Noise stability and Arrow's Theorem (.mp4)
• Lecture 5 -- Spectral concentration and learning (.mp4)
• Lecture 6 -- Restrictions and the Goldreich-Levin Theorem (.mp4)
• Lecture 7 -- DNF formulas (.mp4)
• Lecture 8 -- Linial-Mansour-Nisan Theorems (.mp4)
• Lecture 9 -- Majority, LTFs, and the CLT (.mp4)
• Lecture 10 -- LTFs and noise stability (.mp4)
• Lecture 11 -- Level-1 Inequality, 2/π Theorem, reasonable random variables (.mp4)
• Lecture 12 -- Bonami Lemma and KKL Theorem (.mp4)
  (contains an incorrect justification of the simple Markov inequality argument used in the KKL proof; oops)
• Lecture 13 -- Dictator Testing and the FKN Theorem (.mp4)
• Lecture 14 -- Probabilistically checkable proofs of proximity (.mp4)
• Lecture 15 -- Constraint satisfaction problems (.mp4)
• Lecture 16 -- Håstad's hardness theorems (.mp4)
• Lecture 17 -- UG-hardness from dictator tests (.mp4), lecture by John Wright
• Lecture 18 -- The Hypercontractivity Theorem (.mp4)
• Lecture 19 -- Invariance theorems (.mp4)
• Lecture 20 -- Majority Is Stablest theorem (.mp4)
• Lecture 21 -- Additive combinatorics (.mp4)
• Lecture 22 -- Sanders's Theorem (.mp4)
• Lecture 23 -- Open problems (.mp4)

Course description
Boolean functions, f : {0,1}n → {0,1}, are perhaps the most basic object of study in theoretical computer science. They also arise in several other areas of mathematics, including combinatorics (graph theory, extremal combinatorics, additive combinatorics), metric and Banach spaces, statistical physics, and mathematical social choice. In this course we will study Boolean functions via their Fourier transform and other analytic methods. Highlights will include applications in property testing, social choice, learning theory, circuit complexity, pseudorandomness, constraint satisfaction problems, additive combinatorics, hypercontractivity, Gaussian geometry, random graph theory, and probabilistic invariance principles.

Prerequisites
The main prerequisite is working knowledge of discrete probability. Also helpful will be undergraduate-level knowledge of linear algebra, asymptotic analysis, calculus, and computer science.

Evaluation
There will be about 6 problem sets, plus one writing project. The writing project will be given an interim grade and a final grade. The three components (homework, project interim grade, project final grade) will be weighted equally.