The instructor will cover some specific topics (e.g., circuits as a complexity model, Kolmogorov complexity, finite fields, graph spectra, etc.) briefly but sufficiently at the start of the term.
For additional material, see below.
| Office hours: | general: Tuesdays and Thursdays, 11:30–12:10 |
| special consultation: Fridays, 10:00am, or as arranged | |
| other: drop by any time |
- Computational complexity
- For a comprehensive reference (much more than this course needs), you might try
C. Papadimitriou, Computational Complexity, Addison Wesley, 1994.Many standard "theory of computation" texts also have the basic material; one good one for complexity in particular isM. Sipser, Introduction to the Theory of Computation, Thompson/PWS, 1997 (or the later 2nd edition).- Circuit complexity
- I'll try to find a good not-too-long reference; for now, try Papadimitriou's text listed above.
- Expander graphs
- I'll try to find a good not-too-long reference; for now, Papadimitriou's text listed above has some information.
- Graph eigenvalues and spectra
- The papers we will cover don't assume this material of their readers; their explanations and/or references will be about the best available.
(For a reference giving far more than you need to know, try searching for "graph spectra" on TRELLIS or Google Scholar.)
- Finite fields
- These have a vast literature. I'll cover in class almost everything you'll need to know—not much.