Institut
für
Theoretische Informatik
Universität zu Lübeck
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! |