CS 860: Advanced Topics in Algorithms and Complexity
The state of P vs. NP
Fall 2016

Welcome to CS 860 for Fall 2016. The information below is organized for utility. A formal course outline is also available.

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.

Students who cannot attend the first meeting, or have questions or concerns about the suitability of the course, should contact the instructor.


Jonathan Buss, DC 3353, x34428, jfbuss@cs.uw…
Office hours (DC 3353):

Background requirements and readings

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.
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.

Course policies

Always cite all of your sources. A lack of a citation indicates one of

For more information, one excellent source is the Harvard Guide to Using Sources, Harvard College Writing Program (Harvard University).

Reading List