16. STACS 1999: Trier, Germany

Christoph Meinel, Sophie Tison (Eds.): STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings. Lecture Notes in Computer Science 1563 Springer 1999 BibTeX

@proceedings{DBLP:conf/stacs/1999,
  editor    = {Christoph Meinel and
               Sophie Tison},
  title     = {STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer
               Science, Trier, Germany, March 4-6, 1999, Proceedings},
  booktitle = {STACS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1563},
  year      = {1999},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited talks

Noam Nisan:
Algorithms for Selfish Agents. 1-15
Electronic Edition (Springer LINK) BibTeX
Patrice Ossona de Mendez:
The Reduced Genus of a Multigraph. 16-31
Electronic Edition (Springer LINK) BibTeX
Thomas Wilke:
Classifying Discrete Temporal Properties. 32-46
Electronic Edition (Springer LINK) BibTeX

Complexity 1

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

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
Electronic Edition (Springer LINK) BibTeX
Andreas Jakoby:
The Average Time Complexity to Compute Prefix Functions in Processor Networks. 78-89
Electronic Edition (Springer LINK) BibTeX

Complexity 2

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

Computational Geometry

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

Complexity 3

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

Algorithms and Data Structures 1

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

Automata and Formal Languages

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

Algorithms and Data Structures 2

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

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
Electronic Edition (Springer LINK) BibTeX
Vikraman Arvind, Jacobo Torán:
Sparse Sets, Approximable Sets, and Parallel Queries to NP. 281-290
Electronic Edition (Springer LINK) BibTeX

Algorithms and Data Structures 3

Jop F. Sibeyn:
External Selection. 291-301
Electronic Edition (Springer LINK) BibTeX
Timm Ahrendt:
Fast Computations of the Exponential Function. 302-312
Electronic Edition (Springer LINK) BibTeX

Verification

Maciej Koutny, Giuseppe Pappalardo:
A Model of Behaviour Abstraction for Communicating Processes. 313-322
Electronic Edition (Springer LINK) BibTeX
Ahmed Bouajjani, Richard Mayr:
Model Checking Lossy Vector Addition Systems. 323-333
Electronic Edition (Springer LINK) BibTeX

Algorithms and Data Structures 4

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

Complexity 5

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

Theory of Parallel Algorithms 2

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

Algorithmic Learning

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

Logic in Computer Science

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

Complexity 6

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

Logic in Computer Science 2

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

Complexity 7

Jochen Meßner:
On Optimal Algorithms and Optimal Proof Systems. 541-550
Electronic Edition (Springer LINK) BibTeX
Juan Luis Esteban, Jacobo Torán:
Space Bounds for Resolution. 551-560
Electronic Edition (Springer LINK) BibTeX

Algorithms and Data Structures 5

Rolf Niedermeier, Peter Rossmanith:
Upper Bounds for Vertex Cover Further Improved. 561-570
Electronic Edition (Springer LINK) BibTeX
Marco Riedel:
Online Matching for Scheduling Problems. 571-580
Electronic Edition (Springer LINK) BibTeX