News
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.