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

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:45 PM – 1:00
PM (See **Schedule** for details)

**Lecture
Location: **LSRC D106

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

[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)

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

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

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.

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