53. Workshop über Komplexitätstheorie, Datenstrukturen und Effiziente Algorithmen

Der 53. TheorieTag wird am 3. und 4. Mai 2007 vom Lehrstuhl Informatik 1 der Universität Dortmund veranstaltet.

Eingeladener Vortrag

Harry Buhrman (Amsterdam): On Computation and Communication with Small Bias (Abstract)

Termine

Vortragsanmeldung (mit Abstract)	22. April 2007
Anmeldung (ohne Vortrag)	29. April 2007
Workshop	Beginn: Donnerstag der 3. Mai 2007, gegen Mittag Ende: Freitag der 4. Mai 2007, gegen Mittag

Anmeldungen bitte per Mail an volker.weber@uni-dortmund.de.

Programm

Donnerstag, 03.05.2007
14:00	Begrüßung
14:05	Harry Buhrman, Amsterdam, Eingeladener Vortrag On Computation and Communication with Small Bias

15:05	Pause
15:25	Matthias Englert, Aachen Reordering Buffers for General Metric Spaces

15:50	Henning Wunderlich, Ulm Covers have structure

16:15	Sven Kosub, München Fixpunktanalyse boolescher dynamischer Systeme

16:40	Pause
17:00	Gábor Erdélyi, Düsseldorf On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time

17:25	Kai Plociennik, Chemnitz Approximation von Minimum Independent Dominating Set in zufälligen Hypergraphen

17:50	Pause
18:00	Fachgruppentreffen Komplexität (GI 0.1.4)
20:00	Gemeinsames Abendessen

Freitag, 04.05.2007
09:30	Stefan Porschen, Köln Zur Erfüllbarkeit linearer CNF Formeln

09:55	Thomas Schneider, Jena Die Komplexität des verallgemeinerten Erfüllbarkeitsproblems für Lineare Temporale Logik

10:20	Pause
10:40	Daniel Raible, Trier Maximum Acyclic Subgraph on cubic graphs in time O(1.1960^k)

11:05	André Lanka, Chemnitz Spektrale Partitionierung zufälliger Graphen mit vorgegebener erwarteter Gradsequenz

11:30	Stefan Edelkamp, Dortmund Eine Komplexitätslandkarte für die externe, implizite und gerichtete Graphsuche

11:55	Pause
12:15	Christian Glaßer, Würzburg Logspace Mitoticity

12:40	Heiko Röglin, Aachen Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP

13:05	Ende des Workshops

Programm und Abstracts zu den Vorträgen im PDF-Format

Fachgruppentreffen

Neben dem wissenschaftlichen Programm soll bei diesem Workshop auch ein Fachgruppentreffen der GI-Fachgruppe Komplexität (0.1.4) stattfinden. Bei diesem Treffen soll die zukünftige Arbeit der Fachgruppe besprochen werden und eine neue Fachgruppenleitung gewählt werden. Nach vielen erfolgreichen Jahren möchte die bisherige Fachgruppenleitung, Christoph Meinel und Uwe Schöning, ihr Amt zur Verfügung stellen.

Über eine rege Beteiligung an diesem Treffen würden wir uns sehr freuen - auch wer nicht in der GI ist, kann gerne daran teilnehmen.

Veranstaltungsort und Anfahrt

Der Workshop findet im Neubau der Informatik (OH-14) im Raum E04 statt. Das Gebäude befindet sich auf dem Nordcampus der Universität Dortmund. Anfahrt und Lageplan.

Unterkunft

Eine Liste von Hotels finden Sie hier.

Hinweis! Die Hotelliste wurde aktualisiert (26.03.07).
Für einige Hotels gibt es jetzt spezielle Uni-Preise.
Die Preise und einen Hinweis zur Reservierung finden Sie in der Liste.

Fotos vom TheorieTag

Die Teilnehmer des 53. TheorieTags.

Die neue Fachgruppenleitung

Die neue GI-Fachgruppenleitung Komplexität (GI 0.1.4):
Heribert Vollmer (mitte, Hannover) mit seine Stellvertretern
Thomas Schwentick (links, Dortmund) und
Martin Mundhenk (rechts, Jena).

Organisatoren

Thomas Schwentick
Volker Weber

Letzte Änderung: Montag, der 14. Mai 2007