19. STACS 2002: Antibes Juan-les-Pins, France

Invited Papers

• Yan Zong Ding, Michael O. Rabin:
  Hyper-Encryption and Everlasting Security. 1-26
  
• Christian Scheideler:
  Models and Techniques for Communication in Dynamic Networks. 27-49
  
• Gilles Dowek:
  What Is a Theory? 50-64
  

Algorithms

• Pierre Fraigniaud, Cyril Gavoille:
  A Space Lower Bound for Routing in Trees. 65-75
  
• Amos Korman, David Peleg, Yoav Rodeh:
  Labeling Schemes for Dynamic Tree Networks. 76-87
  
• Micah Adler, Adi Rosén:
  Tight Bounds for the Performance of Longest-in-System on DAGs. 88-99
  
• Klaus Jansen:
  Approximate Strong Separation with Application in Fractional Graph Coloring and Preemptive Scheduling. 100-111
  
• Benjamin Doerr:
  Balanced Coloring: Equally Easy for All Numbers of Colors? 112-120
  
• Johannes Köbler, Jacobo Torán:
  The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3. 121-132
  
• Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino:
  On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets. 133-141
  
• Khaled M. Elbassioni:
  On Dualization in Products of Forests. 142-153
  
• Renaud Lepère, Christophe Rapine:
  An Asymptotic O(ln rho/ln ln rho)-Approximation Algorithm for the Scheduling Problem with Duplication on Large Communication Delay Graphs. 154-165
  
• Hannah Bast:
  Scheduling at Twilight the Easy Way. 166-178
  
• Alain Darte, Guillaume Huard:
  Complexity of Multi-dimensional Loop Alignment. 179-191
  
• Thomas Hofmeister, Uwe Schöning, Rainer Schuler, Osamu Watanabe:
  A Probabilistic 3-SAT Algorithm Further Improved. 192-202
  
• Ulf Lorenz, Burkhard Monien:
  The Secret of Selective Game Tree Search, When Using Random-Error Evaluations. 203-214
  
• Victor Y. Pan:
  Randomized Acceleration of Fundamental Matrix Computations. 215-226
  
• L. Sunil Chandran, L. Shankar Ram:
  Approximations for ATSP with Parametrized Triangle Inequality. 227-237
  
• Joachim Giesen, Matthias John:
  A New Diagram from Disks in the Plane. 238-249
  
• Stefan Langerman, Pat Morin, Michael A. Soss:
  Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees, and Cycles. 250-261
  

Current Challenges

• Michael R. Fellows, Jens Gramm, Rolf Niedermeier:
  On the Parameterized Intractability of CLOSEST SUBSTRINGsize and Related Problems. 262-273
  
• Rolf Backofen, N. S. Narayanaswamy, Firas Swidan:
  On the Complexity of Protein Similarity Search under mRNA Structure Constraints. 274-286
  
• Manuel Bodirsky, Martin Kutz:
  Pure Dominance Constraints. 287-298
  
• Peter Høyer, Ronald de Wolf:
  Improved Quantum Communication Complexity Bounds for Disjointness and Equality. 299-310
  
• Harumichi Nishimura:
  On Quantum Computation with Some Restricted Amplitudes. 311-322
  
• Mark Adcock, Richard Cleve:
  A Quantum Goldreich-Levin Theorem with Cryptographic Applications. 323-334
  
• Hartmut Klauck:
  On Quantum and Approximate Privacy. 335-346
  
• Mart de Graaf, Ronald de Wolf:
  On Quantum Versions of the Yao Principle. 347-358
  

Computational and Structural Complexity

• Jörg Flum, Martin Grohe:
  Describing Parameterized Complexity Classes. 359-371
  
• Matthias Krause:
  On the Computational Power of Boolean Decision Lists. 372-383
  
• Hans-Ulrich Simon:
  How Many Missing Answers Can Be Tolerated by Query Learners? 384-395
  
• Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe:
  Games with a Uniqueness Property. 396-407
  
• Aduri Pavan, Alan L. Selman:
  Bi-Immunity Separates Strong NP-Completeness Notions. 408-418
  
• Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik:
  Complexity of Semi-algebraic Proofs. 419-430
  
• Philipp Woelfel:
  A Lower Bound Technique for Restricted Branching Programs and Applications. 431-442
  
• Andrei A. Krokhin, Peter Jeavons, Peter Jonsson:
  The Complexity of Constraints on Intervals and Lengths. 443-454
  

Automata and Formal Languages

• Denis Thérien, Thomas Wilke:
  Nesting Until and Since in Linear Temporal Logic. 455-464
  
• Till Tantau:
  Comparing Verboseness for Finite Automata and Turing Machines. 465-476
  
• Daniel Krob, Jean Mairesse, Ioannis Michos:
  On the Average Parallelism in Trace Monoids. 477-488
  
• Dietrich Kuske:
  A Further Step towards a Theory of Regular MSC Languages. 489-500
  
• Volker Diekert, Markus Lohrey:
  Existential and Positive Theories of Equations in Graph Products. 501-512
  
• Holger Petersen:
  The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL. 513-522
  
• Rémi Morin:
  Recognizable Sets of Message Sequence Charts. 523-534
  
• Jirí Srba:
  Strong Bisimilarity and Regularity of Basic Parallel Processes Is PSPACE-Hard. 535-546
  
• Marie-Pierre Béal, Dominique Perrin:
  On the Enumerative Sequences of Regular Languages on k Symbols. 547-558
  

Logic in Computer Science

• Christof Löding:
  Ground Tree Rewriting Graphs of Bounded Tree Width. 559-570
  
• Deepak D'Souza, P. Madhusudan:
  Timed Control Synthesis for External Specifications. 571-582
  
• Jos C. M. Baeten, Erik P. de Vink:
  Axiomatizing GSOS with Termination. 583-595
  
• Achim Blumensath:
  Axiomatising Tree-Interpretable Structures. 596-607
  
• Emanuel Kieronski:
  EXPSPACE-Complete Variant of Guarded Fragment with Transitivity. 608-619
  
• Stéphane Demri, François Laroussinie, Ph. Schnoebelen:
  A Parametric Analysis of the State Explosion Problem in Model Checking. 620-631
  
• Markus Frick:
  Generalized Model-Checking over Locally Tree-Decomposable Classes. 632-644
  
• Martin Grohe, György Turán:
  Learnability and Definability in Trees and Similar Structures. 645-658