CSL853: Complexity Theory
II semester: 2005-06
Naveen Garg, Amit Kumar and Amitabha Bagchi
Class Timings: 10AM to 11AM, Tuesdays, Wednesdays and Fridays.
Room: CS Seminar Room (4th Floor Bharti Building.)
Topics
This class will focus on the proofs of hardness results for
approximation algorithms. We will begiin by giving an introduction to
complexity classes and time and space hierarchy. We will introduce
interactive proofs and the complexity class associated with them. Then
we will discuss the PCP theorem and proceed to hardness results.
Lecture Breakup
- Intro to complexity. 10 lectures.
- The PCP Theorem. 10 lectures.
- Hardness of approximation. 20 lectures.
Notes and texts
- The primary text for the first 10 lectures will be
Computational Complexity by Christos
Papadimitriou, Addison Wesley, 1994.
- Lecture notes from Christian Scheideler's class on Modern
Complexity Theory are available here.
- Lecture notes from Oded Goldreich's class are available
here. Lecture 11
is on Interactive Proofs.
- Lance Fortnow's Computational
Complexity blog.
Evaluation
- I Minor Exam: 20%.
- II Minor Exam: 20%.
- Major Exam: 30%.
- Homeworks: 20%.
- Class participation: 10%.
Amitabha Bagchi