Computational complexity theory investigates the problems related to the resources required to run algorithms. It is concerned with the distinction between "tractable" problems, that we can solve with reasonable amounts of resources, and "intractable" problems, that are beyond the power of existing computers. Computational complexity theory also looks at the trade-offs and relationships between different "modes" of computation (randomness, approximation, etc).
The first part of the course will cover basic aspects of complexity theory, and the second part of the course will cover advanced topics, e.g. circuit lower bounds, communication complexity, derandomization, Blum measures, hierarchy results, gap theorem.
- Models of Computation (Logic Circuits, FSM Language Recognition, TM Language Recognition, The Classes P and NP, NP-complete Languages)
- Space Complexity
- Diagonalization and Reduction
- Lower bounds techniques
- Kolmogorov complexity
- Arithmetic on the computer (with some applications in cryptography)