This is an advanced graduate course on the theory of computational complexity. The course will cover basic machine models and complexity measures along with their properties and relationships, complexity classes and their properties, reductions and complete problems, concrete representative problems from important complexity classes. Techniques will be covered for establishing limits on the possible efficiency of algorithms, and concrete lower bounds based on the following models of computation decision trees, straight line programs, communication games, branching programs, PRAMs, boolean circuits. Approximation algorithms and the complexity of approximations. Pseudo-randomness and cryptography.