COMP 531 (Winter 2013): Theory of Computation
- Instructor: Denis Thérien
- Contact: See Here
- Lectures: Mondays and Wednesdays 8:35 - 9:55am in McConnell Engineering Building 103
- Office Hours: By appointment (denis at cs mcgill ca)
- Office: McConnell 309
- Teaching Assistant: Anil Ada
- Contact: aada at cs mcgill ca
- Office Hours: By appointment
- Office: McConnell 337
Announcements
- Assignment 1 posted.
- Assignment 2 posted.
- A bonus question for extra credit is posted. See Assignments section.
- Assignment 3 posted.
- Assignment 4 posted.
- Assignment 5 posted.
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:
- Assignment 1
- Assignment 2
- For extra credit (due March 11th): Read the article "Knowledge, Creativity and P versus NP (a very informal draft)" listed below. Write in three pages what you learned from it. Which parts do you like? Are there any parts you don't understand, don't like, or don't agree with?
- Assignment 3
- Assignment 4
- Assignment 5
Recommended References:
We will somewhat follow the book "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak. An online 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)