COMP 531 (Winter 2017): Advanced Theory of Computation

Lectures: Mondays and Wednesdays 2:35 - 3:55 in McConnell 103

Instructor: Denis Thérien
Contact: denis at cs mcgill ca
Office Hours: TBD
Office: McConnell 309

Teaching Assistant: Harrison Humphrey
Contact: harrison dot humphrey at mail dot mcgill dot ca
Office Hours: Tuesday and Friday 2:00 - 3:00, or by e-mail
Office: McConnell 110 (South Wing)

Course description:

The notion of computation is fundamental in today's world and thus developing formal understanding of it has significant importance. In this course we will survey various attempts to classify problems in terms of resources necessary to compute their solutions, a point of view that has proved to be fruitful over the last 50 years. The course will be divided into four sections:

A recurrent theme during the course will be that, in spite of deep significant results having been obtained, our understanding of computation is still very fragmentary.


The prerequisites are COMP 330 and mathematical maturity. The students are expected to know basic probability theory and linear algebra.

Assignments will be posted here.

Recommended References:

We will somewhat follow the book "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak. An online (incomplete) draft can be found here.

Other useful resources:
Links to some course notes on the web:

Tentative plan:

Reference: Computational Complexity: A Modern Approach by S. Arora and B. Barak.