Computational Complexity



  • 2014 Spring/Summer (Jan - May)

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


pseudorandom constructions: expanders, extractors ...

proof complexity

circuit complexity

PCPs and hardness of approximation

hardness amplification and connection to coding

quantum computing

arithmetic circuits