COMP 531 (Winter 2012): Theory of Computation
- Instructor: Denis Thérien
- Contact: See Here
- Lectures: Tuesdays and Thursdays 16:05 - 17:25 in McConnell Engineering Building 320
- Office Hours: By appointment (denis at cs mcgill ca)
- Office: McConnell 309
- Teaching Assistant: Anil Ada
- Contact: aada at cs mcgill ca
- Office Hours: Tuesdays and Wednesdays 11:00 to 12:00
- Office: McConnell 337
- Assignment 1 posted!
- Assignment 2 posted. Start early!
- Assignment 3 posted!
- Assignment 4 posted!
- Assignment 5 posted!
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.
- 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.
The prerequisites are COMP 330 and mathematical maturity. The students are expected to know basic probability theory and linear algebra.
- Lecture 1 (Jan 10): Introduction to the course
- Lecture 2 (Jan 12): Space complexity, classes P, NP, L, NL, PSPACE, No universal time bound, Space and time hierarchy theorems, Savitch's theorem
- Lecture 3 (Jan 17): NL = co-NL
- Lecture 4 (Jan 19): Grammers, Chomsky Hierarchy, Reductions, SAT is NP-complete (Cook-Levin Theorem)
- Lecture 5 (Jan 24): Polynomial Hierarchy, QBF is PSPACE-complete
- Lecture 6 (Jan 26): Relativisation, Oracle machines, Baker-Gill-Solovay Theorem, Introduction to Boolean Circuits
- Lecture 7 (Jan 31): Non-uniform computation, P/poly, Karp-Lipton Theorem, Non-uniform Hierarchy Theorem, NC^i, AC^i, TC^i
- Lecture 8 (Feb 2): Restrictions, omega-parity requires uncountably many gates for constant depth circuits
- Lecture 9 (Feb 7): Superpolynomial lower bounds for AC^0 circuits computing Parity (using random restrictions)
- Lecture 10 (Feb 9): The polynomial method of proving Parity not in AC^0 (Razborov-Smolenski)
- Lecture 11 (Feb 14): Lower bounds for threshold circuits, Discriminator Lemma
- Lecture 12 (Feb 16): Threshold_polylog(n) is in AC^0, Symmetric functions in AC^0
- Lecture 13 (Mar 6): Introduction to randomized computation, RP, BPP, Schwartz-Zippel Lemma, Symbolic determinant in RP
- Lecture 14 (Mar 8): Error reduction using few random bits: pairwise independence (Chor-Goldreich) and expanders (Karp-Pippenger-Sipser)
- Lecture 15 (Mar 13): Universal hashing, BPP is in P/poly, BPP is in Sigma_2
- Lecture 16 (Mar 15): Undirected st connectivity is in randomized log space
- Lecture 17 (Mar 20): Interactive Proofs, IP = PSPACE
- Lecture 18 (Mar 22): Finishing IP = PSPACE, An overview of Toda's Theorem and Valiant-Vazirani Theorem
- Lecture 19 (Mar 27): Probabilistically Checkable Proofs (PCP) and hardness of approximation
- Lecture 20 (Mar 29): NP is in PCP(poly(n),1)
- Lecture 21 (Apr 3): Introduction to communication complexity, lower bounds using rank and fooling set, Karchmer-Wigderson games
- Lecture 22 (Apr 5): Randomized and distributional communication complexity, the disrepancy method, discrepancy of Inner-Product
- Lecture 23 (Apr 10): Non-deterministic communication complexity, Communication complexity classes, Some applications of cc: data streaming and time/space tradeoffs for TMs
- Lecture 24 (Apr 12): Multiparty 'number on the forehead model', cylinder intersections, Grolmusz protocol for GIP, connection to circuit lower bounds
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:
- 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
- Assignments: 100% (20% each)