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

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

**Times:**

** Lecture Times: ** Mon,
Wednesday Friday, 1:00 PM-2:30 PM (Room LSRC D243)

**Reif Office
Hours: **
Wed, 11:00-12:30 (D223)

**TA:** Urmi Majumder

**TA email:**
urmim@cs.duke.edu

**TA
office hours:** By Appointment

**Required Class
Text Books:** ([AB] and [G] used by permission)

- [AB] Sanjeev
Arora and Boaz Barak, Computational Complexity: A Modern Approach,
digital preprint of yet to be published book, Princeton University.
- [G] Oded
Goldreich, Computational
Complexity: A Conceptual Perspective, digital preprint of yet to be
published book, Weizmann Institute.
- [Pap]
Christos Papadimitriou. Computational Complexity.
*Addison-Wesley Longman*, 1994. Errata. - Other Relevant
References for Further Reading

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

· Homework4: 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 (at most 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.*

* *

* *