STACS '99 List of Accepted Papers

146 submissions, 51 accepted (in alphabetical order of titles):

A Complete and Tight Average-Case Analysis of Learning Monomials
Rüdiger Reischuk, Thomas Zeugmann
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines
Nicole Schweikardt, Clemens Lautemann, Thomas Schwentick
A Modal Fixpoint Logic with Chop
Markus Müller-Olm
A Model of Behaviour Abstraction for Communicating Processes
Maciej Koutny, Guiseppe Pappalardo
An Approximation Algorithm for Max p-Section
Gunnar Andersson
An Explicit Lower Bound for TSP with Distances One and Two
Lars Engebretsen
Joint talk:
An Optimal Competitive Strategy for Walking in Streets
Christian Icking, Rolf Klein, Elmar Langetepe
An Optimal Strategy for Searching in Unknown Streets
Ines Semrau, Sven Schuierer
Approximating Bandwidth by Mixing Layouts of Interval Graphs
Dieter Kratsch, Lorna Stewart
Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions
Ming-Yang Kao, Andrzej Lingas, Anna Ostlin
Ton Kloks, Jan Kratochvil, Haiko Müller
Circuit Complexity of Testing Square-Free Numbers
Igor Shparlinski, Anna Bernasconi
Completeness of Neighbourhood Logic
Suman Roy, Barua Rana, Chaochen Zhou
Complexity of Some Problems in Algebra and Their Relationship to Algebraic Specifications
Clifford Bergman, Giora Slutzki
Constructing Light Spanning Trees with Small Routing Cost
Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang
Costs of General Purpose Learning
John Case, Keh-Jiann Chen, Sanjay Jain
Decidability and Undecidability of Marked PCP
Mika Hirvensalo, Vesa Halava, Ronald de Wolf
Descriptive complexity of computable sequences
Bruno Durand, Alexander Shen, Nikolai Vereshagin
Eliminating recursion in the $\mu$-calculus
Martin Otto
Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
External Selection
Jop F. Sibeyn
Fast Computations of the Exponential Function
Timm Ahrendt
Finding All Distances in Graphs with Integer Weights
Matti Nykänen, Esko Ukkonen
How to forget a secret
Giovanni Di Crescenzo, Niels Ferguson, Russell Impagliazzo, Markus Jakobsson
In How Many Steps the $k$ Peg Version of the Towers of Hanoi Game Can Be Solved?
Mario Szegedy
Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs
Robert Preis
Lower bounds for dynamic algebraic problems
Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen
Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines
A. E. Andreev, A. E. F. Clementi, P. Penna, J. D. P. Rolim
Model Checking Lossy Vector Addition Systems
Richard Mayr, Ahmed Bouajjani
On Optimal Algorithms and Optimal Proof Systems
Jochen Messner
On Quadratic Word Equations
John Michael Robson, Volker Diekert
On Quantum Algorithms for Noncommuntative Hidden Subgroups
Peter Hoyer, Mark Ettinger
On the Difference of Horn Theories
Kazuhisa Makino, Thomas Eiter, Toshihide Ibaraki
On the Hardness of Permanent
Jin Yi Cai, A. Pavan, D. Sivakumar
On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions
Martin Sauerhoff
One-sided Versus Two-sided Error in Probabilistic Computation
Lance Fortnow, Harry Buhrman
Online Matching for Scheduling Problems
Marco Riedel
Parallel Searching on $m$ Rays
Mikael Hammar, Bengt J. Nilsson, Sven Schuierer
Relating Branching Program Size and Formula Size over the Full Binary Basis
M. Sauerhoff, I. Wegener, R. Werchner
Scheduling Dynamic Graphs
Andreas Jakoby, Rüdiger Reischuk, Maciej Liskiewicz
Some Undecidability Results related to the Star Problem in Trace Monoids
Daniel Kirsten
Space Bounds for Resolution
Jacobo Toran, Juan Luis Esteban
Sparse Sets, Approximable Sets, and Parallel Queries to NP
V. Arvind, J. Toran
Supporting Increment and Decrement Operations in Balancing Networks
Costas Busch, William Aiello, Maurice Herlihy, Marios Mavronicolas, Nir Shavit, Dan Touitou
The Average Time Complexity to Prefix Functions in Processor Networks
Andreas Jakoby
The Descriptive Complexity Approach to LOGCFL
Heribert Vollmer, Clemens Lautemann, Pierre McKenzie, Thomas Schwentick
The weakness of Self-Complementation
Orna Kupferman, Moshe Vardi
Treewidth and Minimum Fill-in of Weakly Triangulated Graphs
V. Bouchitté, I. Todinca
Universal distributions and time-bounded Kolmogorov complexity
Rainer Schuler
Upper Bounds for Vertex Cover - Further Improved
Rolf Niedermeier, Peter Rossmanith
Worst-case Equilibria
Elias Koutsoupias, Christos Papadimitriou