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
Announcements
- Change of room: From now on we will meet at Birks 111.
- Assignment 2 is out. Start early.
- Assignment 3 is out. Start early.
- Here some notes on Communication Complexity
- Assignment 4 is out.
- Assignment 5 is out.
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 area known as communication complexity is
now an essential tool pervasive in the whole theory of computing.
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:
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:
- 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 (see Communication Complexity book)
- 2 party, fooling set, rank, discrepancy, GIP
- multiparty, circuit lower bounds
- Karchmer-Wigderson
- Disjointness
Evaluation
- Assignments: 100% (20% each)