STACS 2004 21st Symposium on Theoretical Aspects of Computer Science Le Corum, Montpellier, France March 25-27, 2004

Wednesday 24th

Thursday 25th

• Approximation Schemes for Metric Clustering Problems
  Claire Kenyon

• Individual communication Complexity
  Vereshchagin Nikolai, Vitanyi Paul, Klauck Hartmut, Buhrman Harry
• The Complexity of Satisfiability Problems over Finite Lattices
  Schwarz Bernhard
• Constant width planar computation characterizes ACC0
  Arnsfelt Hansen Kristoffer

• A Simple and Fast Approach for Solving Problems on Planar Graphs
  Fomin Fedor, Thilikos Dimitrios
• Sum-Multicoloring on Paths
  Kovacs Annamaria
• Matching Algorithms are Fast in Sparse Random Graphs
  Bast Holger, Mehlhorn Kurt, Schäfer Guido, Tamaki Hisao

• Algebraic Results on Quantum Automata
  Ambainis Andris, Beaudry Martin, Golovkins Marats, Kikusts Arnolds, Mercer Mark, Thérien Denis
• Quantum Identification of Boolean Oracles
  Ambainis Andris, Iwama Kazuo, Kawachi Akinori, Masuda Hiroyuki, Putra Raymond, Yamashita Shigeru

• Effective Strong Dimension in Algorithmic Information and Computational Complexity
  Athreya Krishna B., Hitchock John M., Lutz Jack H., Mayordomo Elvira
• A Lower Bound on the Competitive Ratio of Truthful Auctions
  Goldberg Andrew, Hartline Jason, Karlin Anna, Saks Michael

• Algorithms for SAT based on search in Hamming balls
  Dantsin Evgeny, Hirsch Edward A., Wolpert Alexander
• Identifying Efficiently Solvable Cases of Max CSP
  Cohen David, Cooper Martin, Jeavons Peter, Krokhin Andrei
• The Complexity of Boolean Constraint Isomorphism
  Böhler Elmar, Hemaspaandra Edith, Reith Steffen, Vollmer Heribert

• On minimizing the total weighted tardiness on a single machine
  Kolliopoulos Stavros, Steiner George
• Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs
  Bartal Yair, Chin Francis Y. L., Chrobak Marek, Fung Stanley P. Y., Jawor Wojciech, Lavi Ron, Sgall Jiri, Tichy Tomas
• Optimal and online preemptive scheduling on uniformly related machines Ebenlendr Tomas, Sgall Jiri

• Parallel Prefetching and Caching is Hard
  Ambühl Christoph, Weber Birgitta
• Strongly Stable Matchings in Time O(nm) and Extension to the H/R Problem
  Kavitha Telikepalli, Mehlhorn Kurt, Michail Dimitrios, Paluch Katarzyna
• Approximation algorithms for minimizing average distortion
  Dhamdhere Kedar, Gupta Anupam, Ravi R.

• The syntactic graph of a sofic shift
  Béal Marie-Pierre, Fiorenzi Francesca, Perrin Dominique
• Periodicity and Unbordered Words
  Harju Tero, Nowotka Dirk
• Desert Automata and the Finite Substitution Problem
  Kirsten Daniel

Friday 26th

• Title to be announced
  Robin Thomas

• Directed Graphs Exploration with Little Memory
  Fraigniaud Pierre, Ilcinkas David
• Approximate Path Coloring with Applications to Wavelength Assignment in WDM
  Caragiannis Ioannis, Kaklamanis Christos
• An algorithmic view on OVSF code assignment
  Erlebach Thomas, Jacob Riko, Mihalak Matus, Nunkesser Marc, Szabo Gabor, Widmayer Peter

• Satisfiability Problems Complete for Deterministic Logarithmic Space
  Johannsen Jan
• A Logspace Approximation Scheme for The Shortest Path Problem for Graphs...
  Tantau Till
• The Minimal Logically-Defined NP-complete Problem
  Barbanchon Regis, Grandjean Etienne

• Solving the 2-Disjoint Paths Problem in Nearly Linear Time
  Tholey Torsten
• Simpler computation of single-source shortest paths in linear average-time
  Hagerup Torben 

• Lattices with Many Cycles Are Dense
  Trolin Mårten
• Automata-based Analysis of Recursive Cryptographic Protocols
  Kuesters Ralf, Wilke Thomas

• On Minimum Circular Arrangement
  Ganapathy Murali K., Lodha Sachin
• Integral Symmetric 2-Commodity Flows
  Jarry Aubin
• Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-hoc Wireless Networks
  Ambulh Christoph, Clementi Andrea E.F., Di Ianni Miriam, Lev-Tov Nissan, Monti Angelo, Peleg David, Rossi Gianluca, Silvestri Riccardo

• On the Expressiveness of Deterministic Transducers over Infinite Trees
  Colcombet Thomas, Löding Christof
• Definability and Regularity in Automatic Structures
  Khoussainov Bakhadyr, Rubin Sasha, Stephan Frank
• Active Context-Free Games
  Muscholl Anca, Schwentick Thomas, Segoufin Luc

• Worst Case Performance of Approximation Algorithm for Asymmetric TSP
  Palbom Anna
  
• On Visibility Representation of Plane Graphs
  Zhang Huaming, He Xin
• Topology Matters: Smoothed Competitiveness of Metrical Task Systems
  Schäfer Guido, Sivadasan Naveen

• A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees
  Laber Eduardo
• The Plurality Problem with Three Colors
   De Marco Gianluca, Aigner Martin, De Marco Gianluca, Montangero Manuela
• What can be efficiently reduced to the K-random strings?
  Allender Eric, Buhrman Harry, Koucky Michal

Saturday 27th

• Positional Determinacy of Infinite Games
  Erich Grädel
  

• An Information Theoretic Lower Bound for Broadcasting in Radio Networks
  Brito Carlos, Gafni Eli, Vaya Shailesh
  
• A new model for selfish routing rode manuel
  Lucking Thomas, Mavronicolas Marios, Monien Burkhard, Rode Manuel
• Broadcast in the Rendezvous Model
  Duchon Philippe, Hanusse Nicolas, Saheb Nasser, Zemmari Akka

• Time-Space Tradeoff in Derandomizing Probabilistic Logspace
  Cai Jin-Yi, Chakaravarthy Venkatesan, van Melkebeek Dieter
• A Measured Collapse of The Modal mu-Calculus Alternation Hierarchy
  Bustan Doron, Kupferman Orna, Vardi Moshe Y.
• Regular Language Matching and Other Decidable Cases of The Satisfiability Problem
  Bala Sebastian

• Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines
  Auletta Vincenzo, De Prisco Roberto, Penna Paolo, Persiano Pino
• The expected competitive ratio for weighted completion time scheduling Souza Alexander, Steger Angelika

• Local limit distributions in pattern statistics: beyond the Markovian model Bertoni Alberto, Choffrut Christian, Goldwurm Massimiliano, Lonati Violetta
• A Discontinuity in Pattern Inference
  Reidenbach Daniel