WiSe 2012/2013 » Strukturelle Komplexitätstheorie
Ziegler

Aktuelles

16.12.2012	Das (Block-)Seminar wird am 18.1.2013 und am 25.1.2013 stattfinden, jeweils ab 9h50 im S2|15-201
08.10.2012	Vorbesprechung: 22.10. 9h50 im S2|02-A126

 

Veranstalter

Name	Raum	Tel.
Ziegler, Martin

 

Inhalt

Die strukturelle Komplexitätstheorie wurde begründet von Juris Hartmanis und hat die großen offenen Fragen wie P versus NP versus PSPACE versus EXP wenngleich nicht gelöst, so doch neue Ansätze und Blickwinkel eröffnet.
In diesem Seminar, das gemeinsam mit PD Dr. Ulrike Brandt vom Fachbereich Informatik veranstaltet wird, wollen wir ausgewählte (inzwischen klassische) Höhepunkt-Resultate dieser Theorie erarbeiten und präsentieren; gewissermaßen aus dem Buch der Beweise der Komplexitätstheorie.

Zeitplan

Fr 18.1.2013, S2|15-201
 9h50: Eröffnung und Begrüßung
10h00: Berman-Hartmanis' Isomorphievermutung, Teil 1 (Holger Thies)
11h00: Dinurs Beweis des PCP-Theorems, Teil 1 (Eike Neumann)
12h00: Mittagspause
13h30: Faltungsoperatoren auf endlichen Quantengruppen 
       als Beispiele für vollständig positive Operatoren (Florian Steinberg)
14h30: Die Komplexitätsklasse NPR über Ringen R (Björn Deiseroth)

Fr 25.1.2013, S2|15-201
10h00: Dinurs Beweis des PCP-Theorems, Teil 2 (Eike Neumann)
11h00: Kohäsivität in Promise Problemen (Hermann Walter)
12h00: Mittagspause
13h00: On the Complexity of Satisfiability over Vector Product Terms (Johanna Sokoli)
14h30: Berman-Hartmanis' Isomorphievermutung, Teil 2 (Holger Thies)
15h30: Representations of Closed Sets and Complexity of Operators thereon (Carsten Rösnick)

 

Impressum | Datenschutzerklärung