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.
Course contents. The course will mostly follow (a subset of) the material in the textbook. Homework assignments and pointers to additional reading material will be posted here.
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 (CS373), and mathematical maturity will be expected.
Graded Work. There will one homework every 2 weeks (about 5 in total), and one final exam. The homework assignments and the final exam will be worth 50% each.
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.
Acknowledgments. Website design: Manoj Prabhakaran.