Computational Complexity.

Catalog description

This course provides a deep dive into the field of computational complexity, emphasizing the study of NP-completeness, the exploration of various complexity classes and the design and analysis of approximation algorithms. Students will explore the foundational theories that classify computational problems according to their inherent difficulty and investigate the limits of algorithmic efficiency. The course will cover classic approximation algorithms and randomized algorithms for a wide range of problems, including graph algorithms, scheduling, and partitioning, while also touching on recent advances and open problems in the field.