COMP 531 (Winter 2014): Advanced Theory of Computation

Lectures: Mondays and Wednesdays 13:05 - 14:25 in Birks Building 111

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

Co-instructor: Anil Ada
Contact: aada at cs mcgill ca
Office Hours: Tuesdays 4-5pm
Office: McConnell 337


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.


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: