Computer Science
|
Analytical Methods in Computer Science |
Spring 2011 |
| Lectures
|
Friday 10:00-13: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 Friedgut-Kalai 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 | UG-hardness from any dictatorship vs. quasirandom tester |
| Mar 18 | NP-hardness of MAX3LIN2, Learning (see Yishay's survey); the Goldreich-Levin algorithm and an application to hard-core predicates from one-way permutations |
| Mar 25 | 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) |
| Apr 1 | More DNFs; Learning juntas [MOS] |
| Apr 8 | Finishing juntas; lp 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 |