Establishing the absolute limits of what algorithms can and cannot do. (No matter what new algorithmic techniques are discovered or what computational technologies are invented in the future.)
With mathematics! We will explore the foundations of computer science and complexity theory, and we will establish our main results using tools from the analysis of algorithms, combinatorics, probability theory, and information theory, among other topics.
If you've ever wanted to learn how we can go (far!) beyond the theory of NP-completeness to prove the limitations of randomized algorithms, of approximation algorithms, of massively distributed algorithms, of streaming algorithms, or of sublinear-time algorithms, then this course is for you.
The prerequisites for the course are CS 341 and mathematical maturity. CS 360/365 is recommended but not required.
1. See
the textbook
2. Scroll down for a more detailed list of topics.
3. Contact the instructor, Eric Blais, with any other question.
The assignments will be added here as they become available.