Complexity Theory Markus Bläser, Balagopal Komarath

News



08.04.2020

Exams, part 2

Here are some clarifications: Everybody will get the opportunity to do the exams before the semester starts. Currently, it is planned that the university will open from April 27 on. However, this might not happen. If this does not happen, then we will do the exams... Read more

Here are some clarifications: Everybody will get the opportunity to do the exams before the semester starts. Currently, it is planned that the university will open from April 27 on. However, this might not happen. If this does not happen, then we will do the exams online. If you do not want to do the exams online, you can of course take it later when the university opens again.

Sorry for creating some confusion, it was my fault.

08.04.2020

Exams

Hello All,

 

  We hope all of you are safe and well.

 

  The current information is that the University may open by the end of April. Please email us with your preferred dates for the exam starting from April 27. We plan to finish all exams before the... Read more

Hello All,

 

  We hope all of you are safe and well.

 

  The current information is that the University may open by the end of April. Please email us with your preferred dates for the exam starting from April 27. We plan to finish all exams before the beginning of the summer semester.

19.02.2020

Hints for Assignments

Hints for Assignment 10 and 11 are uploaded.

12.02.2020

Examinations

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

Lectures

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

 

30.01.2020

ETH

Sparsification Lemma

 

https://cseweb.ucsd.edu/~russell/ipz.pdf

 

ETH

 

https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf

30.01.2020

Barrington

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

30.01.2020

Circuit Lower Bounds

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%20polynomial-time%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%20polynomial-time%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, Thursday

There 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 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



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