Computer Science
Tel-Aviv University

Analytical Methods in Computer Science


Fall 2007


Lecture notes (may contain bugs)

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

Some Information


Thursday 16:00-19:00, Orenstein 111

Oded Regev | Schreiber 103 | 6407996
Lecture notes on the web Ryan O'Donnell's course
Irit Dinur and Ehud Friedgut's course

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
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 UG-hardness from any dictatorship vs. quasirandom tester, NP-hardness of MAX3LIN2
Feb 28 Learning (see Yishay's survey); the Goldreich-Levin algorithm and an application to hard-core predicates from one-way permutations
Mar 6 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)
Mar 13 Learning juntas [MOS]
Mar 20 lp 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

Possible Projects for the Seminar