20. STACS 2003: Berlin, Germany

Invited Papers

• Victor Vianu:
  Logic as a Query Language: From Frege to XML. 1-12
  
• Alain Viari:
  How Does Computer Science Change Molecular Biology? 13
  

Contributed Papers

• Ching-Chi Lin, Hsueh-I Lu, I-Fan Sun:
  Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer. 14-25
  
• Ileana Streinu, Sue Whitesides:
  Rectangle Visibility Graphs: Characterization, Construction, and Compaction. 26-37
  
• Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel H. M. Smid, Norbert Zeh:
  Approximating Geometric Bottleneck Shortest Paths. 38-49
  
• Stefan Langerman, William L. Steiger:
  Optimization in Arrangements. 50-61
  
• Pascal Tesson, Denis Thérien:
  Complete Classifications for the Communication Complexity of Regular Languages. 62-73
  
• Juhani Karhumäki, Michel Latteux, Ion Petre:
  The Commutation with Codes and Ternary Sets of Words. 74-84
  
• Guillem Godoy, Ashish Tiwari, Rakesh M. Verma:
  On the Confluence of Linear Shallow Term Rewrite Systems. 85-96
  
• Victor L. Selivanov:
  Wadge Degrees of omega-Languages of Deterministic Turing Machines. 97-108
  
• Dariusz R. Kowalski, Andrzej Pelc:
  Faster Deterministic Broadcasting in Ad Hoc Radio Networks. 109-120
  
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Private Computations in Networks: Topology versus Randomness. 121-132
  
• Thomas Erlebach, Stamatis Stefanakos:
  On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements. 133-144
  
• Claus-Peter Schnorr:
  Lattice Reduction by Random Sampling and Birthday Methods. 145-156
  
• Qi Cheng:
  On the Ultimate Complexity of Factorials. 157-166
  
• Xizhong Zheng, Robert Rettinger, Burchard von Braunmühl:
  On the Effective Jordan Decomposability. 167-178
  
• Lucian Ilie, Baozhen Shan, Sheng Yu:
  Fast Algorithms for Extended Regular Expression Matching and Searching. 179-190
  
• Veli Mäkinen, Gonzalo Navarro, Esko Ukkonen:
  Algorithms for Transposition Invariant String Matching. 191-202
  
• Anton Mityagin:
  On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets. 203-211
  
• Harry Buhrman, Lance Fortnow, Aduri Pavan:
  Some Results on Derandomization. 212-222
  
• Eike Kiltz:
  On the Representation of Boolean Predicates of the Diffie-Hellman Function. 223-233
  
• Peter Høyer, Robert Spalek:
  Quantum Circuits with Unbounded Fan-out. 234-246
  
• Marek Chrobak, Jiri Sgall:
  Analysis of the Harmonic Algorithm for Three Servers. 247-259
  
• Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, Amitabh Sinha:
  Non-clairvoyant Scheduling for Minimizing Mean Slowdown. 260-270
  
• Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul G. Spirakis:
  Space Efficient Hash Tables with Worst Case Constant Access Time. 271-282
  
• Hervé Brönnimann, Frédéric Cazals, Marianne Durand:
  Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure. 283-294
  
• Beate Bollig:
  Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs. 295-306
  
• Martin Sauerhoff:
  Randomness versus Nondeterminism for Read-Once and Read- k Branching Programs. 307-318
  
• Petr Hlinený:
  Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids. 319-330
  
• Ricard Gavaldà, Denis Thérien:
  Algebraic Characterizations of Small Classes of Boolean Functions. 331-342
  
• John Hershberger, Subhash Suri, Amit M. Bhosle:
  On the Difficulty of Some Shortest Path Problems. 343-354
  
• Tomás Feder, Adam Meyerson, Rajeev Motwani, Liadan O'Callaghan, Rina Panigrahy:
  Representing Graph Metrics with Fewest Edges. 355-366
  
• Tomás Feder, Rajeev Motwani, Liadan O'Callaghan, Chris Olston, Rina Panigrahy:
  Computing Shortest Paths with Uncertainty. 367-378
  
• Andrei A. Krokhin, Benoit Larose:
  Solving Order Constraints in Logarithmic Space. 379-390
  
• Vasco Brattka:
  The Inversion Problem for Computable Linear Operators. 391-402
  
• Markus Bläser:
  Algebras of Minimal Rank over Arbitrary Fields. 403-414
  
• Oliver Giel, Ingo Wegener:
  Evolutionary Algorithms and the Maximum Matching Problem. 415-426
  
• Piotr Sankowski:
  Alternative Algorithms for Counting All Matchings in Graphs. 427-438
  
• Robert W. Irving, David Manlove, Sandy Scott:
  Strong Stability in the Hospitals/Residents Problem. 439-450
  
• Arnaud Durand, Miki Hermann:
  The Inference Problem for Propositional Circumscription of Affine Formulas Is coNP-Complete. 451-462
  
• Dietrich Kuske, Markus Lohrey:
  Decidable Theories of Cayley-Graphs. 463-474
  
• Stefan Szeider:
  The Complexity of Resolution with Generalized Symmetry Rules. 475-486
  
• Amin Coja-Oghlan, Anusch Taraz:
  Colouring Random Graphs in Expected Polynomial Time. 487-498
  
• Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse:
  An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation. 499-510
  
• Amin Coja-Oghlan:
  Finding Large Independent Sets in Polynomial Expected Time. 511-522
  
• Peter Damaschke:
  Distributed Soft Path Coloring. 523-534
  
• Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara:
  Competing Provers Yield Improved Karp-Lipton Collapse Results. 535-546
  
• Harry Buhrman, Richard Chang, Lance Fortnow:
  One Bit of Advice. 547-558
  
• Marcus Schaefer, Frank Stephan:
  Strong Reductions and Immunity for Exponential Time. 559-570
  
• Pierre McKenzie, Klaus W. Wagner:
  The Complexity of Membership Problems for Circuits over Sets of Natural Numbers. 571-582
  
• Wil Michiels, Jan H. M. Korst, Emile H. L. Aarts, Jan van Leeuwen:
  Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem. 583-595
  
• Malik Magdon-Ismail, Costas Busch, Mukkai S. Krishnamoorthy:
  Cake-Cutting Is Not a Piece of Cake. 596-607
  
• Kunal Talwar:
  The Price of Truth: Frugality in Truthful Mechanisms. 608-619
  
• Patricia Bouyer:
  Untameable Timed Automata! 620-631
  
• Nicolas Ollinger:
  The Intrinsic Universality Problem of One-Dimensional Cellular Automata. 632-641
  
• Julien Cervelle, Enrico Formenti:
  On Sand Automata. 642-653
  
• Amr Elmasry, Michael L. Fredman:
  Adaptive Sorting and the Information Theoretic Lower Bound. 654-662
  
• Henrik Björklund, Sven Sandberg, Sergei G. Vorobyov:
  A Discrete Subexponential Algorithm for Parity Games. 663-674
  
• Michael Backes, Christian Jacobi:
  Cryptographically Sound and Machine-Assisted Verification of Security Protocols. 675-686
  
• Véronique Bruyère, Emmanuel Dall'Olio, Jean-François Raskin:
  Durations, Parametric Model-Checking in Timed Automata with Presburger Arithmetic. 687-698