Complexity Theory Markus Bläser, Balagopal Komarath

News

23.01.2020

Tutorial Today

The tutorial today is canceled.

20.01.2020

Interactive Proofs

Email 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 Feedback

You 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

Toda

https://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

Determinant

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... 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/cj97-05.pdf

16.12.2019

Ketan Mulmuley, Umesh Vazirani, Vijay Vazirani

https://people.eecs.berkeley.edu/~vazirani/pubs/matching.pdf

06.12.2019

Sipser, Lautemann

Sipser 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 Construction

http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/lupanov56.pdf

29.11.2019

Karp and Lipton

https://dl.acm.org/citation.cfm?id=804678

12.11.2019

Chandra, Kozen, Stockmeyer

Alternation

The introduction states some cool theorems that you can prove in this model. One of them is that time-bounds become space-bounds and space-bounds become time-bounds when moving between deterministic and alternating TMs.

The definition of ATMs given... Read more

Alternation

The introduction states some cool theorems that you can prove in this model. One of them is that time-bounds become space-bounds and space-bounds become time-bounds 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 non-halting. 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 poly-time bounded machines.

08.11.2019

Róbert Szelepcsényi and Neil Immerman

Róbert Szelepcsényi, The Method of Forced Enumeration for Nondeterministic Automata (1987)

 
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)

 
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 context-sensitive 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

https://core.ac.uk/download/pdf/82306488.pdf

07.11.2019

Venue for Tutorial

The 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) lecture

Today'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 - 3

Since I had to swap the lecture and tutorial this week, I plan to stick with the Friday-to-Friday 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 Tutorial

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

https://theory.stanford.edu/~trevisan/cs172-07/cook.pdf

 

Note that he reduces to tautological formulas via Turing reductions.

24.10.2019

Hennie and Stearns

Here's a link to the two-tape simulation paper.

 

https://www.ccs.neu.edu/home/viola/classes/papers/HennieStearns66.pdf

18.10.2019

Hartmanis and Stearns

The following paper motivated the need to classify problems based on the complexity of algorithms to decide them.

Hartmanis and Stearns

Show all
 

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 NP-completeness) 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.

 



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators