Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

Dieses Seminar wird von Mitgliedern des Lehrstuhls Logik in der Informatik als Forum der Diskussion und des Austauschs genutzt. Studierende und Gäste sind herzlich eingeladen. Das Seminar findet während des Sommersemesters 2005 Freitags von 11-13 Uhr im Raum 4.410 des Johann von Neumann Hauses (Rudower Chaussee 25) statt.

Folgende Termine und Vorträge sind bisher vorgesehen:

Fr, 24.6.05, 11:15 Uhr, Raum 4.410:

Thema:	Disjoint NP-pairs from propositional proof systems
Referent:	Olaf Beyersdorff (HU Berlin)

Fr, 10.6.05, 11:15 Uhr, Raum 4.410:

Thema:	The Closest Substring problem with small distances
Referent:	Dr. Dániel Marx (HU Berlin)

Fr, 3.6.05, 11:15 Uhr, Raum 4.410:

Thema:	Exponential Time and Parameterized Complexity
Referent:	Dr. Yijia Chen (HU Berlin)

Di, 31.5.05, 15:15 Uhr, Raum 4.410:

Thema:	Temporal Logics Beyond Regularity
Referent:	Dr. Martin Lange (LMU München)
Abstract:	The most common temporal logics, like LTL, CTL, CTL*, and even relatives like PDL, can be embedded into the modal mu-calculus. Its expressive power - compared to these logics - is rather high. On the other hand, it is also rather limited since it can only define bisimulation-invariant properties of Monadic Second Order Logic, ie. only regular properties. In this talk we will give an overview of temporal logics that are capable of expressing non-regular properties, present results about the decidability and complexity of their satisfiability and model checking problems, and present some yet unanswered questions about them.

Fr, 27.5.05, 11:15 Uhr, Raum 4.410:

Thema:	Strategy Improvement for Parity Games: A Combinatorial Perspective
Referent:	Paul Hunter (HU Berlin)

Fr, 20.5.05, 11:15 Uhr, Raum 4.410:

Thema:	Tight Lower Bounds for Query Processing on Streaming and External Memory Data
Referent:	Prof. Dr. Nicole Schweikardt (HU Berlin)

Fr, 13.5.05, 11:15 Uhr, Raum 4.410:

Thema:	Modellierung und Analyse biochemischer Netwerk mit TPN: Teil 2. Analyse biochemischer Netwerke mit TPN
Referent:	Dr. Louchka Popova-Zeugmann (HU Berlin)

Fr, 29.4.05, 11:15 Uhr, Raum 4.410:

Thema:	Modellierung und Analyse biochemischer Netwerk mit TPN: Teil 1. Modellierung biochemischer Netwerke mit TPN
Referent:	Frau Prof. Monika Heiner (BTU Cottbus)

Fr, 22.4.05, 11:15 Uhr, Raum 4.410:

Thema:	Deterministische und Nichtdeterministische TWAs
Referent:	Andreas Meyer (HU Berlin)

Fr, 15.4.05, 11:15 Uhr, Raum 4.410:

Thema:	Derandomisierung von PPSZ für Unique-k-SAT
Referent:	Daniel Rolf (HU Berlin)
Abstract:	Der PPSZ-Algorithmus von Paturi, Pudlak, Saks und Zane aus dem Jahre 1998 findet die erfüllende Belegung einer eindeutig erfüllbaren 3-SAT Formel in erwarteter Laufzeit O(1.3071n). Mittels der Technik der beschränkten Unabhängikeit kann der Algorithmus mit deterministischer Laufzeit O(1.3071n) derandomisiert werden.
Preprint:	Derandomization of PPSZ for Unique-k-SAT