Computational Complexity

Credits 4
Lecturer Ola Svensson
Office hours Wednesdays 14:00 - 16:00 in INJ 112
Schedule Mondays 10-12 in INM 10. Thursdays 8-10 in INR 113.

Short description

Computational complexity is the part of computer science that studies the computational resources (time, memory, communication, ...) needed to solve problems that we care about. It also looks at the trade-offs and relationships between different types of computation (e.g. whether randomness helps, exact vs approximate solutions, average vs worst case guarantees, ...).

This course familiarizes the students with advanced concepts in computational complexity, and develop an understanding of fundamental questions that underlie some of the key problems of modern computer science. After starting with some basic concepts, potential topics include

Recommended book: Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press, 2009. A draft of the book is available for free here.


Schedule and references