**John H. Reif
Spring Semester, 2011 **

**Instructor: **John H. Reif

A.
Hollis Edens Professor of Computer Science

D223
LSRC Building

E-mail:
reif AT cs.duke.edu

Phone:
919-660-6568

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

**Lectures:**

** Lecture Times: ** Tues,
Thurs 11:40 AM – 12:55 PM (See Schedule
for details)

**Lecture
Location: **Bio Sci 154

**Reif Office Hours: **
Tues
1:00 PM – 3:00 PM

· office: D330 LSRC

· TA email: nikhil@cs.duke.edu

· **TA office hours:** To be determined

**Required
Hardcopy Text Book:**

[Pap]
Christos Papadimitriou. Computational Complexity. *Addison-Wesley Longman*, 1994. ISBN-10: 0201530821, ISBN-13:
978-0201530827. Corrections: Errata.

**Additional
Digital Text Books:** ([AB] and [G] used by permission)

- [AB] Sanjeev
Arora and Boaz Barak, Computational Complexity: A Modern Approach,
Cambridge University Press (May 2009), ISBN: 978-0521424264
- [G] Oded
Goldreich, Computational Complexity: A Conceptual Perspective,
Cambridge University Press, ISBN: 978-0521884730 (April 28, 2008)
- Other Relevant References for Further Reading

**Surveys on
Computational Complexity:**

- Oded
Goldreich, Computational Complexity, 2000
- Oded
Goldreich and Avi Wigderson, Computational Complexity, Oct 2004

**Prerequisites:**

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

**Grading:**

(Tentative) There will be 4 homeworks (5% each, 20% total), a quiz on
reductions (10%), a midterm exam (10%), an end-term Final Exam (25%), and a
Final Project (30%) 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.

- Assigned:
?? Due: ??
- Assigned:
?? Due: ??
- Assigned:
?? Due: ??

· Assigned: ?? Due: ??

*Homework Rules:*

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

**Final Project:**

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

* *

* *