Computational Complexity Theory, Fall 2006

Computational complexity theory is a scientific discipline aiming at answering or at least getting a better understanding of questions such as the following by giving them precise quantitative meaning.

The purpose of the course is to give an introduction to the field and its most important techniques.

Contents: (Details may vary) Space bounded computation, crossing sequence arguments, logspace-reductions, Savitch' theorem. Immerman-Szelepcsenyi Theorem, NL-completeness, hierarchy theorems, P and EXP, padding, circuits and non-uniformity, P vs. P/poly, P-completeness, Paul-Pippenger-Valiant theorem, alternation, games, PSPACE-completeness, relativized computation and oracles, massive parallelism, P vs. NC, the fine structure of P, randomized computation, BPP, RP, pBPP and pRP, pBPP=pRP[pRP], dispersers and extractors, Trevisan's extractor, pseudorandom generators and hitting set generators, Sipser's generator, interactive proofs, IP=PSPACE, the PCP-theorem, hardness of approximations, towards P vs. NP (diagonalization approach), time-space tradeoff for SAT, towards P vs. NP (combinatorics approach), bounded depth computation, towards independence of P vs. NP, natural proofs. SL=L.

The course spans the Fall semester of 2006. The exam is oral. The course is graded (using the 00-13 scale). To take the exam (and gain 10 ECTS), five compulsory assignments must be solved in a satisfactory way during the course.

In addition to a problem set, the compulsory assignments will consist of the production of lecture notes. These, together with lecture notes on the Internet will define the curriculum of the course.

The exam dates are January 12th and January 26th. The exam is a conversation with the notes of the student as the point of departure. Please note that the student notes below are unedited. You should read each others notes with a critical mindset and are encouraged to provide feeedback to each other (and to me).

Lectures