25th International Symposium on Theoretical Aspects of Computer Science

STACS 2008

Program

  • Plenary talks will be in the LaBRI amphitheatre (building A30).
  • Talks for the A track will be in amphitheatre A of building A29.
  • Talks for the B track will be in LaBRI amphitheatre.

Thursday 21 February

8:00-9:00 Registration

LaBRI, conference site, Building A30, University Bordeaux I

9:00-10:00 Maxime Crochemore and Lucian Ilie,

Understanding Maximal Repetitions in Strings

(mirror: Germany, France)

Chair: S. Albers
Coffee break
Session 1A
Chair: R. Klasing
Session 1B
Chair: A. Muscholl
10:20-10:45 Mirela Damian, Robin Flatland, Joseph O'Rourke and Suneeta Ramaswami.

Connecting Polygonizations via Stretches and Twangs

(mirror: Germany France)

Laurent Bienvenu, Andrej Muchnik, Alexander Shen and Nikolay Vereshchagin.

Limit complexities revisited

(mirror: Germany, France)

10:45-11:10 Atlas F. Cook IV and Carola Wenk.

Geodesic Fréchet Distance Inside a Simple Polygon

(mirror: Germany, France)

Pilar Albert, Elvira Mayordomo, Philippe Moser and Sylvain Perifel.

Pushdown Compression

(mirror: Germany, France)

11:10-11:35 Iyad A. Kanj and Ljubomir Perković.

On Geometric Spanners of Euclidean and Unit Disk Graphs

(mirror: Germany, France)

Angsheng Li and Mingji Xia.

A Theory for Valiant's Matchcircuits

(mirror: Germany, France)

Coffee break
Session 2A
Chair: E. Grandjean
Session 2B
Chair: M. Lohrey
11:50-12:15 Chandan Saha.

Factoring Polynomials over Finite Fields using Balance Test

(mirror: Germany, France)

Jean-François Dufourd.

Discrete Jordan Curve Theorem: A proof formalized in Coq with hypermaps

(mirror: Germany, France)

12:15-12:40 Javier Esparza, Stefan Kiefer and Michael Luttenberger.

Convergence Thresholds of Newton's Method for Monotone Polynomial Equations

(mirror: Germany, France)

Edith Hemaspaandra and Henning Schnoor.

On the Complexity of Elementary Modal Logics

(mirror: Germany, France)

Lunch break
Session 3A
Chair: C. Gavoille
Session 3B
Chair: C. Löding
14:30-14:55 Johan M. M. van Rooij and Hans L. Bodlaender.

Design by Measure and Conquer - A Faster Exact Algorithm for Dominating Set

(mirror: Germany, France)

Jacques Sakarovitch and Rodrigo de Souza.

On the Decomposition of k-valued Rational Relations

(mirror: Germany, France)

14:55-15:20 Andreas Björklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto.

Trimmed Moebius Inversion and Graphs of Bounded Degree

(mirror: Germany, France)

Wouter Gelade and Frank Neven.

Succinctness of the Complement and Intersection of Regular Expressions

(mirror: Germany, France)

15:20-15:45 Julián Mestre.

Lagrangian Relaxation and Partial Cover

(mirror: Germany, France)

Antti Valmari and Petri Lehtinen.

Efficient Minimization of DFAs with Partial Transition Functions

(mirror: Germany, France)

Coffee break
Session 4A
Chair: V. Diekert
Session 4B
Chair: I. Walukiewicz
16:00-16:25 Chao Chen and Daniel Freedman.

Quantifying Homology Classes

(mirror: Germany, France)

Patricia Bouyer, Nicolas Markey, Joël Ouaknine, Philippe Schnoebelen and James Worrell.

On Termination for Faulty Channel Machines

(mirror: Germany, France)

16:25-16:50 Joshua Brody and Amit Chakrabarti.

Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound

(mirror: Germany, France)

Diana Fischer, Erich Grädel and Łukasz Kaiser.

Model Checking Games for the Quantitative μ-Calculus

(mirror: Germany, France)

16:50-17:15 Artur Jeż and Alexander Okhotin.

Complexity of solutions of equations over sets of natural numbers

(mirror: Germany, France)

Dietrich Kuske.

Compatibility of Shelah and Stupp's and Muchnik's Iterations with Fragments of Monadic Second Order Logic

(mirror: Germany, France)

17:45-19:00 Wine conference and degustation in Chateau Peixotto (City council of Talence)

Walking distance from LaBRI (see map)

Friday 22 February

9:00-10:00 Mihalis Yannakakis,

Equilibria, Fixed Points and Complexity Classes

(mirror: Germany, France)

Chair: K. Iwama
Coffee break
Session 5A
Chair: A. Raspaud
Session 5B
Chair: P. Gastin
10:20-10:45 Samir Datta, Raghav Kulkarni and Sambuddha Roy.

Deterministically Isolating a Matching in Bipartite Planar Graphs

(mirror: Germany, France)

Andris Ambainis.

Quantum search with variable times

(mirror: Germany, France)

10:45-11:10 Thomas Erlebach, Michael Hoffmann, Danny Krizanc, Matúš Mihal'ák and Rajeev Raman.

Computing Minimum Spanning Trees with Uncertainty

(mirror: Germany, France)

Bill Rosgen.

Distinguishing Short Quantum Computations

(mirror: Germany, France)

11:10-11:35 Éric Colin de Verdière and Alexander Schrijver.

Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs

(mirror: Germany, France)

Alexis Ballier, Bruno Durand and Emmanuel Jeandel.

Structural aspects of tilings

(mirror: Germany, France)

Coffee break
Session 6A
Chair: Ch. Frougny
Session 6B
Chair: S. Albers
11:50-12:15 Markus Bläser and Christian Hoffmann.

On the Complexity of the Interlace Polynomial

(mirror: Germany, France)

Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela and Leen Stougie.

Minimizing Flow Time in the Wireless Gathering Problem

(mirror: Germany, France)

12:15-12:40 Thomas Thierauf and Fabian Wagner.

The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace

(mirror: Germany, France)

Zvi Lotker, Boaz Patt-Shamir and Dror Rawitz.

Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental

(mirror: Germany, France)

Lunch break
Session 7A
Chair: N. Hanusse
Session 7B
Chair: M. Bousquet-Mélou
14:30-14:55 Ulrich Meyer.

On Dynamic Breadth-First Search in External-Memory

(mirror: Germany, France)

Jui-Yi Kao, Jeffrey Shallit and Zhi Xu.

The Frobenius Problem in a Free Monoid

(mirror: Germany, France)

14:55-15:20 Shachar Lovett.

Lower bounds for adaptive linearity tests

(mirror: Germany, France)

Jean-Éric Pin and Pedro V. Silva.

A Mahler's theorem for functions from words to integers

(mirror: Germany, France)

15:20-15:45 Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener and Philipp Woelfel.

Tight Bounds for Blind Search on the Integers

(mirror: Germany, France)

Marni Mishna and Mike Zabrocki.

Analytic aspects of the shuffle product

(mirror: Germany, France)

Coffee break
Session 8A
Chair: M. Robson
Session 8B
Chair: L. Ségoufin
16:00-16:25 Iyad A. Kanj, Michael J. Pelsmajer, Marcus Schaefer and Ge Xia.

On the Induced Matching Problem

(mirror: Germany, France)

Felix Klaedtke.

Ehrenfeucht-Fraïssé Goes Automatic for Real Addition

(mirror: Germany, France)

16:25-16:50 Viet Tung Hoang and Wing-Kin Sung.

Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees

(mirror: Germany, France)

Lukasz Kaiser, Sasha Rubin and Vince Bárány.

Cardinality and counting quantifiers on omega-automatic structures

(mirror: Germany, France)

16:50-17:15 Mariano Zelke.

Weighted Matching in the Semi-Streaming Model

(mirror: Germany, France)

Tobias Ganzow and Sasha Rubin.

Order-Invariant MSO is Stronger than Counting MSO in the Finite

(mirror: Germany, France)

20:00-23:00 Banquet in Palais Rohan (City council of Bordeaux)

Tram station Pey Berland (see map)

Saturday 23 February

9:00-10:00 Thomas Schwentick,

A Little Bit Infinite? On Adding Data to Finitely Labelled Structures

(mirror: Germany, France)

Chair: P. Weil
Coffee break
Session 9A
Chair: J. Esparza
Session 9B
Chair: J. Karhumäki
10:20-10:45 Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff and Alexander Wolff.

Trimming of Graphs, with Application to Point Labeling

(mirror: Germany, France)

Arist Kojevnikov and Sergey I. Nikolenko.

New Combinatorial Complete One-Way Functions

(mirror: Germany, France)

10:45-11:10 Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, M. Sohel Rahman and Tomasz Waleń.

Improved Algorithms for the Range Next Value Problem and Applications

(mirror: Germany, France)

Jeff Kinne and Dieter van Melkebeek.

Space Hierarchy Results for Randomized Models

(mirror: Germany, France)

11:10-11:35 Sören Lauen.

Geometric Set Cover and Hitting Sets for Polytopes in R3

(mirror: Germany, France)

Venkatesan T. Chakaravarthy and Sambuddha Roy.

Finding Irrefutable Certificates for S2p via Arthur and Merlin

(mirror: Germany, France)

Coffee break
Session 10A
Chair: B. Vöcking
Session 10B
Chair: W. Thomas
11:50-12:15 Pinyan Lu and Changyuan Yu.

An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines

(mirror: Germany, France)

Christian Glaßer, Heinz Schmitz and Victor Selivanov.

Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

(mirror: Germany, France)

12:15-12:40 Patrick Briest, Martin Hoefer and Piotr Krysta.

Stackelberg Network Pricing Games

(mirror: Germany, France)

Filip Murlak.

Weak index versus Borel rank

(mirror: Germany, France)

End of conference