内容

目次

Invited Talks.- Self-Adjusting Computation.- The Past, Present, and Future of Web Search Engines.- What Do Program Logics and Type Systems Have in Common?.- Feasible Proofs and Computations: Partnership and Fusion.- Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input.- Testing, Optimizaton, and Games.- Contributed Papers.- Deciding Knowledge in Security Protocols Under Equational Theories.- Representing Nested Inductive Types Using W-Types.- Algorithms for Multi-product Pricing.- Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas.- Linear and Branching Metrics for Quantitative Transition Systems.- Learning a Hidden Subgraph.- Optimal Reachability for Weighted Timed Games.- Wavelength Assignment in Optical Networks with Fixed Fiber Capacity.- External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs.- A ?-Calculus for Resource Separation.- The Power of Verification for One-Parameter Agents.- Group Spreading: A Protocol for Provably Secure Distributed Name Service.- Further Improvements in Competitive Guarantees for QoS Buffering.- Competition-Induced Preferential Attachment.- Approximating Longest Directed Paths and Cycles.- Definitions and Bounds for Self-Healing Key Distribution Schemes.- Tree-Walking Automata Cannot Be Determinized.- Projecting Games on Hypercoherences.- An Analog Characterization of Elementarily Computable Functions over the Real Numbers.- Model Checking with Multi-valued Logics.- The Complexity of Partition Functions.- Comparing Recursion, Replication, and Iteration in Process Calculi.- Dynamic Price Sequence and Incentive Compatibility.- The Complexity of Equivariant Unification.- Coordination Mechanisms.- Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help.- Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities.- Coloring Semirandom Graphs Optimally.- Sublinear-Time Approximation for Clustering Via Random Sampling.- Solving Two-Variable Word Equations.- Backtracking Games and Inflationary Fixed Points.- A PTAS for Embedding Hypergraph in a Cycle.- Towards an Algebraic Theory of Typed Mobile Processes.- Ecological Turing Machines.- Locally Consistent Constraint Satisfaction Problems.- Quantum Query Complexity of Some Graph Problems.- A Domain Theoretic Account of Picard’s Theorem.- Interactive Observability in Ludics.- Easily Refutable Subformulas of Large Random 3CNF Formulas.- On Graph Problems in a Semi-streaming Model.- Linear Tolls Suffice: New Bounds and Algorithms for Tolls in Single Source Networks.- Bounded Fixed-Parameter Tractability and log2 n Nondeterministic Bits.- Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In.- Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up.- Selfish Unsplittable Flows.- A General Technique for Managing Strings in Comparison-Driven Data Structures.- Greedy Regular Expression Matching.- A Time Algorithm for d-Dimensional Protein Folding in the HP-Model.- Nash Equilibria in Discrete Routing Games with Convex Latency Functions.- Improved Results for Data Migration and Open Shop Scheduling.- Deterministic M2M Multicast in Radio Networks.- Syntactic Control of Concurrency.- Linear-Time List Decoding in Error-Free Settings.- A Categorical Model for the Geometry of Interaction.- Testing Monotonicity over Graph Products.- The Minimum-Entropy Set Cover Problem.- Communication Versus Computation.- Optimal Website Design with the Constrained Subtree Selection Problem.- Simple Permutations Mix Well.- Closest Pair Problems in Very High Dimensions.- Universality in Quantum Computation.- Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design.- Fairness to All While Downsizing.- A Generalisation of Pre-logical Predicates to Simply Typed Formal Systems.- A Faster Algorithm for Minimum Cycle Basis of Graphs.- The Black-Box Complexity of Nearest Neighbor Search.- Regular Solutions of Language Inequalities and Well Quasi-orders.- A Calculus of Coroutines.- Almost Optimal Decentralized Routing in Long-Range Contact Networks.- Word Problems on Compressed Words.- Complexity of Pseudoknot Prediction in Simple Models.- Property Testing of Regular Tree Languages.- Entropy as a Fixed Point.- Transparent Long Proofs: A First PCP Theorem for .- A Time Lower Bound for Satisfiability.- Some Results on Effective Randomness.- A Polynomial Quantum Query Lower Bound for the Set Equality Problem.- Succinct Representations of Functions.- A Note on Karr’s Algorithm.- The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs.- Efficient Consistency Proofs for Generalized Queries on a Committed Database.- A -Approximation Algorithm for Rectangle Tiling.- Extensional Theories and Rewriting.- Hardness of String Similarity Search and Other Indexing Problems.- A Syntactic Characterization of Distributive LTL Queries.- Online Scheduling with Bounded Migration.- On the Expressive Power of Monadic Least Fixed Point Logic.- Counting in Trees for Free.- Games with Winning Conditions of High Borel Complexity.- Propositional PSPACE Reasoning with Boolean Programs Versus Quantified Boolean Formulas.- LA, Permutations, and the Hajós Calculus.- A Calibration of Ineffective Theorems of Analysis in a Hierarchy of Semi-classical Logical Principles.- Efficiently Computing Succinct Trade-Off Curves.- On Randomization Versus Synchronization in Distributed Systems.- A New Algorithm for Optimal Constraint Satisfaction and Its Implications.- On the Power of Ambainis’s Lower Bounds.