Mathematical Foundations of Computer Science 2003

Invited Talks.- Distributed Quantum Computing.- Selfish Routing in Non-cooperative Networks: A Survey.- Process Algebraic Frameworks for the Specification and Analysis of Cryptographic Protocols.- Semantic and Syntactic Approaches to Simulation Relations.- On the Computational Complexity of Conservative Computing.- Constructing Infinite Graphs with a Decidable MSO-Theory.- Towards a Theory of Randomized Search Heuristics.- Contributed Papers.- Adversarial Models for Priority-Based Networks.- On Optimal Merging Networks.- Problems which Cannot Be Reduced to Any Proper Subproblems.- ACID-Unification Is NEXPTIME-Decidable.- Completeness in Differential Approximation Classes.- On the Length of the Minimum Solution of Word Equations in One Variable.- Smoothed Analysis of Three Combinatorial Problems.- Inferring Strings from Graphs and Arrays.- Faster Algorithms for k-Medians in Trees.- Periodicity and Transitivity for Cellular Automata in Besicovitch Topologies.- Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms.- Error-Bounded Probabilistic Computations between MA and AM.- A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves.- Symbolic Analysis of Crypto-Protocols Based on Modular Exponentiation.- Denotational Testing Semantics in Coinductive Form.- Lower Bounds for General Graph-Driven Read-Once Parity Branching Programs.- The Minimal Graph Model of Lambda Calculus.- Unambiguous Automata on Bi-infinite Words.- Relating Hierarchy of Temporal Properties to Model Checking.- Arithmetic Constant-Depth Circuit Complexity Classes.- Inverse NP Problems.- A Linear-Time Algorithm for 7-Coloring 1-Planar Graphs.- Generalized Satisfiability with Limited Occurrences per Variable: A Study through Delta-Matroid Parity.- Randomized Algorithms for Determining the Majority on Graphs.- Using Transitive-Closure Logic for Deciding Linear Properties of Monoids.- Linear-Time Computation of Local Periods.- Two Dimensional Packing: The