# 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