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



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



Home
        
Call for Papers 

Program

Important Dates

Conference Venue

Invited Speakers


Program Committee

Organizing Committee

Registration 

Accomodation

Contact

Previous FCT

Location

Pictures

Travel Information

Sightseeing









Conference Program




Wednesday 17.08.2005






17:00 - 20:00 h



Registration








19:00 - 21:00 h



Reception








Thursday 18.08.2005







08:30 h



Registration









09:00 - 09:10 h



Welcome
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



Lunch



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


Lunch




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



Excursion








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!