Computer Science

Analytical Methods in Computer ScienceCSCIGA 3033013 
Fall 2012 
Lectures

Mondays 17:0018:50, WWH 1314 
Instructor 
Oded Regev 
Lecture notes on the web  Ryan O'Donnell's 2007 course and the 2012 one (with videos!) 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. O'Donnell's textbook in preparation can be found here. 
Preliminary syllabus 
Boolean functions, Fourier Transform, Property Testing, Learning Theory, Hardness of Approximation, Noise Stability, and more.... 
Requirements 
Attendance, homework assignments 
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, but not necessary. 
Useful links 
You can try your luck with some open questions (and here is the arXiv version). 
Date  Class Topic 
Sep 17  Linearity and approximate linearity; the BLR test; Fourier expansion; analysis of the BLR test 
Sep 24  Analyzing the BLR test using convolutions; testing dictatorships using the Håstad test; the noise operator; odd Håstad test 
Oct 1  Testing dictatorships using the NAE test and the NAE+BLR test; testing for a subset of the dictatorships; testing a general family; extra reading: an extension of the BLR test, combinatorial property testing 
Oct 8  Influence, total influence, and attenuated influence; quasirandomness; hardness of approximation; the label cover problem 
Oct 12  the unique games conjecture; UGhardness from any dictatorship vs. quasirandom tester 
Oct 22  NPhardness of MAX3LIN2, Learning; the GoldreichLevin algorithm 
Nov 5  An application to hardcore predicates from oneway permutations; The PAC learning model; learning using spectral concentration: the LinialMansourNisan and KushilevitzMansour algorithms; Learning decision trees; 
Nov 12  Learning DNFs (based on Håstad's switching lemma; see Chapter 13 here for a proof) 
Nov 19  More DNFs; Learning juntas [MOS] (using fast matrix multiplication) and see Gregory Valiant's page for his recent improvement 
Nov 26  l_{p} norms; the hypercontractive inequality; Friedgut's theorem and the KKL theorem 
Dec 3  The [FKN] theorem on functions whose Fourier weight is concentrated on the first two levels; 
Dec 10  An application in communication complexity; proof of the hypercontractive inequality 
Dec 12  Gaussian random variables; Noise stability and the stability of majority; majority is stablest, applications and proof 