COMP 6902 -- Theory of computation, Spring 2018

Announcements | Course information | Important dates | Assignments and tests | Lecture notes


older announcements...


Assignments and tests

Assignment 1. (LaTeX source) Due May 30, 2018. Assignment 2. (LaTeX source) Due June 15, 2018 Assignment 3. (LaTeX source) Due July 11, 2018

For typesetting please use LaTeX. I will post source files for the assignments. If you need a LaTeX compiler, the simplest way is to use an online one, such as ShareLaTeX. Just load the source file and start adding your solutions. A good, though outdated, introduction to LaTeX is "Essential LaTeX" .

Policy on collaboration: The work you submit must be your own. You may discuss problems from assignments with each other; however, you should prepare written solutions alone. Plagiarism is a serious academic offense and will be dealt with accordingly.


Course information

Lectures: 2-3:30pm Mondays and Wednesdays in EN-1052.
Antonina Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.
Instructor office hours: Mondays 1pm-1:50pm, or by appointment.

Reference books:
Mathematics and Computation by Avi Wigderson
Introduction to the Theory of Computation" by Michael Sipser
Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.
We will also use lecture notes from similar courses (to be posted later).

Marking scheme: 3 assignments 15% each, a project %25, and a test 30%.

Description: The goal of this course is to help students develop an intuitive feel for hardness of computational problems, and an ability to prove that intuition. What does it mean that a given problem is "hard"? In which sense is it "hard": is it memory-intensive, computation-intensive; how are these notions related? How expressive are various languages used in databases and AI, and what does it mean computationally? These are some of the questions we will explore in this course.

In particular, we will cover the classical P vs. NP problem (is checking a solution easier than finding a solution? Nobody knows!), as well as classes of higher complexity (polynomial-time hierarchy), space classes, counting classes, randomized and circuit complexity, and descriptive and proof complexity. We will also review some computability theory and, time permitting, cover a range of advanced topics such as PCP, natural proofs (why it is hard to resolve the P vs. NP question), hardness of approximation, etc.
(this picture is from the cover of the book "Descriptive Complexity" by Neil Immerman)


Lecture Notes

For now, please see lecture notes from the previous run of this course and notes on computability and NP-completeness from an undergraduate course I taught before. I will try to post updated notes if there are sufficient changes from before, new material, etc.

Classic papers on computability and complexity: