- 01.07.2016: The eleventh problem set is available. This is the last problem set.
- 24.06.2016: The tenth problem set is available.
- 17.06.2016: The ninth problem set is available.
- 10.06.2016: Next week (13.06.–17.06.2016), the lecture will be on Monday and Tuesday, the tutorial
session will be on Friday. In the following week (20.06.–24.06.2016), the
lecture will be on Tuesday and Friday, and the tutorial session will be on Monday.
There is a special problem set 8a that is to be presented on Monday, 20.06.2016.
- 10.06.2016: The eighth problem set is available.
- 06.06.2016: The class on Friday, 17.06.2016, 10–12, takes place in
K23 instead of SR006.
- 03.06.2016: The seventh problem set is available.
- 27.05.2016: The sixth problem set is available.
- 20.05.2016: The fifth problem set is available.
- 13.05.2016: The fourth problem set is available.
- 06.05.2016: The third problem set is available.
- 29.04.2016: The second problem set is available.
- 27.04.2016: The tutorial session was moved from SR 006 to SR 032, Arnimallee 6 (Pi-building).
- 25.04.2016: The next lecture will be tomorrow during the slot for the tutorial session.
The first tutorial session will be in Friday during the usual lecture slot.
- 01.04.2016: The first problem set is available.
- 01.04.2016: The website is online. The first class happens on
22.04.2016. The tutorial session starts in the second week.
The problem sets will appear only online,
on this website.
- Classes
- time: P, NP, coNP, PH, EXP, NEXP
- space L, SL, NL, coNL, PSPACE, NPSPACE
- randomness: BPP, PP, ZPP, RP
- counting: #P, PARITY P
- interaction: IP, AM, MA, MIP, PCP
- circuits: P/Poly, NC, ACC
- quantum and oracles
- Theorems
- Cook-Levin
- time- and space-hierarchy, Ladner, Mahaney, Baker-Gill-Solovay
- Savitch, Immerman-Szelepcsényi
- Karp-Lipton, Razborov-Smolensky, Håstad switching lemma
- Adleman, Sipser-Gács, Valiant-Vazirani, expander-mixing lemma,
leftover hash lemma, Nisan-Wigderson
- Goldreich-Levin, Razborov-Rudich
- PCP, parallel repetition, Goldwasser-Sipser,
sum-check-protocol
- Notions
- time
- space
- nondeterminism
- advice
- interaction
- diagonalization
- alternation
- relativization
- algebrization
- naturalization
- pseudo-randomness
- error correction
- expander graphs
- discrete Fourier-analysis
- Friday, 22.04.2016
- administrative issues
- introduction
- goals and motivation of complexity theory
- examples of interesting computational problems
- Monday, 25.04.2016
- computational model:
- multi-tape Turing machine
- facts from computability: undecidability, Church-Turing thesis,
encoding of TMs, universal TM
- complexity measures: time and space
- linear speedup theorem
- DTIME and DSPACE
- time-constructible functions
- Tuesday, 26.04.2016
- efficient simulation of Turing machines
- diagonalization and hierarchy theorems
- speedup theorem and gap theorem (without proof)
- the complexity class P
- Monday, 02.05.2016
- nondeterminism, NTIME and NSPACE
- nondeterministic time hierarchy
- the complexity class NP
- characterizations of NP
- reductions and NP-completeness
- Friday 06.05.2016
- Ladner's theorem
- variants of NP: coNP and DP
- Monday, 09.05.2016
- oracles and relativization
- Baker-Gill-Solovay
- Friday, 13.05.2016
- space complexity classes
- Savitch's theorem
- Monday, 16.05.2016
- Friday, 20.05.2016 (given by Claudia Dieckmann)
- LOGSPACE-reductions, NL, PSPACE
- NL-complete problems
- Monday, 23.05.2016 (given by Claudia Dieckmann)
- coNL and Immerman-Szelepsényi
- PSPACE-completeness
- Friday, 27.05.2016
- TQBF
- PSPACE and games
- polynomial hierarchy: introduction
- Monday, 30.05.2016 (given by Claudia Dieckmann)
- polynomial hierarchy: definition, properties, characterization
- Friday, 03.06.2016 (given by Claudia Dieckmann)
- polynomial hierarchy and oracles
- circuits
- Monday, 06.06.2016
- uniformity, advice
- Karp-Lipton theorem
- Friday, 10.06.2016
- non-uniform hierarchy theorem: proof
- NC, P-completeness, parallel algorithms
- Monday, 13.06.2016
- circuit lower bounds: state of the art
- randomization
- the benefits of randomization
- Tuesday, 14.06.2016
- polynomial identity testing
- probabilistic Turing machines
- ZPP, RP, coRP
- Tuesday, 21.06.2016
- BPP
- robustness of definitions
- error reduction in BPP and Chernoff bounds
- Friday, 24.06.2016
- relationships between BPP and other complexity classes
- Adleman's theorem: BPP has polynomial-size circuits
- Sipser-Gács-Lautemann theorem: BPP is in the polynomial hierarchy
- Monday, 27.06.2016
- Interactive proofs: definitions and properties
- Friday, 01.07.2016
- private coin interactive proof for Graph-Non-Isomorphism
- private coins vs. public coins: definition of AM
- Monday, 04.07.2016
- public coin interactive proof for Graph-Non-Isomorphism
- Goldwasser-Sipser set lowerbound protocol
- Friday, 08.07.2016
- arithmetization and sumcheck protocol
- IP=PSPACE
- Monday, 11.07.2016
- Friday, 15.07.2016
- Monday, 18.07.2016
- NP = PCP(poly n, 1) (continued)
- Tuesday, 19.07.2016
Prerequisites
-
MafI I–III, Grundlagen der theoretischen Informatik, AlP III, Höhere Algorithmik
Textbooks
- Sanjeev Arora und Boaz Barak. Computational Complexity: A Modern Approach.
Cambridge University Press, 2009.
The modern standard textbook. Up-to-date,
precise, clearly presented, and comprehensive.
A preliminary version is available
here.
- Oded Goldreich. Computational Complexity: A Conceptual Perspective.
Cambridge University Press, 2008.
Deep, comprehensive, opinionated.
Not necessarily recommended for novices, but it contains
a lot of interesting material for advanced readers.
- Christos Papadimitriou. Computational Complexity. Addison Wesley, 1994.
The classic. A bit dated by now, but still useful.
- Michael Sipser. Introduction to the Theory of Computation. Thomson Press,
2005.
The later chapters provide a well-written overview of selected topics
in complexity theory.
- Ingo Wegener. Komplexitätstheorie: Grenzen der Effizienz von
Algorithmen. Springer Verlag, 2003.
In German.
To pass the class, students have to
-
participate regularly and actively in the tutorial sessions (at least 80%);
- obtain at least 60% of the credits on the problem sets;
- present at least two problems in the tutorial session;
- pass an oral exam at the end of the semester.
The grades are based only on the oral exam.
The lectures take place Monday, 10–12, in SR 005 and Friday,
10–12, in SR 006.
The tutorial session happens on Tuesday, 10–12, in SR 032, Arnimallee 6 (Pi-building).
Instructor's office hours: Tuesday, 14–15, in Room 114.
The problem sets well appear here on a weekly basis.
They are published
online only.
| No. | Out | Due |
pdf | tex | Comments |
| 1 |
01.04.2016 |
03.05.2016 |
|
|
|
| 2 |
29.04.2016 |
10.05.2016 |
|
|
|
| 3 |
06.05.2016 |
17.05.2016 |
|
|
|
| 4 |
13.05.2016 |
24.05.2016 |
|
|
|
| 5 |
20.05.2016 |
31.05.2016 |
|
|
|
| 6 |
27.05.2016 |
07.06.2016 |
|
|
|
| 7 |
03.06.2016 |
14.06.2016 |
|
|
|
| 8 |
10.06.2016 |
21.06.2016 |
|
|
|
| 8a |
10.06.2016 |
20.06.2016 |
|
|
Special problem set |
| 9 |
17.06.2016 |
28.06.2016 |
|
|
|
| 10 |
24.06.2016 |
05.07.2016 |
|
|
|
| 11 |
01.07.2016 |
12.07.2016 |
|
|
Last problem set |