Computer Science
Tel-Aviv University

Analytical Methods in Computer Science

[2008/03/30] The extra class on Wednesday at 9:00 is in Schreiber 6. The class next Monday at 16:00 is in Schreiber 7.
[2008/03/28] We rescheduled the extra classes to 2008/4/2, 9:00 and 2008/4/7, 16:00. This is final (I hope).
[2008/03/21] We rescheduled the extra classes to 2008/4/1 and 2008/4/7. Please let me know if you have any problem with this date.
[2008/03/04] The Moed A exam is scheduled for 2008/4/29. Let me know immediately if you have a problem with this date.
[2008/02/28] We will have an extra class on 2008/4/3 between 16:00-19:00. And in the 4th hour next week I'll show solutions for Homework 2.
[2008/02/22] We should decide on a date for the exam. I will send instructions by email soon.
[2008/02/13] Ori just pointed out to me that my "Solution 2" to the constant function issue in Håstad's test is totally wrong (think why...).
[2008/02/12] In Homework 1, Question 6b, you can think of ε as being 1%, and your goal is to recover S correctly with probability 90%.
[2008/02/08] We will have an (official) extra class on Sunday, March 30, 16:00. In addition, we can either add about 30 minutes to each class, or have another meeting, possibly on Thursday, April 3. Next class we'll decide on what's best.
[2008/02/01] Read carefully the instructions given in the beginning of Homework 1. You might prefer to wait with exercises 4b, 5, and 6c until next week (although you can give it a try if you wish).

Lectures	Thursday 16:00-19: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 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	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

The Chow Parameters Problem, by Ryan O'Donnell and Rocco A. Servedio
Independent Sets in Graph Powers are Almost Contained in Juntas, by Irit Dinur, Ehud Friedgut, Oded Regev
Learning Monotone Decision Trees in Polynomial Time, by Ryan O'Donnell and Rocco Servedio.
Any of O'Donnell's lectures that we haven't covered