Complexity of Computational Problems
CS 489/698: Topics in Computer Science, Winter 2016
- Winter 2016
- Time: Mondays and Wednesdays, 4:00-5:20pm
Location: MC 1056
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?
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?
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.
- 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.