This course is an introduction to the theory of computational complexity.
Course objectives. By the end of the course, you should have a broad understanding of the various notions used in computational complexity theory to classify computational problems as hard or easy to solve. You are expected to become familiar with the important complexity classes, how they are related to each other, typical problems in those classes, and some of the central open problems in the field. You should be able to follow the proofs, and develop a feel for the techniques used in reasoning about computational complexity. The course will also briefly introduce you to applications of complexity theory to cryptography.
Course contents. The course will mostly follow (a subset of) the material in the textbook. Additional reading material, when required, will be given out in class. Slides from the lectures and homework assignments will appear in this webpage.
Here is a list of suggested topics for the reading project.
Work involved. Read the textbook (relevant sections); attend the lectures; read and ponder over references/handouts given in class. Grading will be based on assignments (60%), one class-test (15%), one reading-project (20%) and class-participation (5%). Assignments will typically be given out on a Tuesday or Thursday and will be due in class after two weeks.
Prerequisites. This is a graduate course, aimed at Computer Science, ECE and Mathematics students with an interest in theoretical computer science. Some familiarity with basic theory of computation, and some mathematical maturity will be expected.
Office hours. Wednesday 2:00-3:00PM. Please do come for the office hours if you find anything mysterious (or missed anything) in the lectures, class-tests or assignments. You are also welcome to drop by and chat about the content/structure of the course during the office hours. Feel free to send me e-mails anytime if you have any questions or comments.
Collaboration Policy. Limited collaboration is allowed for assignments, unless otherwise specified: you can discuss the problems with others in the class, but you should write up your solutions independently. In particular, you should not look at solutions written up by others. All collaboration should be declared.
Class Test: On Tuesday, March 29 (in class). The topics include what was covered up to (and including) Lecture 14. You are allowed to refer to the lecture notes during the exam, but no other reference, collaboration or assistance should be used.
There will be no office hour on Wednesday, March 30.