21. STACS 2004: Montpellier, France

Invited Lectures

• Claire Kenyon:
  Approximation Schemes for Metric Clustering Problems. 1-3
  
• Erich Grädel:
  Positional Determinacy of Infinite Games. 4-18
  

Structural Complexity (I)

• Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi:
  Individual Communication Complexity: Extended Abstract. 19-30
  
• Bernhard Schwarz:
  The Complexity of Satisfiability Problems over Finite Lattices. 31-43
  
• Kristoffer Arnsfelt Hansen:
  Constant Width Planar Computation Characterizes ACC⁰. 44-55
  

Graph Algorithms (I)

• Fedor V. Fomin, Dimitrios M. Thilikos:
  A Simple and Fast Approach for Solving Problems on Planar Graphs. 56-67
  
• Annamária Kovács:
  Sum-Multicoloring on Paths. 68-80
  
• Holger Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki:
  Matching Algorithms Are Fast in Sparse Random Graphs. 81-92
  

Quantum Computations

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

Pattern Inference and Statistics

• Alberto Bertoni, Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati:
  Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models. 117-128
  
• Daniel Reidenbach:
  A Discontinuity in Pattern Inference. 129-140
  

Satisfiability - Constraint Satisfaction Problem

• Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert:
  Algorithms for SAT Based on Search in Hamming Balls. 141-151
  
• David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin:
  Identifying Efficiently Solvable Cases of Max CSP. 152-163
  
• Elmar Böhler, Edith Hemaspaandra, Steffen Reith, Heribert Vollmer:
  The Complexity of Boolean Constraint Isomorphism. 164-175
  

Scheduling (I)

• Stavros G. Kolliopoulos, George Steiner:
  On Minimizing the Total Weighted Tardiness on a Single Machine. 176-186
  
• Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jiri Sgall, Tomás Tichý:
  Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs. 187-198
  
• Tomás Ebenlendr, Jiri Sgall:
  Optimal and Online Preemptive Scheduling on Uniformly Related Machines. 199-210
  

Algorithms

• Christoph Ambühl, Birgitta Weber:
  Parallel Prefetching and Caching Is Hard. 211-221
  
• Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch:
  Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem. 222-233
  
• Kedar Dhamdhere, Anupam Gupta, R. Ravi:
  Approximation Algorithms for Minimizing Average Distortion. 234-245
  

Networks (I)

• Pierre Fraigniaud, David Ilcinkas:
  Digraphs Exploration with Little Memory. 246-257
  
• Ioannis Caragiannis, Christos Kaklamanis:
  Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks. 258-269
  
• Thomas Erlebach, Riko Jacob, Matús Mihalák, Marc Nunkesser, Gábor Szabó, Peter Widmayer:
  An Algorithmic View on OVSF Code Assignment. 270-281
  

Automata Theory and Words

• Marie-Pierre Béal, Francesca Fiorenzi, Dominique Perrin:
  The Syntactic Graph of a Sofic Shift. 282-293
  
• Tero Harju, Dirk Nowotka:
  Periodicity and Unbordered Words: A Proof of Duval?s Conjecture. 294-304
  
• Daniel Kirsten:
  Desert Automata and the Finite Substitution Problem. 305-316
  

Structural Complexity (II)

• Jan Johannsen:
  Satisfiability Problems Complete for Deterministic Logarithmic Space. 317-325
  
• Till Tantau:
  A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number. 326-337
  
• Régis Barbanchon, Etienne Grandjean:
  The Minimal Logically-Defined NP-Complete Problem. 338-349
  

Path Algorithms

• Torsten Tholey:
  Solving the 2-Disjoint Paths Problem in Nearly Linear Time. 350-361
  
• Torben Hagerup:
  Simpler Computation of Single-Source Shortest Paths in Linear Average Time. 362-369
  

Cryptography

• Mårten Trolin:
  Lattices with Many Cycles Are Dense. 370-381
  
• Ralf Küsters, Thomas Wilke:
  Automata-Based Analysis of Recursive Cryptographic Protocols. 382-393
  

Networks (II)

• Murali K. Ganapathy, Sachin Lodha:
  On Minimum Circular Arrangement. 394-405
  
• Aubin Jarry:
  Integral Symmetric 2-Commodity Flows. 406-417
  
• Christoph Ambühl, Andrea E. F. Clementi, Miriam Di Ianni, Nissan Lev-Tov, Angelo Monti, David Peleg, Gianluca Rossi, Riccardo Silvestri:
  Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks. 418-427
  

Logic and Formal Languages

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

Graphs Algorithms (II)

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

Game Theory and Complexity

• Eduardo Sany Laber:
  A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees. 501-512
  
• Martin Aigner, Gianluca De Marco, Manuela Montangero:
  The Plurality Problem with Three Colors. 513-521
  
• Doron Bustan, Orna Kupferman, Moshe Y. Vardi:
  A Measured Collapse of the Modal µ-Calculus Alternation Hierarchy. 522-533
  

Networks (III)

• Carlos Brito, Eli Gafni, Shailesh Vaya:
  An Information Theoretic Lower Bound for Broadcasting in Radio Networks. 534-546
  
• Thomas Lücking, Marios Mavronicolas, Burkhard Monien, Manuel Rode:
  A New Model for Selfish Routing. 547-558
  
• Philippe Duchon, Nicolas Hanusse, Nasser Saheb, Akka Zemmari:
  Broadcast in the Rendezvous Model. 559-570
  

Structural Complexity (III)

• Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek:
  Time-Space Tradeoff in Derandomizing Probabilistic Logspace. 571-583
  
• Eric Allender, Harry Buhrman, Michal Koucký:
  What Can be Efficiently Reduced to the K-Random Strings? 584-595
  
• Sebastian Bala:
  Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints between Regular Open Terms. 596-607
  

Scheduling (II)

• Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano:
  Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines. 608-619
  
• Alexander Souza, Angelika Steger:
  The Expected Competitive Ratio for Weighted Completion Time Scheduling. 620-631
  

Algorithmic Information

• Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo:
  Effective Strong Dimension in Algorithmic Information and Computational Complexity. 632-643
  
• Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks:
  A Lower Bound on the Competitive Ratio of Truthful Auctions. 644-655
  

Errata

• Marek Chrobak, Jiri Sgall:
  Errata to Analysis of the Harmonic Algorithm for Three Servers. 656