LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Oberseminar Theoretische Informatik WS 01/02

Brauer, Esparza, Mayr, Steger

Mittwochs um 14:00 Uhr s.t., Raum S2229

[Zusammenfassung des nächsten Vortrags (Mittwoch, 6. Februar 2002)]

*Mi,31.10.2001
Martin Kreuzer (Universität Regensburg)
Optimierung des Buchberger-Algorithmus im homogenen Fall
*Mi,21.11.2001
Sven Kosub
Generic Separations and Leaf Languages
In the early nineties of the previous century, leaf languages were introduced as a means for the uniform characterization of many complexity classes, mainly in the range between P (polynomial time) and PSPACE (polynomial space). It was shown that the relativized separability of two complexity classes can be reduced to a combinatorial property of the corresponding defining leaf languages. In the present paper, it is shown that every separation obtained in this way holds for every generic oracle in the sense of Blum and Impagliazzo. We obtain several consequences of this result, regarding, e.g., simultaneous separations and universal oracles, resource-bounded genericity, and type-2 complexity.
*Mi,28.11.2001
Ekkart Kindler
DAWN: Modellierung, Spezifikation and Verifikation verteilter Algorithmen.
DAWN ist eine Technik zur Modellierung, Spezifikation und Verifikation verteilter Algorithmen, die Petrinetze mit Temporaler Logik kombiniert. Der Vortrag gibt einen Überblick über die Prinzipien, Konzepte und Notationen von DAWN
*Mi,12.12.2001
Stefanie Gerke
Erwartete Anzahl Kanten in zufälligen planaren Graphen
*Mi,19.12.2001
Markus Holzer
Assembling Molecules in Atomix is Hard
It is shown that assembling molecules in the Atomix game can be used to simulate finite automata. In particular, an instance of Atomix is constructed that has a solution if and only if the non-emptiness intersection problem for finite automata is solvable. This shows that the game under consideration is PSPACE-complete, improving a recent result of Hüffner et al. (2001). Thus, there are Atomix games which have exponentially long optimal solutions. We also give an easy construction of Atomix game levels whose optimal solutions meet the worst case.
*Mi,16.1.2002
Thomas Schickinger
Szemeredis Regularitätslemma in dünnen Zufallsgraphen
Das Regularitätslemma von Szemeredi stellt eines der wichtigsten Werkzeuge in der modernen Graphentheorie dar. Beispielsweise kann es in der extremalen Graphentheorie zum Beweis des Satzes von Erdös und Stone verwendet werden. Dieses Resultat gibt an, wieviele Kanten ein Graph mindestens enthalten muss, damit die Existenz eines bestimmten Subgraphen G garantiert werden kann.
In zahlreichen Arbeiten wurde versucht, ein zum Satz von Erdös und Stone analoges Ergebnis für Subgraphen G eines Zufallsgraphen G_{n,p} zu zeigen. In Combinatorica 17(2) wurde von Kohayakawa, Luczak und Rödl der Fall G = K_4 bewiesen und zugleich eine Vermutung über die Existenz bestimmter Subgraphen in \eps-regulären Graphen geäußert, mit deren Hilfe der Beweis für den Fall G = K_4 konzeptionell stark vereinfacht würde. Dies würde eine Übertragung des Ansatzes auf beliebige Subgraphen G ermöglichen und könnte allgemein die Anwendbarkeit des Regularitätslemmas in dünnen Zufallsgraphen maßgeblich erweitern.
In diesem Vortrag geben wir eine Einführung in die Anwendung des Regularitätslemmas vor dem Hintergrund des Resultats von Kohayakawa et al. und stellen eine eigene, in Zusammenarbeit mit S. Gerke, H. J. Prömel, A. Steger und A. Taraz entstandene Arbeit zum Beweis der Vermutung für den Fall G = K_4 vor.
*Mi,23.1.2002
Peter Rossmanith
Wieviele Vertex Cover hat ein Graph?
Ein einfacher Algorithmus, der zählen kann wieviele Vertex Cover der Größe k ein Graph enthält, wird vorgestellt. Die Laufzeit ist exponentiell in k. Bisher gab es keinen solchen Algorithmus, was unter anderem daran liegen könnte, die Anzahl selbst durchaus größer als exponentiell in k sein kann.
Auß>erdem möchte ich noch Neuigkeiten ueber das exakte Loesen von Vertex Cover allgemein berichten, welches ja eine Reihe von immer schnelleren Algorithmen hervorbrachte.
Zum Schluss stelle ich eine Technik vor, die DFS-Spannbäume zum Lösen von Optimierungsproblemen verwendet und nicht nur für Vertex Cover anwendbar ist
*Mi,30.1.2002
Martin Raab
Gröbnerbasen, torische Ideale und Matroide
In diesem Vortrag wird gezeigt, wie man Methoden aus der Computeralgebra auf die ganzzahlige lineare Programmierung anwenden kann. Für die in diesem Zusammenhang betrachteten Ideale können Gröbnerbasen in polynomiellem Platz berechnet werden. Um Aussagen über die Struktur dieser Gröbnerbasen zu erhalten, betrachten wir das Optimierungsproblem auf Matroiden und Schnitten von Matroiden.
*Mi,6.2.2002
Peter Ullrich
Algorithmen in der reellen algebraischen Geometrie
...

Martin Raab Last modified: Tue Feb 5 09:30:15 CET 2002