Computer Science 6902 (former 6743) -- Complexity of Computational Problems, Winter 2015

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


  • 28/3/2015 Here is a study guide for the Wednesday exam. Remember that we are starting at 5pm, rather than the usual 5:30pm.
  • 28/3/2015 My office hour this week will be 12pm-1pm (I will not be able to make it at the usual time). If this time does not work for you, email me.
  • 28/3/2015 For the unary case, to make it a single circuit you can assume your inputs are alway of the form "000... 111", up to the maximal length. So if your maximal number is 5, you would have five bits, and encode 1,2,3,4,5 by 00001,00011,00111,01111,11111. Also, if you find it easier, you can number the sets as S_0 to S_4 rather than S_1 to S_5, but please explicitly state that you are doing this.
  • 24/2/2015 Schedule reminder: assignment 3 due by 10pm on Sunday, March 29. Monday, March 30 we have a review before the exam. The exam itself is on Wednesday, April 1st: to allow for 2 hours, we will start at 5pm rather than the usual 5:30pm.
  • 23/3/2015 Several classic papers, including Impagliazzo's "5 worlds" paper, are posted below in the lecture notes section.

    older announcements...


    Assignments and tests

    Assignment 1. (LaTeX source) Due Feb 4, 2015. Assignment 2. (LaTeX source) Due Feb 23, 2015. Assignment 3. (LaTeX source) Due March 29, 2015.

    For typesetting please use LaTeX. I will post source files for the assignments. A good, though outdated, introduction to LaTeX is "Essential LaTeX" .


    Course information

    Lectures: 5:30-7pm Mondays and Wednesdays in EN-1051. Instructor: Antonina Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.
    Instructor office hours: Wednesdays 12:30-1:30pm, or by appointment.
    Textbook: Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.
    The link is to the online version, containing an earlier draft of the book.
    Reference book: M. Sipser: Introduction to the Theory of Computation (second edition).
    We will also use lecture notes from similar courses (to be posted later).

    Marking scheme (tentative!): 3 assignments 15% each, a midterm %20, and a final exam 35%.

    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.