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
 
Branchwidth
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