Computer Science

Analytical Methods in Computer Science0368.4157.01 
Fall 2007 
Lectures

Thursday 16:0019:00, Orenstein 111 
Instructor 
Oded Regev  Schreiber 103  6407996 
Lecture notes on the web  Ryan O'Donnell's course Irit Dinur and Ehud Friedgut's course 
Textbooks 
There's no textbook for this course 
Preliminary syllabus 
Boolean functions, Fourier Transform, Property Testing, Learning Theory, Hardness of Approximation, Noise Stability, and more.... 
Requirements 
Attendance, homework assignments (will require relatively lots of effort), and a final project 
Prerequisites 
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 FriedgutKalai conjecture 
Date  Class Topic 
Jan 31  Linearity and approximate linearity; the BLR test; Fourier expansion; two different ways to analyze the BLR test 
Feb 7  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 
Feb 14  A basic construction of PCPP; influence, total influence, and attenuated influence; quasirandomness; hardness of approximation; the label cover problem; the unique games conjecture 
Feb 21  UGhardness from any dictatorship vs. quasirandom tester, NPhardness of MAX3LIN2 
Feb 28  Learning (see Yishay's survey); the GoldreichLevin algorithm and an application to hardcore predicates from oneway permutations 
Mar 6  The PAC learning model; learning using spectral concentration: the LinialMansourNisan and KushilevitzMansour algorithms; Learning decision trees; learning DNFs (based on Håstad's switching lemma; see Chapter 13 here for a proof) 
Mar 13  Learning juntas [MOS] 
Mar 20  l_{p} norms; the hypercontractive inequality; Friedgut's theorem and the KKL theorem 
Mar 27  the [FKN] theorem on functions whose Fourier weight is concentrated on the first two levels; an application in communication complexity; 
Apr 2  Proof of the hypercontractive inequality; Gaussian random variables 
Apr 7  Noise stability and the stability of majority; majority is stablest, applications and proof 