17. STACS 2000: Lille, France

• Mohammad Amin Shokrollahi:
  Codes and Graphs. 1-12
  
• Thomas A. Henzinger, Rupak Majumdar:
  A Classification of Symbolic Transition Systems. 13-34
  
• Pascal Koiran:
  Circuits versus Trees in Algebraic Complexity. 35-52
  
• Kaustubh Deshmukh, Priti Shankar, Amitava Dasgupta, B. Sundar Rajan:
  On the Many Faces of Block Codes. 53-64
  
• Edward A. Hirsch:
  A New Algorithm for MAX-2-SAT. 65-73
  
• Jack H. Lutz, Martin Strauss:
  Bias Invariance of Small Upper Spans. 74-86
  
• Eric Allender, Meena Mahajan:
  The Complexity of Planarity Testing. 87-98
  
• Gwénaël Richomme, Francis Wlazinski:
  About Cube-Free Morphisms. 99-109
  
• Jarkko Kari:
  Linear Cellular Automata with Multiple State Variables. 110-121
  
• Lucian Ilie, Wojciech Plandowski:
  Two-Variable Word Equations. 122-132
  
• Andris Ambainis, Ronald de Wolf:
  Average-Case Quantum Query Complexity. 133-144
  
• Juraj Hromkovic, Martin Sauerhoff:
  Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs. 145-156
  
• Sven Kosub, Klaus W. Wagner:
  The Boolean Hierarchy of NP-Partitions. 157-168
  
• Hesham Al-Ammal, Leslie Ann Goldberg, Philip D. MacKenzie:
  Binary Exponential Backoff Is Stable for High Arrival Rates. 169-180
  
• Nicolas Schabanel:
  The Data Broadcast Problem with Preemption. 181-192
  
• Jessica H. Fong, Martin Strauss:
  An Approximate L^p-Difference Algorithm for Massive Data Streams. 193-204
  
• Paolo Penna:
  Succinct Representations of Model Based Belief Revision. 205-216
  
• Leonid Libkin:
  Logics Capturing Local Properties. 217-229
  
• Edith Hemaspaandra:
  The Complexity of Poor Man's Logic. 230-242
  
• Yijie Han:
  Fast Integer Sorting in Linear Space. 242-253
  
• Stefan Edelkamp, Ingo Wegener:
  On the Performance of WEAK-HEAPSORT. 254-266
  
• Luca Aceto, Zoltán Ésik, Anna Ingólfsdóttir:
  On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers. 267-278
  
• Catalin Dima:
  Real-Time Automata and the Kleene Algebra of Sets of Real Numbers. 279-289
  
• Marcin Jurdzinski:
  Small Progress Measures for Solving Parity Games. 290-301
  
• Frédéric Magniez:
  Multi-linearity Self-Testing with Relative Error. 302-313
  
• Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán:
  Nondeterministic Instance Complexity and Hard-to-Prove Tautologies. 314-323
  
• Jack H. Lutz, Vikram Mhetre, Sridhar Srinivasan:
  Hard Instances of Hard Problems. 324-333
  
• Petr Jancar, Antonín Kucera, Faron Moller:
  Simulation and Bisimulation over One-Counter Processes. 334-345
  
• Alain Finkel, Grégoire Sutre:
  Decidability of Reachability Problems for Classes of Two Counters Automata. 346-357
  
• Marcin Jurdzinski, Mogens Nielsen:
  Hereditary History Preserving Bisimilarity Is Undecidable. 358-369
  
• Michael Elkin, David Peleg:
  The Hardness of Approximating Spanner Problems. 370-381
  
• Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger:
  An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality. 382-394
  
• Hans L. Bodlaender, Ton Kloks, Richard B. Tan, Jan van Leeuwen:
  lambda-Coloring of Graphs. 395-406
  
• Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek:
  Optimal Proof Systems and Sparse Sets. 407-418
  
• Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Sebastiaan Terwijn:
  Almost Complete Sets. 419-430
  
• Vikraman Arvind, Johannes Köbler:
  Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results. 431-442
  
• Evripidis Bampis, Rodolphe Giroudeau, Jean-Claude König:
  An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications. 443-454
  
• Klaus Jansen, Maxim Sviridenko:
  Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem. 455-465
  
• Ulf Lorenz:
  Controlled Conspiracy-2 Search. 466-478
  
• Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis:
  The Stability of Saturated Linear Dynamical Systems Is Undecidable. 479-490
  
• Julien Cervelle, Bruno Durand:
  Tilings: Recursivity and Regularity. 491-502
  
• Vincent Bouchitté, Ioan Todinca:
  Listing All Potential Maximal Cliques of a Graph. 503-515
  
• Michal Katz, Nir A. Katz, David Peleg:
  Distance Labeling Schemes for Well-Separated Graph Classes. 516-528
  
• Jean-Marc Lanlignel, Olivier Raynaud, Eric Thierry:
  Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphs. 529-541
  
• Joost Engelfriet, Sebastian Maneth:
  Characterizing and Deciding MSO-Definability of Macro Tree Transductions. 542-554
  
• Christian Glaßer, Heinz Schmitz:
  Languages of Dot-Depth 3/2. 555-566
  
• Alberto Bertoni, Massimiliano Goldwurm, Massimo Santini:
  Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures. 567-580
  
• Elias Koutsoupias, David Scot Taylor:
  The CNN Problem and Other k-Server Variants. 581-592
  
• Marek Chrobak, Jiri Sgall:
  The Weighted 2-Server Problem. 593-604
  
• Yair Bartal, Elias Koutsoupias:
  On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem. 605-613
  
• Mikael Goldmann, Alexander Russell:
  Spectral Bounds on General Hard Core Predicates. 614-625
  
• Annalisa De Bonis, Alfredo De Santis:
  Randomness in Visual Cryptography. 626-638
  
• Norbert Ascheuer, Sven Oliver Krumke, Jörg Rambau:
  Online Dial-a-Ride Problems: Minimizing the Completion Time. 639-650
  
• Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri:
  The Power Range Assignment Problem in Radio Networks on the Plane. 651-660