Complexity of Computational Problems
CS 489/698: Topics in Computer Science, Winter 2016

CS 489/698: Complexity of Computational Problems
Winter 2016

Winter 2016
Time: Mondays and Wednesdays, 4:00-5:20pm
Location: MC 1056
Eric Blais
Office hours: Wednesdays, 2:30-3:30 in DC 3122
Teaching assistant
Amit Levi
Office hours: TBD
Piazza page
All announcements for the class will be posted on the Piazza page. The page will also be the central place for class discussions and for any questions about the lectures and assignments.

What is this course about?

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.)

How can we do this?

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.

Is this course for me?

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.

Where can I find more information?

1. See the textbook Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak for a preview of the content of the course.
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.

Problem set 1.
Available on Jan 13. Due on Jan 27.
Problem set 2.
Available on Jan 28. Due on Feb 10.
Problem set 3.
Available on Feb 24. Due on Mar 2.
Problem set 4.
Available on Mar 3. Due on Mar 16.
Problem set 5.
Available on Mar 19. Due on Mar 30.

List of topics

General introduction
Computation models. Lower bound proof techniques. Reductions.
Communication complexity
Deterministic and randomized communication complexity.
Query complexity
Decision tree complexity. Evasiveness. Group testing. Data structure lower bounds.
Time complexity
Going beyond P and NP. Linear-time algorithms. Sublinear-time algorithms.
Hardness of approximation
Optimization problems. PCP Theorem. Hardness of approximation problems.
Parallel computation complexity
PRAM model. Connection to circuit complexity. Alternative models.
Space complexity
The classes L and NL. Streaming algorithms. Distinct elements problem. Johnson-Lindenstrauss Lemma.

Cover photo of Babbage's Difference Engine #2 ©Giles Moss.
Site designed with Bootstrap.