Princeton University
Computer Science Department

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

Fall 2002

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

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387

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)



Homeworks: HW1, HW2, HW3, HW4

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

  1. Probabilistic arguments.
  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.