Computer Science

Analytical Methods in Computer Science 
Spring 2011 
Lectures

Friday 10:0013:00, Room R 
Instructor 
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 
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 
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  UGhardness from any dictatorship vs. quasirandom tester 
Mar 18  NPhardness of MAX3LIN2, Learning (see Yishay's survey); the GoldreichLevin algorithm and an application to hardcore predicates from oneway permutations 
Mar 25  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) 
Apr 1  More DNFs; Learning juntas [MOS] 
Apr 8  Finishing juntas; l_{p} 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 