Computer Science
|
Analytical Methods in Computer ScienceCSCI-GA 3033-013 |
Fall 2012 |
| Lectures
|
Mondays 17:00-18: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; 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 |