COMP 531: Theory of Computation (Winter 06)

[ Lectures: summary and links ] [ Assignments ] [ Course description ] [ Links ]


Time: Tuesdays and Thursdays 11:35 AM - 12:55 PM
Place: McConnell Engineering Building 320

Instructor: Navin Goyal
email: first name followed by @cs.mcgill.ca
office: McConnell 106
phone: (514) 398-7071 (ext. 0524)
office hours: Tue 2:00--3:00 PM, and by appt

TA: Mark Mercer
email: jmerce1 followed by @cs.mcgill.ca
office: McConnell 106
phone: (514) 398-7071 (ext. 0524)
office hours: Thu 2:00--3:00 PM, and by appt
Lecture 1 (Jan 3) (Most of this material can be found in Arora Chapters 1, 4 and Sipser Section 7.1)
Quick recap of Turing Machines, Strong Church--Turing hypothesis, time and space complexity measures for TMs, simulation of multi-tape TM by single-tape TM, linear speed up for time and space.

Lecture 2 (Jan 5) (Sipser Chapter 9, Arora Chapter 4)
Space and time hierarchy theorems. Complexity classes P, NP, L, NL, PSPACE, EXP.

Lecture 3 (Jan 10)
Tentative outline:
Reductions. Completeness. P-completeness.
(For the first three topics we mainly use Papadimitriou Chapter 8)
Wikipedia article on P-complete problems

Lecture 4 (Jan 12)
Nondeterminism. NP. Cook--Levin theorem. NP-completeness. Self-reducibility. (Arora Chapter 2)

Lecture 5 (Jan 17)
Space complexity classes L, NL, PSPACE. Complete problems for these classes. (Arora Chapter 3)

Lecture 6 (Jan 19)
Savitch's theorem. Immerman--Szelepcsenyi theorem. (Arora Chapter 3)

Lecture 7 (Jan 24)
Nondeterministic time and space hierarchy theorems (Arora Chapter 4). Ladner's theorem (Papadimitriou Chapter 14).
A write-up of Fortnow on Ladner's theorem. It contains two proofs of the theorem. Proof we did in class resembled the first one a bit.

Lecture 8 (Jan 26)
Relativization (Arora Chapter 4; Papadimitriou Chapter 14). Polynomial Hierarchy (Arora Chapter 5; Papadimitriou Chapter 17).
A compendium of problems in the polynomial hierarchy (PH) by Schaefer and Umans

Lecture 9 (Jan 31)
Continue with PH.

Lecture 10 (Feb 02)
Boolean Circuits. Nonuniform complexity classes. (Arora Chapter 6)

Lecture 11 (Feb 07)
Karp-Lipton theorem. Classes NC, AC, and relationships with other complexity classes (Arora Chapter 6).

Lecture 12 (Feb 09)
Randomized computation. Examples: decision trees, equality computation in two party communication model. Polynomial identity testing. (Arora Chapter 7)

Lecture 13 (Feb 14)
Complexity classes RP, BPP, ZPP. Error reduction by repetition. Adleman's theorem: BPP is in P/poly. Sipser--Lautemann theorem: BPP is in PH.

Lecture 14 (Feb 16)
Randomized space complexity classes. Undirected s-t connectivity is in RL. Universal Hash Functions.

Week of Feb 19. No Lectures: Study Break

Week of Feb 26. No Lectures: Instructor away
Reading assignment: Section 8.1 of Arora's book

Lecture 15 (March 7)
Application of universal hash functions to randomness efficient error reduction. Impagliazzo--Zuckerman generator
The original paper (it's rather terse)
A monograph by Luby and Wigderson on related matters

A planned topic (but not covered due to lack of time):
Introduction to Expander graphs and their application to randomness efficient error reduction. (This material can be found, e.g. within the first 30 pages of the lecure notes Expander Graphs and their Applications by Hoory, Linial, and Wigderson)

Lecture 16 (March 9)
Completing the proof of the Impagliazzo--Zuckerman result. Pseudorandom generators. Nisan--Wigderson pseudorandom generator (Chapter 18 of Arora's book).

Lecture 17 (March 14)
Completing the proof of the Nisan--Wigderson result.

Lecture 18 (March 16)
Communication Complexity. (Chapter 13 of Arora's book)

Lecture 19 (March 21)
(Lecture by Mark Mercer. Instructor away)
AC0 circuits can't compute PARITY (even when augmented with MOD 3 gates). A nice exposition of this material can be found here . See also Arora Chapter 18.2

Lecture 20 (March 23)
(Lecture by Arkadev Chattopadhyay. Instructor away)
Lower bounds for monotone circuits (Arora Chapter 14.3)

Lecture 21 (March 28)
Interactive Proof Systems. Arthur--Merlin protocols. (Arora Chapter 10)
The story of the original discovery of Arthur--Merlin protocols.
And the story of the modern rediscovery (this link might not work from outside the campus).
Another story also discussing the subsequent developments including the PCP Theorem and complete with pictures of the cast of characters.

Lecture 22 (March 30)
#P is in IP. Multiprover interactive proof systems. (Arora Chapter 10)

Lecture 23 (April 4)
Introduction to Probabilistically Checkable Proofs. Relation to multiprover interactive proof systems. (Arora Chapter 19, Papadimitriou Chapter 13)
Section 3 of this paper contains the proof of MIP=PCP(poly(n), poly(n))
A compendium of NP optimization problems

Lecture 24 (April 6)
Remarks on the PCP theorem. Application to Inapproximability results for optimization problems.
A course on the PCP theorem and hardness of approximation

Assignments:

Assignment 1
Assignment 2
Assignment 3
Assignment 4

Course Description: This is an introductory graduate course in computational complexity. We will study questions such as these:

  • Can we prove that some computational problems require lot of time?
  • Does having access to random coin help compute faster?
  • Is it easier to find a solution than to count the number of solutions?
  • Is it easier to find approximate solutions than to find exact solutions?


    • This study suggests a rich web of complexity classes that classify the problems according to the computational resources (e.g., time, memory, randomness, parallelism) needed for their solutions. In this course we will learn about some of these classes and how they are belived to relate with each other. Many important parts of this picture are as yet unproven and filling these gaps constitutes some of the deepest and most important problems in computer science, of which P = NP? problem is the most famous example.

    Brief tentative list of topics:

  • Time and space hierarchy theorems, nondeterminism, time and space complexity classes, reductions, completeness
  • Polynomial hierarchy
  • Counting classes
  • Randomized computation
  • Interactive proofs
  • Probabilistically checkable proofs and hardness of approximation
  • Nonuniform computation and boolean circuits
  • Undirected s-t connectivity in log space


    • Prereqs: The formal prerequisite for the course is COMP 330 or an equivalent course in Automata and Computability. The course will involve a fair amount of mathematics, but this is all elementary: basic probability, algebra, and discrete math. And of course, some knowledge of algorithms is important to appreciate the course. Please check with me if in doubt.

    Grading: There will be bi-weekly homework assignments (a total of about 5).

    Text: We will loosely follow a     draft of an upcoming book by Sanjeev Arora. I'll provide relevant material from the book. The following two books are also useful and on reserve in Schulich library: Introduction to the Theory of Computation by Sipser and Computational Complexity by Papadimitriou. These books cover the basics in more detail than Arora's book. There are many excellent lecture notes available on the web. If you want to have a detailed idea of what the course will be like, please refer to these notes.

    Links to some course notes on the web:
  • Luca Trevisan
  • Steven Rudich and Avrim Blum
  • Madhu Sudan
    • Misc. links:

  • Electronic Colloquium on Computational Complexity
  • Complexity_Zoo Complexity Zoo - Qwiki
  • Computational Complexity Weblog
  • Expander Graphs and their Applications by Hoory, Linial and Wigderson
  • The P vs NP page
  • P, NP and Mathematics - a computational complexity perspective (This paper by Avi Wigderson serves as a good introduction to some of the most important developments in computational complexity)