Invited Lectures.- Polarized Process Algebra and Program Equivalence.- Problems on RNA Secondary Structure Prediction and Design.- Some Issues Regarding Search, Censorship, and Anonymity in Peer to Peer Networks.- The SPQR-Tree Data Structure in Graph Drawing.- Model Checking and Testing Combined.- Logic and Automata: A Match Made in Heaven.- Algorithms.- Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes.- Generalized Framework for Selectors with Applications in Optimal Group Testing.- Decoding of Interleaved Reed Solomon Codes over Noisy Data.- Process Algebra.- On the Axiomatizability of Ready Traces, Ready Simulation, and Failure Traces.- Resource Access and Mobility Control with Dynamic Privileges Acquisition.- Replication vs. Recursive Definitions in Channel Based Calculi.- Approximation Algorithms.- Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem.- An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality.- An Improved Approximation Algorithm for Vertex Cover with Hard Capacities.- Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem.- Approximating Steiner k-Cuts.- MAX k-CUT and Approximating the Chromatic Number of Random Graphs.- Approximation Algorithm for Directed Telephone Multicast Problem.- Languages and Programming.- Mixin Modules and Computational Effects.- Decision Problems for Language Equations with Boolean Operations.- Generalized Rewrite Theories.- Complexity.- Sophistication Revisited.- Scaled Dimension and Nonuniform Complexity.- Quantum Search on Bounded-Error Inputs.- A Direct Sum Theorem in Communication Complexity via Message Compression.- Data Structures.- Optimal Cache-Oblivious Implicit Dictionaries.- TheCell Probe Complexity of Succinct Data Structures.- Succinct Representations of Permutations.- Succinct Dynamic Dictionaries and Trees.- Graph Algorithms.- Labeling Schemes for Weighted Dynamic Trees.- A Simple Linear Time Algorithm for Computing a (2k - 1)-Spanner of O(n 1+1/k ) Size in Weighted Graphs.- Multicommodity Flows over Time: Efficient Algorithms and Complexity.- Multicommodity Demand Flow in a Tree.- Automata.- Skew and Infinitary Formal Power Series.- Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser's Separation.- Residual Languages and Probabilistic Automata.- A Testing Scenario for Probabilistic Automata.- The Equivalence Problem for t-Turn DPDA Is Co-NP.- Flip-Pushdown Automata: k + 1 Pushdown Reversals Are Better than k.- Optimization and Games.- Convergence Time to Nash Equilibria.- Nashification and the Coordination Ratio for a Selfish Routing Game.- Stable Marriages with Multiple Partners: Efficient Search for an Optimal Solution.- An Intersection Inequality for Discrete Distributions and Related Generation Problems.- Graphs and Bisimulation.- Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games.- Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes.- Bisimulation Proof Methods for Mobile Ambients.- On Equivalent Representations of Infinite Structures.- Online Problems.- Adaptive Raising Strategies Optimizing Relative Efficiency.- A Competitive Algorithm for the General 2-Server Problem.- On the Competitive Ratio for Online Facility Location.- A Study of Integrated Document and Connection Caching.- Verification.- A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems.- Monadic Second-Order Logics withCardinalities.- ? 2 ? ? 2 ? AFMC.- Upper Bounds for a Theory of Queues.- Around the Internet.- Degree Distribution of the FKP Network Model.- Similarity Matrices for Pairs of Graphs.- Algorithmic Aspects of Bandwidth Trading.- Temporal Logic and Model Checking.- CTL+ Is Complete for Double Exponential Time.- Hierarchical and Recursive State Machines with Context-Dependent Properties.- Oracle Circuits fo
Inhaltsverzeichnis
Invited Lectures. - Polarized Process Algebra and Program Equivalence. - Problems on RNA Secondary Structure Prediction and Design. - Some Issues Regarding Search, Censorship, and Anonymity in Peer to Peer Networks. - The SPQR-Tree Data Structure in Graph Drawing. - Model Checking and Testing Combined. - Logic and Automata: A Match Made in Heaven. - Algorithms. - Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes. - Generalized Framework for Selectors with Applications in Optimal Group Testing. - Decoding of Interleaved Reed Solomon Codes over Noisy Data. - Process Algebra. - On the Axiomatizability of Ready Traces, Ready Simulation, and Failure Traces. - Resource Access and Mobility Control with Dynamic Privileges Acquisition. - Replication vs. Recursive Definitions in Channel Based Calculi. - Approximation Algorithms. - Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem. - An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality. - An Improved Approximation Algorithm for Vertex Cover with Hard Capacities. - Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem. - Approximating Steiner k-Cuts. - MAX k-CUT and Approximating the Chromatic Number of Random Graphs. - Approximation Algorithm for Directed Telephone Multicast Problem. - Languages and Programming. - Mixin Modules and Computational Effects. - Decision Problems for Language Equations with Boolean Operations. - Generalized Rewrite Theories. - Complexity. - Sophistication Revisited. - Scaled Dimension and Nonuniform Complexity. - Quantum Search on Bounded-Error Inputs. - A Direct Sum Theorem in Communication Complexity via Message Compression. - Data Structures. - Optimal Cache-Oblivious Implicit Dictionaries. - TheCell Probe Complexity of Succinct Data Structures. - Succinct Representations of Permutations. - Succinct Dynamic Dictionaries and Trees. - Graph Algorithms. - Labeling Schemes for Weighted Dynamic Trees. - A Simple Linear Time Algorithm for Computing a (2k 1)-Spanner of O(n 1+1/k ) Size in Weighted Graphs. - Multicommodity Flows over Time: Efficient Algorithms and Complexity. - Multicommodity Demand Flow in a Tree. - Automata. - Skew and Infinitary Formal Power Series. - Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser s Separation. - Residual Languages and Probabilistic Automata. - A Testing Scenario for Probabilistic Automata. - The Equivalence Problem for t-Turn DPDA Is Co-NP. - Flip-Pushdown Automata: k + 1 Pushdown Reversals Are Better than k. - Optimization and Games. - Convergence Time to Nash Equilibria. - Nashification and the Coordination Ratio for a Selfish Routing Game. - Stable Marriages with Multiple Partners: Efficient Search for an Optimal Solution. - An Intersection Inequality for Discrete Distributions and Related Generation Problems. - Graphs and Bisimulation. - Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games. - Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes. - Bisimulation Proof Methods for Mobile Ambients. - On Equivalent Representations of Infinite Structures. - Online Problems. - Adaptive Raising Strategies Optimizing Relative Efficiency. - A Competitive Algorithm for the General 2-Server Problem. - On the Competitive Ratio for Online Facility Location. - A Study of Integrated Document and Connection Caching. - Verification. - A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems. - Monadic Second-Order Logics withCardinalities. - ? 2 ? ? 2 ? AFMC. - Upper Bounds for a Theory of Queues. - Around the Internet. - Degree Distribution of the FKP Network Model. - Similarity Matrices for Pairs of Graphs. - Algorithmic Aspects of Bandwidth Trading. - Temporal Logic and Model Checking. - CTL+ Is Complete for Double Exponential Time. - Hierarchical and Recursive State Machines with Context-Dependent Properties. - Oracle Circuits for Branching-Time Model Checking. - Graph Problems. - There Are Spanning Spiders in Dense Graphs (and We Know How to Find Them). - The Computational Complexity of the Role Assignment Problem. - Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs. - Genus Characterizes the Complexity of Graph Problems: Some Tight Results. - Logic and Lambda-Calculus. - The Definition of a Temporal Clock Operator. - Minimal Classical Logic and Control Operators. - Counterexample-Guided Control. - Axiomatic Criteria for Quotients and Subobjects for Higher-Order Data Types. - Data Structures and Algorithms. - Efficient Pebbling for List Traversal Synopses. - Function Matching: Algorithms, Applications, and a Lower Bound. - Simple Linear Work Suffix Array Construction. - Types and Categories. - Expansion Postponement via Cut Elimination in Sequent Calculi for Pure Type Systems. - Secrecy in Untrusted Networks. - Locally Commutative Categories. - Probabilistic Systems. - Semi-pullbacks and Bisimulations in Categories of Stochastic Relations. - Quantitative Analysis of Probabilistic Lossy Channel Systems. - Discounting the Future in Systems Theory. - Information Flow in Concurrent Games. - Sampling and Randomness. - Impact of Local Topological Information on Random Walks on Finite Graphs. - Analysis of a Simple Evolutionary Algorithm for Minimization in Euclidean Spaces. - OptimalCoding and Sampling of Triangulations. - Generating Labeled Planar Graphs Uniformly at Random. - Scheduling. - Online Load Balancing Made Simple: Greedy Strikes Back. - Real-Time Scheduling with a Budget. - Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling. - Anycasting in Adversarial Systems: Routing and Admission Control. - Geometric Problems. - Dynamic Algorithms for Approximating Interdistances. - Solving the Robots Gathering Problem.
