 Mi,31.10.2001
|
|
|
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
|
|
|
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
|
|
...
|
|
|
