Computational Complexity (Spring 2009)

This course describes attempts to answer a fundamental question of CS namely: What can computers solve efficiently?

Some Bibliography:

While the course does not follow one book in a precise order, most of the material can be found in the following two books (that are available online). I will point to relevant section in the books when teaching the material.

• Draft of book by Sanjeev Arora and Boaz Barak.
• Draft of book by Oded Goldreich.

Some of the topics (at least in the beginning of the course) are also covered in the following books.

• Computational Complexity by Christos Papadimitriou.
• Introduction to the theory of computation by Michael Sipser.

Exercises:

Exercise are given so that you can make sure that you understand the material. Submitting the exercises is not mandatory. I will check a small sample of the questions in each exercise and will give grades. The exercise grade will be 10% of the final grade. (The exercise grade will not be used if it reduces the final grade.

• Exercise 1 : Submission date 30/3/2009.
• Exercise 2 : Submission date 4/5/2009.
• Exercise 3 : Submission date 8/6/2009.

Lectures:

• Lecture 1:
  • High level description of the course's objectives and the achievements of complexity theory.
  • Reminder of time complexity and the classes P,NP.
  • Space complexity: (basics). The material can be found in Part I chapter 4 in Arora-Barak, or Chapter 5 in Goldreich. Most of this material is also available in Sipser's and Papadimitriou's books.
    • 3-SAT in linear space.
    • Definition of TMs that run in space << n.
    • Example: Addition in space O(log n).
    • Definition of L, NL, PSPACE, NPSPACE.
    • Example: directed connectivity in NL.
    • NSPACE(s(n)) in TIME(2^{O(s(n))}) (configuration graphs). (corollary: NL in P).
    • Savich's theroem: NSPACE(s(n)) in SPACE(s(n)^2). (corollary NPSPACE=PSPACE).
    • Directed and undirected connectivity in nondeterministic space O(log n).
    • A randomized algorithm for undirected connectivity in logspace (no proof yet).

• Lecture 2:
  • Space complexity: The class NL (Part I chapter 4 in Arora-Barak).
    • Definition of NL using logarithmic space verifiers and certificates.
    • directed connectivity in NL (proof using certificates).
    • Composition of functions that are computable in logspace.
    • Logspace reductions. Definition, the notion of NL completeness and comparison to poly-time reductions.
    • Directed connectivity is complete for NL.
    • NL=co-NL: We showed this by showing that the complement of directed connectivity is in NL. 

• Lecture 3:
  • Space complexity: The class NL (continued). The material can be found in Part I chapter 4 in Arora-Barak.
    • The problem 2-SAT.
      • 2-SAT in P.
      • 2-SAT in NL.
      • 2-SAT is NL complete.
  • Space complexity: The class PSPACE.
    • Quantified formulae and the problem TQBF.
    • TQBF in PSPACE.
    • PSPACE completeness.
    • TQBF is complete for PSPACE.
    • Interpretation of TQBF as a 2-player game.

• Lecture 4:
  • Diagonalization. The material can be found in Part I chapter 3 in Arora-Barak.
    • The idea of diagonzlization.
    • The deterministic time hierarchy theorem.
    • The deterministic time hierarchy theorem. (Corollary P <> EXP).
    • The space time hierarchy theorem. (Corollary L<>PSPACE).
    • The nondeterministic time hierarchy theorem. (Delayed Diagonaliztion).

• Lecture 5:
  • Diagonalization (continued)
    • Oracles and relativization. (Definitions and examples).
    •  The statement P=NP does not relativize. (Part I chapter 3 in Arora-Barak).
    • Philosophical discussion of the meaning of relativization.
  • The polynomial time Hierarchy. The material can be found in Part I chapter 5 in Arora-Barak.
    • Definition of the polynomial time hierarchy.
    • The hierarchy collapse if Pi_i=Sigma_i or if PH has a complete problem.
    • SAT not in TISP(n^{1.2},n^{0.2}) (statement only, proof next week).

• Lecture 6:
  • SAT not in TISP(n^{1.2},n^{0.2})
  • Boolean circuits (Chapter 6 in Arora-Barak).
    • Circuits and circuit families.
    • Uniform circuits.
    • Nonuniform Turing machines and P/poly.
    • The Karp-Lipton theorem: NP in P/poly implies PH collapses.
    • Definition of AC0 and NC.
    • Relation to parallel computation.

• Lecture 7: Circuit lower bounds.
  • Parity not in AC0 (proof using the Razborov-Smolensky method of approximations see chapter 15 in Arora-Barak).

• Lecture 8: Probabilistic computation (chapter 8 in Arora-Barak)
  • Review of probability theory.
  • The Chernoff inequality and sampling.
  • Randomized quicksort.
  • Polynomial identity testing and Schwartz-Zippel.
  • Finding a perfect matching in randomized NC.
  • Definition of randomized algorithms.
  • The classes BPP and RP.
  • Error reduction for randomized algorithms (statement only).