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:
- We will present some classical results concerning time and space
complexity for sequential computing models.
- We next turn our attention to parallel computations, using mostly the
model of boolean circuits, with size and depth as key parameters.
- Much attention has been devoted to models that include access to
randomness and a rich theory exists to look at randomized computations.
- It is useful in many contexts to look at communication
as the key bottleneck in computations. The field of communication complexity gives essential
tools pervasive in the whole theory of computing, which we will study.
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.
Prerequisites:
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.
- Assignment 1, due date: Feb. 12th. Note: you will see the necessary material for solving problems in this assignment in coming lectures.
- Assignment 2, due date: midnight of Mar. 12th.
- Assignment 3, due date: midnight of Mar. 19th.
- Assignment 4, due date: midnight of Apr. 5th.
- Assignment 5, due date: midnight of Apr. 16th.
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.
- Classical Complexity (Chapters 1,2,3,4,5)
- Deterministic Turing Machine, Nondeterministic Turing Machine, running time, HALT is undecidable, P, NP
- NP-completeness, 3SAT, Eulerian vs Hamiltonian
- Graph Isomorphism, Factoring, IntegerProgramming
- Time hierarchy, diagonalization, Baker-Gill-Solovay
- Space complexity, PSPACE, QBF, Savitch
- L, NL, Immerman-Szelepcsenyi, Polynomial Hierarchy
- Circuits (Chapters 6,14)
- AC, NC, P/poly
- ADD, ITERATEDADD
- P-hardness, CK-SAT, Karp-Lipton
- Most functions are hard
- Razborov-Smolenski, Hastad
- CLIQUE not in monotone P
- Threshold_(log n) in AC0
- Randomness (Chapters 7,8,17)
- BPP, RP, Median, ZEROP, PerfectMatching
- Error reduction, Expanders
- BPP in P/poly, BPP in Sigma_2 intersection Pi_2
- UPATH in RL
- IP, GNI, IP[k] in AM[k+2]
- IP = PSPACE, PERM in IP, Toda
- Communication Complexity
Evaluation
- Assignments: 100% (5 assignments, each worth 20%)