19306711 Seminar

SoSe 24: Seminar on Complexity Theory

Michaela Krüger

Comments

Contents

The well known complexity classes P and NP classify decision problems. Usually, one is interested in the solution itself though, and not just whether a solution exists or not. In this seminar we will look at search problen complexity classes and how the complexity of search and decision versions of problems differ.
In particular we will look at total seach problems, i.e. problems for which there always exists a solution, which is still hard to find. Classes considered are for example PLS, PPAD, PPP, CLS/EOPL/PLS intersected PPAD and UEOPL.
The literature will be in English, talks can be in German or English, depending on the audience.

Target audience

Masters students in computer science and mathematics.

Recommended prerequisites

- "Advanced algorithms" or a similar class.
- P, NP and the concept of reductions is known.

close

Suggested reading

Spezialliteratur aus Zeitschriften

13 Class schedule

Regular appointments

Thu, 2024-04-18 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-04-25 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-05-02 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-05-16 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-05-23 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-05-30 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-06-06 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-06-13 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-06-20 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-06-27 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-07-04 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-07-11 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Thu, 2024-07-18 14:00 - 16:00
Seminar über Komplexitätstheorie

Lecturers:
Michaela Krüger

Location:
T9/SR 006 Seminarraum (Takustr. 9)

Subjects A - Z