Spring Semester, 2023

**Instructor: ****John H. Reif**

A.
Hollis Edens Professor of Computer Science

**Class
Lectures Location: Building: Gross Hall, Room: 103**

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

**Lectures: **

** Lecture Times: ** **12:00 PM – 1:15 PM** **Tues,
Thurs** (See **Schedule**** **for details)

**Lecture
Location: Gross Hall, Room: 103 **

**Reif
Office Hours: ** 1:30 PM - 2:30 PM Tues, Thurs (***Please email Reif a day before to
schedule a 1-1 office meeting with me)

**TA:
****Grayson York** MS Graduate Student **TA email:** alan.york@duke.edu

TA Office hours:

• Tuesday
4 PM-5 PM Virtual on Zoom (please email to reserve)

• Wends
Noon – 1:15 PM in Person at LSRC D344

**Recitation
Time and Place by TA: ** **Thurs 1:15pm-2:30pm Biological Sciences, Room: 63**

**Course Sakai Site: ****COMPSCI.534.01.Sp23**

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

(Tentative) There will be 6 homeworks (5% each, 30%
total), three quizzes (10% each), an end-term Final Exam (20%), and a Final Project (20%) for the
course. Our policy is that one (and only
one) homework during the entire term is allowed not to be handed in, at no loss
of credit. Furthermore, if you hand in all the homework, then we will drop the
lowest graded homework. 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, 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.*

**Honor code: **For homework problems, discussion among
students is permitted, but students must write up solutions independently on
their own. discussion among students is permitted, but students must write up
solutions independently on their own. No materials or sources from prior years'
classes or from the Internet can be consulted. For details about what is
acceptable, see this honesty matrix.**
**

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