This course covers the main complexity classes, as well as selected advanced topics in computational complexity. Topics: Hardness of Computational problems, models of computations including Turing machines (universal, probabilistic), Boolean Circuits. Complexity classes (P, NP, coNP, PSPACE, NL, P/poly, BPP) and their relations. Diagonalization, space complexity, randomized computation. Selection of topics such as interactive proofs, cryptography, quantum computation, hardness of approximation, decision trees, or algebraic computational models.