News
19.02.2020

Hints for AssignmentsHints for Assignment 10 and 11 are uploaded. 
12.02.2020

ExaminationsWith very few exceptions, you can take your exam at any time in the following slots. February: any date except the 17th and the 25th; and on the 26th, only the morning slots are possible. March: any date except the 9th. Please let us know your preferred... Read more With very few exceptions, you can take your exam at any time in the following slots. February: any date except the 17th and the 25th; and on the 26th, only the morning slots are possible. March: any date except the 9th. Please let us know your preferred time by email. It would be nice if you could give us some interval of possible days, so that we have some flexibility when scheduling the exams. 
30.01.2020

LecturesThere will be no lectures next week. We hope you enjoyed the course. All the best for your exams.

30.01.2020

ETHSparsification Lemma
https://cseweb.ucsd.edu/~russell/ipz.pdf
ETH
https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf 
30.01.2020

Barringtonhttps://people.cs.umass.edu/~barrington/publications/bwbp.pdf 
30.01.2020

Circuit Lower BoundsFirst lower bound for parity (Random restrictions) https://wiki.epfl.ch/edicpublic/documents/Candidacy%20exam/Furst%20Saxe%20Sipser%20%201984%20%20Parity%20circuits%20and%20the%20polynomialtime%20hierarchy.pdf
Razborov's lower bound for MAJORITY... Read more First lower bound for parity (Random restrictions) https://wiki.epfl.ch/edicpublic/documents/Candidacy%20exam/Furst%20Saxe%20Sipser%20%201984%20%20Parity%20circuits%20and%20the%20polynomialtime%20hierarchy.pdf
Razborov's lower bound for MAJORITY (polynomial method) https://link.springer.com/article/10.1007%2FBF01137685
Natural proofs http://www.mi.ras.ru/~razborov/int.ps 
28.01.2020

Lecture on Jan 30, ThursdayThere will be a lecture on Jan 30, Thursday, 8:30  10:00 (Usual Tutorial time) in the Tutorial Room SR 016. There is no lecture or tutorial on Jan 31. 
23.01.2020

Tutorial TodayThe tutorial today is canceled. 
20.01.2020

Interactive ProofsEmail and the unexpected power of interaction: https://people.cs.uchicago.edu/~laci/papers/email90.pdf Shamir: https://dl.acm.org/doi/pdf/10.1145/146585.146609?download=true 
14.01.2020

Course FeedbackYou can submit your lecture and tutorial feedback on Jan 17 (Coming Friday) after the lecture. Please try to come and give your feedback. 
09.01.2020

Todahttps://pdfs.semanticscholar.org/6797/9ea92b2cba0e504a596a4c552de4047a39f8.pdf 
09.01.2020

Tutorial on January 16th.As there is no exercise sheet to discuss next week, we will have a short tutorial starting at 09.00. 
16.12.2019

DeterminantBerkowitz algorithm to compute determinant in NC2. https://www.sciencedirect.com/science/article/pii/0020019084900188
Mahajan and Vinay gave a combinatorial interpretation for the determinant. An NC2 algorithm is derived from this... Read more Berkowitz algorithm to compute determinant in NC2. https://www.sciencedirect.com/science/article/pii/0020019084900188
Mahajan and Vinay gave a combinatorial interpretation for the determinant. An NC2 algorithm is derived from this interpretation. http://cjtcs.cs.uchicago.edu/articles/1997/5/cj9705.pdf 
16.12.2019

Ketan Mulmuley, Umesh Vazirani, Vijay Vaziranihttps://people.eecs.berkeley.edu/~vazirani/pubs/matching.pdf 
06.12.2019

Sipser, LautemannSipser first proved containment in the fourth level http://faculty.cs.tamu.edu/chen/courses/637/2006/pres/meng1.pdf
The presented improvement is due to Lautemann. http://faculty.cs.tamu.edu/chen/courses/637/2006/pres/meng2.pdf 
29.11.2019

Lupanov's Constructionhttp://www.thi.informatik.unifrankfurt.de/~jukna/boolean/lupanov56.pdf 
29.11.2019

Karp and Liptonhttps://dl.acm.org/citation.cfm?id=804678 
12.11.2019

Chandra, Kozen, StockmeyerThe introduction states some cool theorems that you can prove in this model. One of them is that timebounds become spacebounds and spacebounds become timebounds when moving between deterministic and alternating TMs. The definition of ATMs given... Read more The introduction states some cool theorems that you can prove in this model. One of them is that timebounds become spacebounds and spacebounds become timebounds when moving between deterministic and alternating TMs. The definition of ATMs given in the paper is more complex because it deals with the following case: If one branch of an existential guess halts and accepts, then you can consider the subcomputation as an accept even if some other branch is nonhalting. However, Theorem 2.6 in this paper proves that as long as we are only considering ATMs with nice time and space bounds, we can assume that all branches halt within that bound. This assumption is true for us since we are only considering polytime bounded machines. 
08.11.2019

Róbert Szelepcsényi and Neil ImmermanRóbert Szelepcsényi, The Method of Forced Enumeration for Nondeterministic Automata (1987) Neil Immerman, Nondeterministic Space is Closed Under Complementation (1988)
As pointed out to me after the lecture, Róbert Szelepcsényi is a Slovak.
Both... Read more Róbert Szelepcsényi, The Method of Forced Enumeration for Nondeterministic Automata (1987) Neil Immerman, Nondeterministic Space is Closed Under Complementation (1988)
As pointed out to me after the lecture, Róbert Szelepcsényi is a Slovak.
Both papers are in English and I assume they missed it because they were published close together. Also, both papers use the NTM definition to prove the theorem and reach the same conclusion.
An interesting corollary is that contextsensitive languages are closed under complementation.
Both of them were awarded the Gödel prize in 1995 for this work. 
08.11.2019

Walter J. Savitch(1969) Relationships Between Nondeterministic and Deterministic Tape Complexities 
07.11.2019

Venue for TutorialThe tutorials will be conducted in Room SR 016, E 1 3 from next week from 8.30  10.00. 
07.11.2019

November 7 (Today's) lectureToday's lecture will take place at Room 415, E 1 3 from 8.30  10.00. The room is on 4th floor of E 1 3 and two rooms next to Markus's office. 
06.11.2019

Assignment  3Since I had to swap the lecture and tutorial this week, I plan to stick with the FridaytoFriday schedule for assignments. I will hand out the third one this Friday and the deadline for submission will be next Friday. 
03.11.2019

Tutorial and Tuesday's lecture slots swapped for this week.The Thursday's tutorial and Tuesday's lecture timings for this week is swapped. This week's tutorial will take place on Tuesday, Nov 5 from 8.30  10.00. The next lecture will be on Thursday, Nov 7 from 8.30  10.00. 
30.10.2019

Dates for Assignments and TutorialThe deadline for submission of assignment 2 is now Tuesday, November 5 as announced in class.
The first tutorial will take place on Thursday, November 7.
The third assignment will be handed out on Tuesday, November 5 and the deadline for the... Read more The deadline for submission of assignment 2 is now Tuesday, November 5 as announced in class.
The first tutorial will take place on Thursday, November 7.
The third assignment will be handed out on Tuesday, November 5 and the deadline for the submission will be Tuesday, November 12. 
29.10.2019

Stephen A. Cookhttps://theory.stanford.edu/~trevisan/cs17207/cook.pdf
Note that he reduces to tautological formulas via Turing reductions. 
24.10.2019

Hennie and StearnsHere's a link to the twotape simulation paper.
https://www.ccs.neu.edu/home/viola/classes/papers/HennieStearns66.pdf 
18.10.2019

Hartmanis and StearnsThe following paper motivated the need to classify problems based on the complexity of algorithms to decide them. 
Complexity Theory
Time and Date:
 Tuesday 8:30  10:00, E1.3 HS003
 Friday 10:15  12:00, E1.3 HS003
 First lecture: Tuesday, Oct. 15
Tutorials:
 The time slot for the tutorial is Thursday 8.30  10.00
Assignments:
There will be weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments.
Exams:
There will be oral exams at the end of the semester.
Prerequisites:
"Grundzüge der Theoretischen Informatik" or equivalent (Introduction to computability and the theory of NPcompleteness) is highly recommended.
Literature:
There are many good books an the topic. Here is a selection:
 Sanjev Arora and Boaz Barak, Computational Complexity  A Modern Approach, Cambridge University Press.
 Oded Goldreich, Computational Complexity  A Conceptual Perspective, Cambridge University Press.
 Uwe Schöning, Gems of Theoretical Computer Science, Springer.
 Rüdiger Reischuk, Komplexitätstheorie (Band 1), Teubner.