Institut   für
Theoretische Informatik
Universität zu Lübeck

15th International Symposium on
Fundamentals of Computation Theory (FCT) 2005
17-20 August 2005

Call for Papers 


Important Dates

Conference Venue

Invited Speakers

Program Committee

Organizing Committee




Previous FCT



Travel Information


Conference Program

Wednesday 17.08.2005

17:00 - 20:00 h


19:00 - 21:00 h


Thursday 18.08.2005

08:30 h


09:00 - 09:10 h

Prof. E. Hartmann,
Dean of the Faculty of Technical and Natural Sciences, University of Lübeck

09:10 - 10.10 h

Plenary session, invited talk 1

Martin Grohe, Berlin
The Complexity of Querying External Memory and Streaming Data
(joint work with C. Koch and N. Schweikardt)

10:10 - 10:30 h

Coffee break

10:30 - 11:30 h

Session 1A

Matthias P. Krieger
On the Incompressibility of Monotone DNFs

Stephen Fenner, Frederic Green, Steven Homer and Yong Zhang
Bounds on the Power of Constant-Depth Quantum Circuits

Session 1B

Michael Hoffmann and Richard M. Thomas
Biautomatic Semigroups

Julien Cristau, Christof Löding and Wolfgang Thomas
Deterministic Automata on Unranked Trees

11:30 - 12:30 h

Session 2A

Daniel Meister
Decidable Membership Problems for Finite Recurrent Systems over Sets of Natural

Philippe Moser
Generic Density and Small Span Theorem

Session 2B

Till Tantau
Logspace Optimization Problems and Their Approximability Properties

Wolfgang Bein, Lawrence Larmore, Linda Morales and I. Hal Sudborough
A Faster and Simpler  2-Approximation Algorithm for Block  Sorting

12:30 - 14:00 h


14:00 - 15:30 h

Session 3A

Holger Spakowski and Rahul Tripathi
On the Power of Unambiguity in Alternating Machines

Chuzo Iwamoto, Yoshiaki Nakashiba, Kenichi Morita and Katsunobu Imai
Translational Lemmas for Alternating TMs and PRAMs

Tomoyuki Yamakami
Collapsing Recursive Oracles for Relativized Polynomial Hierarchies

Session 3B

Fedor V. Fomin, Pinar Heggernes and Dieter Kratsch
Exact Algorithms for Graph Homomorphisms

Jiong Guo, Rolf Niedermeier and Daniel Raible
Improved Algorithms and Complexity Results for Power Domination in Graphs

Andreas Brandstädt, Joost Engelfriet, Hoang-Oanh Le and Vadim V. Lozin
Clique-Width for Four-Vertex Forbidden Subgraphs

15:30 - 16:00 h

Coffee break

16:00 - 17:00 h

Session 4A

Vincenzo Bonifaci, Ugo Di Iorio and Luigi Laura
On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems

Bernd Gärtner and Leo Rüst
Simple Stochastic Games via P-Matrix Linear Complementarity Problems

Session 4B

Hans Ulrich Simon
Visual Cryptography and Approximation Theory: Perfect Reconstruction of Black Pixels Revisited

Sheung-Hung Poon and Chan-Su Shin
Adaptive Zooming in Point Set Labeling

17:00 - 17:15 h

Upcoming FCT 2007

17:15 - 18:00 h

Rump Session

Friday, 19.08.2005

09:00 - 10:00 h

Plenary session, invited talk 2

Daniel Spielman, Cambridge, MA
The Smoothed Analysis of Algorithms

10:00 - 10:30 h

Coffee break

10:30 - 11:30 h

Session 5A

Katalin Friedl, Gabor Ivanyos, Miklos Santha and Yves F. Verhoeven
On the Black-Box Complexity of Sperner's Lemma

Beate Bolllig
Property Testing and the Branching Program Size of Boolean Functions

Session 5B

Bogdan Chlebus and Dariusz Kowalski
Almost Optimal Explicit Selectors

Wolfgang Bein, Kazuo Iwama, Lawrence Larmore and John Noga
The Delayed k-Server Problem

11:30 - 12:30 h

Session 6A

Tomasz Jurdzinski and Krzysztof Lorys
Leftist Grammars and the Chomsky Hierarchy

Markus Holzer and Friedrich Otto
Shrinking Multi-Pushdown Automata

Session 6B

Michael Brinkmeier
A Simple and Fast Min-Cut Algorithm

Eric Angel, Evripidis Bampis, Laurent Gourves and Jerome Monnot
(Non)-Approximability for the Multi-Criteria TSP (1,2)

12:30 - 14:00 h


14:00 - 15:30 h

Session 7A

Pawel Waszkiewicz
Completeness and Compactness of Quantitative Domains

Aleksy Schubert
A Self-Dependency Constraint in the Simply Typed Lambda Calculus

Peeter Laud and Varmo Vene
A Type System for Computationally Secure Information Flow

Session 7B

Alexander Grigoriev and Hans L. Bodlaender
Algorithms for Graphs Embeddable with few Crossings per Edge

Jerome Monnot and Sophie Toulouse
Approximation Results for the Weighted P4 Partition Problems

Joan Boyar, Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt, Kim S. Larsen, Morten Monrad Pedersen and Sanne Wohlk
The Maximum Resource Bin Packing Problem

15:30 - 16:00 h

Coffee break

16:00 - 17:00 h

Session 8A

Birgit Schelm
Average-Case Non-Approximablity of Optimisation Problems

A. Pavan and N.V. Vinodchandran
Relations between Average-Case and Worst-Case Complexity

Session 8B

Joachim Giesen and Dieter Mitsche
Reconstructing Many Partitions Using Spectral Techniques

Akimitsu Ono and Shin-ichi Nakano
Constant Time Generation of Linear Extensions

17:30 - 19:00 h


19:00 - 23:00 h

Conference Dinner

Saturday, 20.08.2005

09:00 - 10:00 h

Plenary session, invited talk 3

Martin Dyer, Leeds
Path Coupling Using Stopping Times
(joint work with M. Bordewich and M. Karpinski)

10:00 - 10:30 h

Coffee break

10:30 - 12:00 h

Session 9A

Sven Koehler, Christian Schindelhauer and Martin Ziegler
On Approximating  Real-World Halting Problems

Klaus Meer and Martin Ziegler
An Explicit Solution to Post's Problem over the Reals

Peter Bürgisser, Felipe Cucker and Paulin de Naurois
The Complexity of Semilinear Problems in Succinct Representation

Session 9B

Kouichi Hirata, Megumi Kuwabara and Masateru Harao
On Finding Acyclic Subhypergraphs

Markus Bläser and Shankar Ram Lashminarayanan
An Improved Approximation for TSP with Distances One and Two

Andreas Brandstädt, Van Bang Le and Suhail Mahfud
New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem

12:00 - 13:00 h

Session 10A

Benedikt Bollig
On the Expressiveness of Asynchronous Cellular Automata

Julien Bernet and David Janin
Tree Automata and Discrete Distributed Games

Session 10B

Yo-Sub Han and Derick Wood
A New Linearizing Restriction in the Pattern Matching Problem

Yusuke Ishida, Shunsuke Inenaga, Ayumi Shinohara and Masayuki Takeda
Fully Incremental LCS Computation

13:00 h

Farewell. End of the Conference!