Meeting and contact information
Meetings: Wednesdays and Fridays,
10:30–11:50am, DC 2568.
Instructor: Jonathan Buss,
DC 3353, jfbuss@cs.
First meeting
The first meeting — Fri., Sept. 9 — will include a brief evaluation of the students' level of background and preparation. The instructor will discuss some of the content of the following paper(s), and/or others, as indicated. Students are encouraged to look at them in advance.
- A. Chandra, D. Kozen, L. Stockmeyer, "Alternation", J. Assoc. Comput. Mach. 28 (114–133) 1981.
Students who cannot attend the first meeting, or have questions or concerns about the suitability of the course, should contact the instructor.
Instructor
Jonathan Buss, DC 3353, x34428, jfbuss@cs.uw…Office hours (DC 3353):
- general — Tuesdays and Thursdays, 1:30–2:15.
- special consultation — Fridays, 2:00pm, or as arranged.
- other — drop by any time.
Background requirements and readings
- An interest in the "theory of computation" and a desire to learn more.
- The instructor will cover some specific topics briefly but sufficiently at the start of the term.
General references
For catching up on particular topics, you might find the following helpful. If you have an alternative, or borrow one, it's likely good as well.- Basics of computational complexity
- Many standard "theory of computation" texts have the basic
material; use the one you have, or check out either or both of
-
M. Sipser, Introduction to the Theory of Computation.
Either the second or third edition is fine. -
C. Papadimitriou, Computational Complexity, Addison
Wesley, 1994.
Somewhat out-dated, but still excellent.
-
M. Sipser, Introduction to the Theory of Computation.
- Comprehensive works (as of their date)
- Either of the following, at your preference.
- S. Arora, B. Barak, Computational Complexity: A Modern approach, Cambridge University Press, 2009.
- O. Goldreich, Computational Complexity: A Conceptual perspective, Cambridge University Press, 2008.
- Adjunct material
- Some mathematical topics get short shrift in the above.
- Finite fields: check out Finite Fields: An introduction through exercises.
- Expander graphs: references to appear.
Course policies
Always cite all of your sources. A lack of a citation indicates one of
- You claim the ideas and their presentation as your own.
- The ideas are "common knowledge" — everyone who could be reasonably expected to read the material already knows them.
For more information, one excellent source is the Harvard Guide to Using Sources, Harvard College Writing Program (Harvard University).