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.)


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

Notes and texts


Amitabha Bagchi