COMP 531 (Winter 2018): Advanced Theory of Computation

Lectures: Mondays and Wednesdays 01:05 PM-02:25 PM in McConnell 103

Instructor: Denis Thérien
Contact: denis at cs dot mcgill dot ca
Office Hours: on request by email.
Office: McConnell 206N

Teaching Assistant: Yaqiao Li
Contact: yaqiao dot li at mail dot mcgill dot ca
Office Hours: Monday 4-5pm, Tuesday 10-11am.
Office: McConnell 303

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.