Computational Complexity

Computer Science 286/486
University of Rochester
Fall 2018

Instructor: Muthu Venkitasubramaniam

Time: MW 14:00-15:15
Place: BL 315
Course Web page: http://www.cs.rochester.edu/courses/286/fall2018/

Prerequisites

CS 173, MTH 150 and CSC 280

Suggested Material

• Sanjeev Arora and Boaz Barak, Complexity Theory: A Modern Approach. Draft available online.
• Dexter Kozen, Theory of Computation.
• Oded Goldreich, Computational Complexity: A Conceptual Approach. A draft of the book is available online.

Course Administration

All homeworks and grades will be posted on blackboard. Course announcement, discussions and notes will be posted through Piazza.

Grading

There will be Quizzes every class, Homeworks every week, and 2-3 Mid-terms. The grade will be based on all tests and workshop participation

Quizzes 35%

Homeworks 40%

Mid-Terms 25%

Academic Honesty Policy

Please read the official academic honesty policy here. Pertaining to CSC 280, it is mandatory that you additionally adhere to the following policies:

1. YOU ARE NOT ALLOWED to refer any online source for homeworks, midterms, quizzes and homeworks.

2. For solving homeworks (while not encouraged) you are allowed to collaborate with other students in this class. However, you are allowed to collaborate with at most TWO OTHER STUDENTS.

3. You must submit individual homeworks and mention all your collaborators at the beginning of your homeowork. Furthermore, if you cannot explain your solution to a TA or instructor, your work will be considered as plagiarized.

Failure to follow any of the aforementioned policies will be reported to the board of academic honesty according to the rules specified here.