## Course Announcement: Computational Complexity
- Winter/Summer Semester (2013-14)

Time: TuTh 9:30-11:00

Location: D405

Instructor:

Homepage:
http://www.tcs.tifr.res.in/~prahladh/teaching/2013-14/complexity

# Computational Complexity

Computational complexity is the study of efficient
computation. Computational Complexity concerns itself with
understanding the difference between "easy" problems and "intractable"
problems: easy in the sense that the problem can be solved using a
reasonable amount of computational resources and intractable in the
sense that it is beyond the scope of existing computers. The
computational resource could be time, memory, randomness,
communication depending on the context.

This course will roughly be divided into two parts. In the first
half of the course, we will cover the classical material (NP
completeness, space complexity, time and space hierarchy, alternation,
randomized algorithms, interactive proofs). In the second half of the
course, we will deal with more advanced topics (possible research
directions), a superset of which is given below.

- cryptography public-key encryption, zero knowledge, commitment
schemes, homomorphic encryption
- derandomization
- pseudorandom constructions: expanders, extractors ...
- cryptography
- proof complexity
- circuit complexity
- PCPs and hardness of approximation
- hardness amplification and connection to coding
- quantum computing
- arithmetic circuits
- ....
- ....

#### References

- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern
Approach (1st edition), Cambridge Universtiy Press, 2009.
- Michael Sipser, Introduction to the
Theory of Computation (2nd edition), Course Technology, 2005.
- Luca Trevisan. CS 278 Computational Complexity, A course
offered at UC, Berkeley (Spring
2001 Notes, Fall
2002 Notes).

Instructor: