Conference Program

 
Download:
program.ps / program.pdf

 

Wednesday, 23.02.2005
 
16:00 Faculty Colloquium, University of Stuttgart
16:00-17:00, room V38.01 (open to all participants)
Manindra Agrawal: Primes is in P

 

Beginning of STACS:

 

Wednesday, 23.02.2005
 
17:30 Registration (Hotel Telekom, 17:30-20:00)
19:00 Welcome Reception (Hotel Telekom, 19:00-21:00)

 

 

Thursday, 24.02.2005
 
08:30 Registration
(Computer Science building, room 0.124)
09:00 Plenary session, invited Talk 1
Uwe Schöning
Algorithmics in Exponential Time
Chair: Volker Diekert
Room: V38.01
10:00 Coffee break
10:30 – Session 1 A –
Chair: Friedhelm Meyer auf der Heide
Room: V38.01
– Session 1 B –
Chair: Dietrich Kuske
Room: V38.04
Carsten Witt: Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics Lidia Tendera: Counting in the two variable guarded logic with transitivity
Petros Drineas, Ravi Kannan and Michael Mahoney: Sampling Sub-problems of Heterogeneous Max-Cut Problems and Approximation Algorithms Dietmar Berwanger and Giacomo Lenzi: The variable hierarchy of the mu-calculus is strict
Nir Andelman, Yossi Azar and Motti Sorani: Truthful Approximation Mechanisms for Scheduling Selfish Related Machines Manuel Bodirsky: The core of a countably categorical structure
11:55 – Session 2 A –
Chair: Brigitte Vallée
Room: V38.01
– Session 2 B –
Chair: Hendrik Jan Hoogeboom
Room: V38.04
Guillaume Theyssier: How Common Can Be Universality for Cellular Automata Tomas Brazdil, Antonin Kucera and Oldrich Strazovsky: On the Decidability of Temporal Properties of Probabilistic Pushdown Automata
Victor Poupet: Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods Detlef Kähler, Ralf Küsters and Thomas Wilke: Deciding Properties of Contract-Signing Protocols
12:50 Lunch
14:30 – Session 3 A –
Chair: Eric Allender
Room: V38.01
– Session 3 B –
Chair: Peter Høyer
Room: V38.04
Christian Glasser: Polylog-Time Reductions Decrease Dot-Depth Zdeněk Dvořák, Vít Jelínek, Daniel Král', Jan Kynčl and Michael Saks: Three Optimal Algorithms for Balls of Three Colors
Frank Harary, Wolfgang Slany and Oleg Verbitsky: On the Computational Complexity of the Forcing Chromatic Number Xiang-Yang Li and Zheng Sun: Cost Sharing and Strategyproof Mechanisms for Set Cover Games
Lars Engebretsen and Jonas Holmerin: More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP Petra Berenbrink, Tom Friedetzky, Zengjian Hu and Russ Martin: On Weighted Balls-into-bins Games
15:45 Coffee break
16:15 – Session 4 A –
Chair: Pascal Weil
Room: V38.01
– Session 4 B –
Chair: Rolf Klein
Room: V38.04
Gregorio Malajovich and Klaus Meer: Computing Multi-Homogeneous Bézout Numbers is Hard Sasanka Roy, Sandip Das and Subhas C. Nandy: Shortest Monotone Descent Path Problem in Polyhedral Terrain
Volker Weber and Thomas Schwentick: Dynamic Complexity Theory Revisited Markus Schmidt: Packet Buffering - Randomization Beats Deterministic Algorithms
Jianer Chen, Henning Fernau, Iyad Kanj and Ge Xia: Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size Abraham D. Flaxman and Bartosz Przydatek: Solving Medium-Density Subset Sum Problems in Expected Polynomial Time

 

 

Friday, 25.02.2005
 
09:00 Plenary session, invited Talk 2
Manindra Agrawal
Automorphisms of Finite Rings and Applications to Complexity of Problems
Chair: Eric Allender
Room: V38.01
10:00 Coffee break
10:30 – Session 5 A –
Chair: Hendrik Jan Hoogeboom
Room: V38.01
– Session 5 B –
Chair: Gilles Schaeffer
Room: V38.04
Hubie Chen: Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms Josep Diaz, Xavier Perez, Maria Serna and Nicholas Charles Wormald: Connectivity for wireless agents moving on a cycle or grid
Michael Benedikt and Luc Segoufin: Regular tree-languages definable in FO Marcin Bienkowski, Miroslaw Dynia and Miroslaw Korzeniowski: Improved Algorithms for Dynamic Page Migration
Kousha Etessami and Mihalis Yannakakis: Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Non-linear equations Prosenjit Bose, Evangelos Kranakis, Pat Morin and Yihui Tang: Approximate range mode and range median queries
11:55 – Session 6 A –
Chair: Ulrich Hertrampf
Room: V38.01
– Session 6 B –
Chair: Dietrich Kuske
Room: V38.04
Emmanuel Jeandel: Topological Automata Harry Buhrman, Ilan Newman, Nikolai Vereshchagin and Lance Fortnow: Increasing Kolmogorov Complexity
Gregor Gramlich and Georg Schnitger: Minimizing NFA's and Regular Expressions Wolfgang Merkle, Joseph Miller, Andre Nies, Jan Reimann and Frank Stephan: Kolmogorov-Loveland Randomness and Stochasticity
12:50 Lunch
14:30 – Session 7 A –
Chair: Jop Sibeyn
Room: V38.01
– Session 7 B –
Chair: Friedhelm Meyer auf der Heide
Room: V38.04
Nir Ailon and Bernard Chazelle: Information Theory in Property Testing and Monotonicity Testing in Higher Dimension Vikraman Arvind and Thirumalai Chakravarthi Vijayaraghavan: The Complexity of solving Linear Equations over a Finite Ring
Vittorio Bilò, Michele Flammini and Luca Moscardelli: On Nash Equilibria in Non-Cooperative All-Optical Networks Michael Kaminski: A lower bound on the complexity of polynomial multiplication over finite fields
Nikhil Bansal and Kirk Pruhs: Speed Scaling to Manage Temperature Andreas Krebs, Klaus-Jörn Lange and Stephanie Reifferscheid: Characterizing TC0 in Terms of Infinite Groups
15:45 Coffee break
16:15 – Session 8 A –
Chair: Giuseppe Persiano
Room: V38.01
– Session 8 B –
Chair: Brigitte Vallée
Room: V38.04
Joachim Gudmundsson, Giri Narasimhan and Michiel Smid: Fast pruning of geometric spanners Fabio Burderi and Antonio Restivo: Varieties of Codes and Kraft Inequality
Gerard Jennhwa Chang, Antonius J. J. Kloks, Jiping Liu and Sheng-Lung Peng: The PIGs Full Monty - A floor show of minimal separators Amnon Ta-Shma and Eran Rom: Improving the alphabet-size in high noise, almost optimal rate list decodable codes.
Ulrik Brandes and Daniel Fleischer: Centrality Measures Based on Current Flow Michal Kunc: The power of commuting with finite sets of words
  Conference Dinner

 

 

Saturday, 26.02.2005
 
09:00 Plenary session, invited Talk 3
Mireille Bousquet-Mélou
Algebraic series in enumerative combinatorics, and context-free languages
Chair: Bruno Durand
Room: V38.01
10:00 Coffee break
10:30 – Session 9 A –
Chair: Peter Høyer
Room: V38.01
– Session 9 B –
Chair: Jop Sibeyn
Room: V38.04
Seiichiro Tani, Hirotada Kobayashi and Keiji Matsumoto: Deterministic Leader Election via Distributed Quantum Computing Benjamin Doerr: Roundings Respecting Hard Constraints
Harry Buhrman, Ilan Newman, Hein Roehrig and Ronald de Wolf: Robust Polynomials and Quantum Algorithms Gianni Franceschini: Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves
Gus Gutoski and John Watrous: Quantum Interactive Proofs with Competing Provers Nicole Immorlica, Mohammad Mahdian and Vahab Mirrokni: Cycle Cover with Short Cycles
11:55 – Session 10 A –
Chair: Rolf Klein
Room: V38.01
– Session 10 B –
Chair: Gilles Schaeffer
Room: V38.04
Telikepalli Kavitha and Kurt Mehlhorn: A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs Violetta Lonati and Massimiliano Goldwurm: Pattern occurrences in multicomponent models
Surender Baswana, Vishrut Goyal and Sandeep Sen: All-pairs nearly 2-approximate shortest-paths in O(n2 polylog n) time Graham P Oliver and Richard M Thomas: Automatic presentations for finitely generated groups
12:50 Lunch