Complexity Theory Markus Bläser

News

11.11.2022

No live lectures next week (Nov 15 and 18)

As announced today, there are no live lectures next week. There are two videos in the materials section on chapter 8 (NP) and 11 (PSPACE). Please watch them next week or read the corresponding chapters in the script. (I have chosen chapters 8 and 11, because I think... Read more

As announced today, there are no live lectures next week. There are two videos in the materials section on chapter 8 (NP) and 11 (PSPACE). Please watch them next week or read the corresponding chapters in the script. (I have chosen chapters 8 and 11, because I think they are the most accessible ones.) When I am back, we will go on with chapter 6.

 

There will be a live tutorial on Thursday (HS001 in E1.3 at 10:15). There will be a new assignment sheet on Friday.

09.11.2022

Room change tutorial tomorrow (Nov. 10)

The tutorial tomorrow will take place in seminar room SR 5 (011) in E2 4 in the math building, strictly speaking in the cellar connecting the math building to the math lecture halls. (Take the stairs down in the math building, this room is also known as "Der... Read more

The tutorial tomorrow will take place in seminar room SR 5 (011) in E2 4 in the math building, strictly speaking in the cellar connecting the math building to the math lecture halls. (Take the stairs down in the math building, this room is also known as "Der Bunker".)

From next week on, the tutorial will be in HS001 in E1.3 (the usual lecture hall).

 

02.11.2022

Tutorial and Assignments

- Last Friday, we decided that we will vote for the tutorial slot on this Friday, Nov 4. 

- We shifted the submission deadline for the first assignment by one week. It is now Nov 11.

- You can form teams in CMS until Nov 7. After this, the submission for the... Read more

- Last Friday, we decided that we will vote for the tutorial slot on this Friday, Nov 4. 

- We shifted the submission deadline for the first assignment by one week. It is now Nov 11.

- You can form teams in CMS until Nov 7. After this, the submission for the assignment solutions will open.

- You can also hand in handwritten solutions during the lectures on Fridays.

- I do not know the mysterious assistant either.

- If you are looking for a challenge and want to be a tutor for the lecture while attending it, send your application

 

Complexity Theory

 

Complexity theory is the science of classifying problems with respect to their usage of resources. Ideally, we would like to prove statements of the form “There is an algorithm with running time O(t(n)) for some problem P and every algorithm solving P has to use at least Ω(t(n)) time”. But as we all know, we do not live in an ideal world

This lecture builds upon "Grundzüge der Theoretischen Informatik/Introduction to Theoretical Computer Science".

 

Time and Date:

  • Tuesday, 8:30 - 10:00, E1.3 HS001
  • Friday, 12:15 - 14:00, E1.3 HS001
  • First lecture: Tuesday, Oct 2

We plan to record the lectures.

 

Tutorials:

  • Thursday, 10:15 - 12:00, E1.3 HS001

 

Assignments:

There will be weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments. You can submit assignments in groups of up to three persons.

 

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