STACS 2003: 20th Annual Symposium on Theoretical Aspects of Computer Science Berlin, Germany, February 27 – March 1, 2003 Proceedings

Logic as a Query Language: From Frege to XML....Pages 1-12
How Does Computer Science Change Molecular Biology?....Pages 13-13
Improved Compact Visibility Representation of Planar Graph via Schnyder’s Realizer....Pages 14-25
Rectangle Visibility Graphs: Characterization, Construction, and Compaction....Pages 26-37
Approximating Geometric Bottleneck Shortest Paths....Pages 38-49
Optimization in Arrangements....Pages 50-61
Complete Classifications for the Communication Complexity of Regular Languages....Pages 62-73
The Commutation with Codes and Ternary Sets of Words....Pages 74-84
On the Confluence of Linear Shallow Term Rewrite Systems....Pages 85-96
Wadge Degrees of ω-Languages of Deterministic Turing Machines....Pages 97-108
Faster Deterministic Broadcasting in Ad Hoc Radio Networks....Pages 109-120
Private Computations in Networks: Topology versus Randomness....Pages 121-132
On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements....Pages 133-144
Lattice Reduction by Random Sampling and Birthday Methods....Pages 145-156
On the Ultimate Complexity of Factorials....Pages 157-166
On the Effective Jordan Decomposability....Pages 167-178
Fast Algorithms for Extended Regular Expression Matching and Searching....Pages 179-190
Algorithms for Transposition Invariant String Matching (Extended Abstract)....Pages 191-202
On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets....Pages 203-211
Some Results on Derandomization....Pages 212-222
On the Representation of Boolean Predicates of the Diffie-Hellman Function....Pages 223-233
Quantum Circuits with Unbounded Fan-out....Pages 234-246
Analysis of the Harmonic Algorithm for Three Servers....Pages 247-259
Non-clairvoyant Scheduling for Minimizing Mean Slowdown....Pages 260-270
Space Efficient Hash Tables with Worst Case Constant Access Time....Pages 271-282
Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure....Pages 283-294
Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs....Pages 295-306
Randomness versus Nondeterminism for Read-Once and Read-k Branching Programs....Pages 307-318
Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids....Pages 319-330
Algebraic Characterizations of Small Classes of Boolean Functions....Pages 331-342
On the Difficulty of Some Shortest Path Problems....Pages 343-354
Representing Graph Metrics with Fewest Edges....Pages 355-366
Computing Shortest Paths with Uncertainty....Pages 367-378
Solving Order Constraints in Logarithmic Space....Pages 379-390
The Inversion Problem for Computable Linear Operators....Pages 391-402
Algebras of Minimal Rank over Arbitrary Fields....Pages 403-414
Evolutionary Algorithms and the Maximum Matching Problem....Pages 415-426
Alternative Algorithms for Counting All Matchings in Graphs....Pages 427-438
Strong Stability in the Hospitals/Residents Problem....Pages 439-450
The Inference Problem for Propositional Circumscription of Afine Formulas Is coNP-Complete....Pages 451-462
Decidable Theories of Cayley-Graphs....Pages 463-474
The Complexity of Resolution with Generalized Symmetry Rules....Pages 475-486
Colouring Random Graphs in Expected Polynomial Time....Pages 487-498
An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation....Pages 499-510
Finding Large Independent Sets in Polynomial Expected Time....Pages 511-522
Distributed Soft Path Coloring....Pages 523-534
Competing Provers Yield Improved Karp-Lipton Collapse Results....Pages 535-546
One Bit of Advice....Pages 547-558
Strong Reductions and Immunity for Exponential Time....Pages 559-570
The Complexity of Membership Problems for Circuits over Sets of Natural Numbers....Pages 571-582
Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem....Pages 583-595
Cake-Cutting Is Not a Piece of Cake....Pages 596-607
The Price of Truth: Frugality in Truthful Mechanisms....Pages 608-619
Untameable Timed Automata!....Pages 620-631
The Intrinsic Universality Problem of One-Dimensional Cellular Automata....Pages 632-641
On Sand Automata....Pages 642-653
Adaptive Sorting and the Information Theoretic Lower Bound....Pages 654-662
A Discrete Subexponential Algorithm for Parity Games....Pages 663-674
Cryptographically Sound and Machine-Assisted Verification of Security Protocols....Pages 675-686
Durations, Parametric Model-Checking in Timed Automata with Presburger Arithmetic....Pages 687-698