Computer Science
Courant Institute

Analytical Methods in Computer Science

CSCI-GA 3033-013

Fall 2012


Lecture notes from previous class (may contain bugs)

Homework assignments (many courtesy of Ryan O'Donnell)

Some Information


Mondays 17:00-18:50, WWH 1314

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

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....
Attendance, homework assignments
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; UG-hardness from any dictatorship vs. quasirandom tester
Oct 22 NP-hardness of MAX3LIN2, Learning; the Goldreich-Levin algorithm
Nov 5 An application to hard-core predicates from one-way permutations; The PAC learning model; learning using spectral concentration: the Linial-Mansour-Nisan and Kushilevitz-Mansour 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 lp 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