Spring Semester, 2017
Instructor: John H. Reif
A. Hollis Edens Professor of Computer Science
Building: LSRC, Room: D106
E-mail: reif AT cs.duke.edu
Summary Description of Course:
Computational Complexity is the study of bounds on the various metrics (such as time and space) of computations executed on abstract machine models (such as Turing machines, Boolean circuits),, required to solve given problems, as a function of the size of the problem input.
Detailed Description of Course Material: see Schedule
Lecture Times: Tues, Thurs 11:45 PM – 1:00 PM (See Schedule for details)
Lecture Location: LSRC D106
Office Hours: Tues 1:00 PM – 3:00 PM
TA: Tianqi Song
· Office: 208 North Building
· Phone: 919-667-7346
· TA email: stq AT cs.duke.edu
· TA office hours: To be determined
Required Text Books:
[Pap] Christos Papadimitriou. Computational Complexity. Addison-Wesley Longman, 1994. ISBN-10: 0201530821, ISBN-13: 978-0201530827. Corrections: Errata.
[G] Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, ISBN: 978-0521884730 (April 28, 2008)
Surveys on Computational Complexity:
There are no formal prerequisites for the course, except mathematical maturity. However, it would help to have a working knowledge of Turing Machines, NP-Completeness, and Reductions, at the level of an undergraduate algorithms class.
Topics: see above Schedule
There will be 5 homeworks (5% each, 25% total), two quizzes (7.5% each), a midterm exam (10%), an end-term Final Exam (20%), and a Final Project (25%) for the course. Also attendance and class interaction will provide an additional 5% of the total grade.
Homeworks: To be prepared using LATEX (preferred) or WORD.
· Be sure to provide enough details to convince me, but try to keep your answers to at most one or two pages.
· It is OK to answer a problem by stating it is open, but if so, please convincingly explain the reasons you believe this.
· It is permitted to collaborate with your classmates, but please list your collaborators with your homework solution.
· There is no credit given for homework past their due date.
· The final project is a short (approx. 12 pages) paper over viewing (definition of the problem and terminology, and the details of some part of the proof) a prior result in complexity theory.
· The topic is of your choice, and the instructor will provide guidance on relevant literature.
· Novel topics and/or new research may result, but is not necessarily required to still produce an excellent project paper.