Computer Science
ENS, Paris

Analytical Methods in Computer Science

Spring 2011


Lecture notes from previous class (may contain bugs)

Homework assignments (many taken from Ryan O'Donnell's)

Some Information


Friday 10:00-13:00, Room R

Oded Regev
Lecture notes on the web Ryan O'Donnell's course
Irit Dinur and Ehud Friedgut's course
A similar course I gave in the past
A survey by Ronald de Wolf

There's no textbook for this course
Preliminary syllabus
Boolean functions, Fourier Transform, Property Testing, Learning Theory, Hardness of Approximation, Noise Stability, and more....
Attendance, homework assignments (will require relatively lots of effort), and a final project
Mathematical maturity is a must for this class. In addition, familiarity with the basics of probability, probabilistic method, algebra (especially finite fields), analysis of algorithms, and computational complexity would be helpful.
Useful links
The Friedgut-Kalai conjecture


Date Class Topic
Feb 11 Linearity and approximate linearity; the BLR test; Fourier expansion; two different ways to analyze the BLR test
Feb 25 Testing dictatorships using the Håstad test; the noise operator; testing averages; testing dictatorships using the NAE test and the NAE+BLR test; testing for a subset of the dictatorships; A basic construction of PCPP
Mar 4 Influence, total influence, and attenuated influence; quasirandomness; hardness of approximation; the label cover problem; the unique games conjecture
Mar 11 UG-hardness from any dictatorship vs. quasirandom tester
Mar 18 NP-hardness of MAX3LIN2, Learning (see Yishay's survey); the Goldreich-Levin algorithm and an application to hard-core predicates from one-way permutations
Mar 25 The PAC learning model; learning using spectral concentration: the Linial-Mansour-Nisan and Kushilevitz-Mansour algorithms; Learning decision trees; learning DNFs (based on Håstad's switching lemma; see Chapter 13 here for a proof)
Apr 1 More DNFs; Learning juntas [MOS]
Apr 8 Finishing juntas; lp norms; the hypercontractive inequality
Apr 29 Friedgut's theorem and the KKL theorem; the [FKN] theorem on functions whose Fourier weight is concentrated on the first two levels;
May 6 an application in communication complexity;
May 13 Proof of the hypercontractive inequality; Gaussian random variables
May 20 Noise stability and the stability of majority; majority is stablest, applications and proof
May 27 Exam

Ideas for further reading