Computational Complexity (Spring 2013)

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.

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

Requirements:

There will be an exam at the end of the course. During the lectures I will sometimes present questions and challenges for you to think about. You are encouraged to work on these questions.

Resources for exam:

Some exercises on the material:

       Ex1

       Ex2

       Ex3

A home exam that was given several years ago.

       Home Exam

Past class exams:

       Moed a

       Moed b

 

Lectures:

 

 

 

       Lecture 4: Diagonalization

o   Another look at the proof of the deterministic time hierarchy theorem.

o   The generality of the argument: the deterministic space hierarchy theorem.

o   Why the argument doesn't give a nondeterministic time hierarchy theorem.

o   The non-deterministic time hierarchy theorem (delayed diagonalization).

o   Weakness of diagnolization: results proven this way hold for any oracle.

o   An oracle A such that NP^A <> P^A. Implies impossibility of proving NP<>P by direct diagonalization.

 

       Lecture 5: Diagonalization (Continued)

o   The notion of relativizing statements and proofs.

o   The statement NP=P and NP<>P are non-relativizing.

o   The polynomial time hierarchy. See nect lecture

 

       Lecture 6: The polynomial time hierarchy

o   Definition with quantifiers and definition with oracles (equivalence is an exercise).

o   The hierarchy collapses if PH has a complete problem.

o   The hierarchy collapses if Sigma_i = Pi_i.

o   Padding arguments.

o   Time space tradeoffs: NTIME(n) not contained in TISP(n^{1.2},n^{0.2}). (Chapter 5 in Arora-Barak).

 

       Lecture 7: Boolean circuits (Chapter 6 in Arora-Barak).

o   Circuits as hardware.

o   Circuits as non-uniform Turing machines (the notion of P/poly and equivalence of definitions).

o   Uniform circuits and alternative definition of P.

o   Counting argument: The existence of functions not computable by size O(2^n/n) circuits.

o   The Karp-Lipton theorem: (NP in P/poly implies PH=Sigma_2).

o   Kannan's lower bound: For every constant c there is a language in Sigma_2 which cannot be computed by circuits of size (n^c).

 

       Lecture 8: Lower bounds for AC0.

o   The notions of AC_i and NC_i and relation to parallel computing.

o   The proof of Razborov and Smolensky that Parity is not in AC0. (see Arora-Barak chapter 14).

 

       Lecture 9: Probabilistic Computation.

o   The notion of a randomized algorithm with one-sided or two sided error.

o   The classes BPP, RP, co-RP.

o   Examples of randomized algorithms (dPATH in Randomized Logspace, Primality testing and identity testing in BPP).

o   Error reduction for randomized algorithms (for both RP and BPP).

 

       Lecture 10: Probabilistic Computation (continued).

o   BPP in P/poly.

o   BPP in Sigma_2.

o   The notion of interactive proofs. Definition of the classes AM and IP.

o   co-GI is in AM.