STACS 99: 16th Annual Symposium on Theoretical Aspects of Computer Science Trier, Germany, March 4–6, 1999 Proceedings

Algorithms for Selfish Agents....Pages 1-15
The Reduced Genus of a Multigraph....Pages 16-31
Classifying Discrete Temporal Properties....Pages 32-46
Circuit Complexity of Testing Square-Free Numbers....Pages 47-56
Relating Branching Program Size and Formula Size over the Full Binary Basis....Pages 57-67
Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines....Pages 68-77
The Average Time Complexity to Compute Prefix Functions in Processor Networks....Pages 78-89
On the Hardness of Permanent....Pages 90-99
One-Sided Versus Two-Sided Error in Probabilistic Computation....Pages 100-109
An Optimal Competitive Strategy for Walking in Streets....Pages 110-120
An Optimal Strategy for Searching in Unknown Streets....Pages 121-131
Parallel Searching on m Rays....Pages 132-142
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines....Pages 143-152
Descriptive Complexity of Computable Sequences....Pages 153-162
Complexity of Some Problems in Universal Algebra....Pages 163-172
New Branchwidth Territories....Pages 173-183
Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions....Pages 184-196
Treewidth and Minimum Fill-In of Weakly Triangulated Graphs....Pages 197-206
Decidability and Undecidability of Marked PCP....Pages 207-216
On Quadratic Word Equations....Pages 217-226
Some Undecidability Results Related to the Star Problem in Trace Monoids....Pages 227-236
An Approximation Algorithm for Max p -Section....Pages 237-247
Approximating Bandwidth by Mixing Layouts of Interval Graphs....Pages 248-258
Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs....Pages 259-269
Extending Downward Collapse from 1-versus-2 Queries to j -versus- j + 1 Queries....Pages 270-280
Sparse Sets, Approximable Sets, and Parallel Queries to NP....Pages 281-290
External Selection....Pages 291-301
Fast Computations of the Exponential Function....Pages 302-312
A Model of Behaviour Abstraction for Communicating Processes....Pages 313-322
Model Checking Lossy Vector Addition Systems....Pages 323-333
Constructing Light Spanning Trees with Small Routing Cost....Pages 334-344
Finding Paths with the Right Cost....Pages 345-355
In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?....Pages 356-361
Lower Bounds for Dynamic Algebraic Problems....Pages 362-372
An Explicit Lower Bound for TSP with Distances One and Two....Pages 373-382
Scheduling Dynamic Graphs....Pages 383-392
Supporting Increment and Decrement Operations in Balancing Networks....Pages 393-403
Worst-Case Equilibria....Pages 404-413
A Complete and Tight Average-Case Analysis of Learning Monomials....Pages 414-423
Costs of General Purpose Learning....Pages 424-433
Universal Distributions and Time-Bounded Kolmogorov Complexity....Pages 434-443
The Descriptive Complexity Approach to LOGCFL....Pages 444-454
The Weakness of Self-Complementation....Pages 455-466
On the Difference of Horn Theories....Pages 467-477
On Quantum Algorithms for Noncommutative Hidden Subgroups....Pages 478-487
On the Size of Randomized OBDDs and Read-Once Branching Programs for k -Stable Functions....Pages 488-499
How To Forget a Secret....Pages 500-509
A Modal Fixpoint Logic with Chop....Pages 510-520
Completeness of Neighbourhood Logic....Pages 521-530
Eliminating Recursion in the μ-Calculus....Pages 531-540
On Optimal Algorithms and Optimal Proof Systems....Pages 541-550
Space Bounds for Resolution....Pages 551-560
Upper Bounds for Vertex Cover Further Improved....Pages 561-570
Online Matching for Scheduling Problems....Pages 571-580