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

Invited Papers.- Logic as a Query Language: From Frege to XML.- How Does Computer Science Change Molecular Biology?.- Contributed Papers.- Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer.- Rectangle Visibility Graphs: Characterization, Construction, and Compaction.- Approximating Geometric Bottleneck Shortest Paths.- Optimization in Arrangements.- Complete Classifications for the Communication Complexity of Regular Languages.- The Commutation with Codes and Ternary Sets of Words.- On the Confluence of Linear Shallow Term Rewrite Systems.- Wadge Degrees of ?-Languages of Deterministic Turing Machines.- Faster Deterministic Broadcasting in Ad Hoc Radio Networks.- Private Computations in Networks: Topology versus Randomness.- On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements.- Lattice Reduction by Random Sampling and Birthday Methods.- On the Ultimate Complexity of Factorials.- On the Effective Jordan Decomposability.- Fast Algorithms for Extended Regular Expression Matching and Searching.- Algorithms for Transposition Invariant String Matching (Extended Abstract).- On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets.- Some Results on Derandomization.- On the Representation of Boolean Predicates of the Diffie-Hellman Function.- Quantum Circuits with Unbounded Fan-out.- Analysis of the Harmonic Algorithm for Three Servers.- Non-clairvoyant Scheduling for Minimizing Mean Slowdown.- Space Efficient Hash Tables with Worst Case Constant Access Time.- Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure.- Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs.- Randomness versus Nondeterminism for Read-Once and Read-k BranchingPrograms.- Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids.- Algebraic Characterizations of Small Classes of Boolean Functions.- On the Difficulty of Some Shortest Path Problems.- Representing Graph Metrics with Fewest Edges.- Computing Shortest Paths with Uncertainty.- Solving Order Constraints in Logarithmic Space.- The Inversion Problem for Computable Linear Operators.- Algebras of Minimal Rank over Arbitrary Fields.- Evolutionary Algorithms and the Maximum Matching Problem.- Alternative Algorithms for Counting All Matchings in Graphs.- Strong Stability in the Hospitals/Residents Problem.- The Inference Problem for Propositional Circumscription of Afine Formulas Is coNP-Complete.- Decidable Theories of Cayley-Graphs.- The Complexity of Resolution with Generalized Symmetry Rules.- Colouring Random Graphs in Expected Polynomial Time.- An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation.- Finding Large Independent Sets in Polynomial Expected Time.- Distributed Soft Path Coloring.- Competing Provers Yield Improved Karp-Lipton Collapse Results.- One Bit of Advice.- Strong Reductions and Immunity for Exponential Time.- The Complexity of Membership Problems for Circuits over Sets of Natural Numbers.- Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem.- Cake-Cutting Is Not a Piece of Cake.- The Price of Truth: Frugality in Truthful Mechanisms.- Untameable Timed Automata!.- The Intrinsic Universality Problem of One-Dimensional Cellular Automata.- On Sand Automata.- Adaptive Sorting and the Information Theoretic Lower Bound.- A Discrete Subexponential Algorithm for Parity Games.- Cryptographically Sound and Machine-Assisted Verification of Security Protocols.- Durations, Parametric Model-Checking in Timed Automata with Presburger Arithmetic.