Princeton University Computer Science Department

Computer Science 597D Advanced Topics in Computer Science: A Theorist's Toolkit Sanjeev Arora

Fall 2002

Directory
General Information

Course Summary

Aimed primarily at first and second year graduate students who plan to do research in theoretical computer science. We will introduce probabilistic, algebraic, combinatorial, and algorithmic methods useful in proofs. We will read appropriate research papers that highlight use of such techniques. Students will be expected to do problem sets and to work on open problems. They will be asked to produce scribe notes for a lecture. There might also be "field trips" to theory talks or workshops held in the area, for which students will be expected to write a 1-page report.

 

Administrative Information

Lectures: Mon 1:30-4 in Room 301, Computer Science Bldg.

Professor: Sanjeev Arora - 307 CS Building - 258-3869 arora@cs.princeton.edu

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu

Scribe notes:  Every student taking or auditing the course is asked to write scribe notes for a
lecture using the latex system. Relevant style files appear here. Scribes should strive for good
mathematical style.  A few pages from Mathematical Writing by by Knuth, Larrabee, and Roberts provide some good hints.

Course syllabus:

(Depends to some extent upon the interests of the class; the following are some ideas)

• probabilitic arguments: expectation, 2nd moment, large deviation bounds.
• linear programming and duality theorem as a proof technique
• algebraic methods: the dimension argument, eigenvalues
• coding and information theory
• fourier analysis, discrete fourier transform and its uses.
• basic algorithmic tricks
• introduction to high-dimensional geometry
• sampling techniques
• random walks

Handouts:

Homeworks: HW1, HW2, HW3, HW4

Lecture notes:  All lecture notes and assignments in a single file.

1. Probabilistic arguments.
2.  
3. (2 and 3): LP Duality and its use in proofs. Nati Linial's homepage has links to his two coauthored papers on
   Approximate Inclusion-Exclusion.
4. The Dimension Method.  (elementary linear algebra arguments) Link to writeup of presentation on the
   paper on Linear Hashing .   Sasha Razborov's homepage
5. Dimension method (contd) and The Lore (and lure) of Expanders. Link to paper on Expander based nonblocking networks.
6. Eigenvalues and expanders. Link to book on Spectral Graph Theory.
7. Random walks: Analysis of convergence.
8. Introduction to high dimensional geometry and geometric random walks.
9. High dimensional geometry (contd): VC-dimension and applications such as learning theory, Nearest Neighbor searching.
10. Discrete Fourier transform and its uses.
11. LP relaxations of NP-hard problems (Approximation algorithms, Lift and project procedures)
12. Semidefinite programs and their use in tightening relaxations.

Copyright 2002, Sanjeev Arora. All views expressed here are mine and do not reflect those of the funding agencies.
Work done to develop this course was partly supported by the National Science Foundation Awards 0205594, CCR 0098180
and the Packard Fellowship. It also benefitted from the opportunity to visit the Institute for Advanced Study for that academic year.