16. STACS 1999: Trier, Germany

Invited talks

• Noam Nisan:
  Algorithms for Selfish Agents. 1-15
  
• Patrice Ossona de Mendez:
  The Reduced Genus of a Multigraph. 16-31
  
• Thomas Wilke:
  Classifying Discrete Temporal Properties. 32-46
  

Complexity 1

• Anna Bernasconi, Igor Shparlinski:
  Circuit Complexity of Testing Square-Free Numbers. 47-56
  
• Martin Sauerhoff, Ingo Wegener, Ralph Werchner:
  Relating Branching Program Size and Formula Size over the Full Binary Basis. 57-67
  

Theory of Parallel Algorithms 1

• Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, José D. P. Rolim:
  Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines. 68-77
  
• Andreas Jakoby:
  The Average Time Complexity to Compute Prefix Functions in Processor Networks. 78-89
  

Complexity 2

• Jin-yi Cai, Aduri Pavan, D. Sivakumar:
  On the Hardness of Permanent. 90-99
  
• Harry Buhrman, Lance Fortnow:
  One-sided Versus Two-sided Error in Probabilistic Computation. 100-109
  

Computational Geometry

• Christian Icking, Rolf Klein, Elmar Langetepe:
  An Optimal Competitive Strategy for Walking in Streets. 110-120
  
• Sven Schuierer, Ines Semrau:
  An Optimal Strategy for Searching in Unknown Streets. 121-131
  
• Mikael Hammar, Bengt J. Nilsson, Sven Schuierer:
  Parallel Searching on m Rays. 132-142
  

Complexity 3

• Clemens Lautemann, Nicole Schweikardt, Thomas Schwentick:
  A Logical Characterisation of Linear Time on Nondeterministic Turing Machines. 143-152
  
• Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin:
  Descriptive Complexity of Computable Sequences. 153-162
  
• Clifford Bergman, Giora Slutzki:
  Complexity of Some Problems in Universal Algebra. 163-172
  

Algorithms and Data Structures 1

• Ton Kloks, Jan Kratochvíl, Haiko Müller:
  New Branchwidth Territories. 173-183
  
• Ming-Yang Kao, Andrzej Lingas, Anna Östlin:
  Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions. 184-196
  
• Vincent Bouchitté, Ioan Todinca:
  Treewidth and Minimum Fill-in of Weakly Triangulated Graphs. 197-206
  

Automata and Formal Languages

• Vesa Halava, Mika Hirvensalo, Ronald de Wolf:
  Decidability and Undecidability of Marked PCP. 207-216
  
• John Michael Robson, Volker Diekert:
  On Quadratic Word Equations. 217-226
  
• Daniel Kirsten:
  Some Undecidability Results Related to the Star Problem in Trace Monoids. 227-236
  

Algorithms and Data Structures 2

• Gunnar Andersson:
  An Approximation Algorithm for Max p-Section. 237-247
  
• Dieter Kratsch, Lorna Stewart:
  Approximating Bandwidth by Mixing Layouts of Interval Graphs. 248-258
  
• Robert Preis:
  Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs. 259-269
  

Complexity 4

• Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel:
  Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries. 269-280
  
• Vikraman Arvind, Jacobo Torán:
  Sparse Sets, Approximable Sets, and Parallel Queries to NP. 281-290
  

Algorithms and Data Structures 3

• Jop F. Sibeyn:
  External Selection. 291-301
  
• Timm Ahrendt:
  Fast Computations of the Exponential Function. 302-312
  

Verification

• Maciej Koutny, Giuseppe Pappalardo:
  A Model of Behaviour Abstraction for Communicating Processes. 313-322
  
• Ahmed Bouajjani, Richard Mayr:
  Model Checking Lossy Vector Addition Systems. 323-333
  

Algorithms and Data Structures 4

• Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang:
  Constructing Light Spanning Trees with Small Routing Cost. 334-344
  
• Matti Nykänen, Esko Ukkonen:
  Finding Paths with the Right Cost. 345-355
  

Complexity 5

• Mario Szegedy:
  In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? 356-361
  
• Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen:
  Lower Bounds for Dynamic Algebraic Problems. 362-372
  
• Lars Engebretsen:
  An Explicit Lower Bound for TSP with Distances One and Two. 373-382
  

Theory of Parallel Algorithms 2

• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Scheduling Dynamic Graphs. 383-392
  
• William Aiello, Costas Busch, Maurice Herlihy, Marios Mavronicolas, Nir Shavit, Dan Touitou:
  Supporting Increment and Decrement Operations in Balancing Networks. 393-403
  
• Elias Koutsoupias, Christos H. Papadimitriou:
  Worst-case Equilibria. 404-413
  

Algorithmic Learning

• Rüdiger Reischuk, Thomas Zeugmann:
  A Complete and Tight Average-Case Analysis of Learning Monomials. 414-423
  
• John Case, Keh-Jiann Chen, Sanjay Jain:
  Costs of General Purpose Learning. 424-433
  
• Rainer Schuler:
  Universal Distributions and Time-Bounded Kolmogorov Complexity. 434-443
  

Logic in Computer Science

• Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer:
  The Descriptive Complexity Approach to LOGCFL. 444-454
  
• Orna Kupferman, Moshe Y. Vardi:
  The Weakness of Self-Complementation. 455-466
  
• Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino:
  On the Difference of Horn Theories. 467-477
  

Complexity 6

• Mark Ettinger, Peter Høyer:
  On Quantum Algorithms for Noncommutative Hidden Subgroups. 478-487
  
• Martin Sauerhoff:
  On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions. 488-499
  
• Giovanni Di Crescenzo, Niels Ferguson, Russell Impagliazzo, Markus Jakobsson:
  How to Forget a Secret. 500-509
  

Logic in Computer Science 2

• Markus Müller-Olm:
  A Modal Fixpoint Logic with Chop. 510-520
  
• Rana Barua, Suman Roy, Zhou Chaochen:
  Completeness of Neighbourhood Logic. 521-530
  
• Martin Otto:
  Eliminating Recursion in the µ-Calculus. 531-540
  

Complexity 7

• Jochen Meßner:
  On Optimal Algorithms and Optimal Proof Systems. 541-550
  
• Juan Luis Esteban, Jacobo Torán:
  Space Bounds for Resolution. 551-560
  

Algorithms and Data Structures 5

• Rolf Niedermeier, Peter Rossmanith:
  Upper Bounds for Vertex Cover Further Improved. 561-570
  
• Marco Riedel:
  Online Matching for Scheduling Problems. 571-580