Front matter
17-59
Self-Adjusting Computation
Robert Harper
123-134
The Past, Present, and Future of Web Search Engines
Monika Henzinger
75-94
What Do Program Logics and Type Systems Have in Common?
Martin Hofmann
219-234
Feasible Proofs and Computations: Partnership and Fusion
Alexander A. Razborov
15-27
Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input
Wojciech Rytter
401-426
Testing, Optimizaton, and Games
Mihalis Yannakakis
145-160
Deciding Knowledge in Security Protocols Under Equational Theories
Martín Abadi and Véronique Cortier
87-95
Representing Nested Inductive Types Using W-Types
Michael Abbott, Thorsten Altenkirch and Neil Ghani
253-266
Algorithms for Multi-product Pricing
Gagan Aggarwal, Tomás Feder, Rajeev Motwani and An Zhu
131-143
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas
Michael Alekhnovich, Edward A. Hirsch and Dmitry Itsykson
131-154
Linear and Branching Metrics for Quantitative Transition Systems
Luca de Alfaro, Marco Faella and Mariëlle Stoelinga
129-138
Learning a Hidden Subgraph
Noga Alon and Vera Asodi
97-112
Optimal Reachability for Weighted Timed Games
Rajeev Alur, Mikhail Bernadsky and P. Madhusudan
105-120
Wavelength Assignment in Optical Networks with Fixed Fiber Capacity
Matthew Andrews and Lisa Zhang
57-74
External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs
Lars Arge, Ulrich Meyer and Laura Toma
29-40
A λ-Calculus for Resource Separation
Robert Atkey
63-82
The Power of Verification for One-Parameter Agents
Vincenzo Auletta, Roberto De Prisco, Paolo Penna and Giuseppe Persiano
187-210
Group Spreading: A Protocol for Provably Secure Distributed Name Service
Baruch Awerbuch and Christian Scheideler
196-207
Further Improvements in Competitive Guarantees for QoS Buffering
Nikhil Bansal, Lisa K Fleischer, Tracy Kimbrel, Mohammad Mahdian and Baruch Schieber, et al.
208-221
Competition-Induced Preferential Attachment
N. Berger, C. Borgs, J. T. Chayes, R. M. D’Souza and R. D. Kleinberg
101-110
Approximating Longest Directed Paths and Cycles
Andreas Björklund, Thore Husfeldt and Sanjeev Khanna
179-194
Definitions and Bounds for Self-Healing Key Distribution Schemes
Carlo Blundo, Paolo D’Arco and Alfredo De Santis
127-157
Tree-Walking Automata Cannot Be Determinized
Mikołaj Bojańczyk and Thomas Colcombet
133-154
Projecting Games on Hypercoherences
Pierre Boudes
157-166
An Analog Characterization of Elementarily Computable Functions over the Real Numbers
Olivier Bournez and Emmanuel Hainry
245-273
Model Checking with Multi-valued Logics
Glenn Bruns and Patrice Godefroid
294-306
The Complexity of Partition Functions
Andrei Bulatov and Martin Grohe
37-60
Comparing Recursion, Replication, and Iteration in Process Calculi
Nadia Busi, Maurizio Gabbrielli and Gianluigi Zavattaro
27-46
Dynamic Price Sequence and Incentive Compatibility
Ning Chen, Xiaotie Deng, Xiaoming Sun and Andrew Chi-Chih Yao
91-103
The Complexity of Equivariant Unification
James Cheney
45-56
Coordination Mechanisms
George Christodoulou, Elias Koutsoupias and Akash Nanavati
145-156
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help
Marek Chrobak, Wojciech Jawor, Jiří Sgall and Tomáš Tichý
257-287
Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities
Bruno Codenotti and Kasturi Varadarajan
71-100
Coloring Semirandom Graphs Optimally
Amin Coja-Oghlan
41-52
Sublinear-Time Approximation for Clustering Via Random Sampling
Artur Czumaj and Christian Sohler
1-30
Solving Two-Variable Word Equations
Robert Da̧browski and Wojtek Plandowski
145-168
Backtracking Games and Inflationary Fixed Points
Anuj Dawar, Erich Grädel and Stephan Kreutzer
433-444
A PTAS for Embedding Hypergraph in a Cycle
Xiaotie Deng and Guojun Li
445-456
Towards an Algebraic Theory of Typed Mobile Processes
Yuxin Deng and Davide Sangiorgi
1-6
Ecological Turing Machines
Bruno Durand, Andrei Muchnik, Maxim Ushakov and Nikolai Vereshchagin
545-580
Locally Consistent Constraint Satisfaction Problems
Zdeněk Dvořák, Daniel Král’ and Ondřej Pangrác
125-142
Quantum Query Complexity of Some Graph Problems
Christoph Dürr, Mark Heiligman, Peter Høyer and Mehdi Mhalla
75-87
A Domain Theoretic Account of Picard’s Theorem
A. Edalat and D. Pattinson
99-118
Interactive Observability in Ludics
Claudia Faggian
429-478
Easily Refutable Subformulas of Large Random 3CNF Formulas
Uriel Feige and Eran Ofek
17-44
On Graph Problems in a Semi-streaming Model
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri and Jian Zhang
315-363
Linear Tolls Suffice: New Bounds and Algorithms for Tolls in Single Source Networks
Lisa Fleischer
113-128
Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits
Jörg Flum, Martin Grohe and Mark Weyer
69-118
Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In
Fedor V. Fomin, Dieter Kratsch and Ioan Todinca
97-123
Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up
Fedor V. Fomin and Dimitrios M. Thilikos
83-129
Selfish Unsplittable Flows
Dimitris Fotakis, Spyros Kontogiannis and Paul Spirakis
31-61
A General Technique for Managing Strings in Comparison-Driven Data Structures
Gianni Franceschini and Roberto Grossi
618-629
Greedy Regular Expression Matching
Alain Frisch and Luca Cardelli
47-71
A 2O(n1-1/dlogn)2^{O(n^{1-{1\over d}}\log n)} Time Algorithm for d-Dimensional Protein Folding in the HP-Model
Bin Fu and Wei Wang
267-294
Nash Equilibria in Discrete Routing Games with Convex Latency Functions
Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien and Manuel Rode
7-23
Improved Results for Data Migration and Open Shop Scheduling
Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz and Hadas Shachnai
25-43
Deterministic M2M Multicast in Radio Networks
Leszek Gąsieniec, Evangelos Kranakis, Andrzej Pelc and Qin Xin
143-176
Syntactic Control of Concurrency
D. R. Ghica, A. S. Murawski and C. -H. L. Ong
1-5
Linear-Time List Decoding in Error-Free Settings
Venkatesan Guruswami and Piotr Indyk
7-23
A Categorical Model for the Geometry of Interaction
Esfandiar Haghverdi and Philip Scott
9-35
Testing Monotonicity over Graph Products
Shirley Halevy and Eyal Kushilevitz
521-544
The Minimum-Entropy Set Cover Problem
Eran Halperin and Richard M. Karp
7-29
Communication Versus Computation
Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim and S. Venkatesh
295-312
Optimal Website Design with the Constrained Subtree Selection Problem
Brent Heeringa and Micah Adler
235-252
Simple Permutations Mix Well
Shlomo Hoory, Avner Magen, Steven Myers and Charles Rackoff
782-792
Closest Pair Problems in Very High Dimensions
Piotr Indyk, Moshe Lewenstein, Ohad Lipsky and Ely Porat
155-175
Universality in Quantum Computation
Emmanuel Jeandel
69-79
Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design
Raja Jothi and Balaji Raghavachari
61-96
Fairness to All While Downsizing
Bala Kalyanasundaram and Mahe Velauthapillai
113-129
A Generalisation of Pre-logical Predicates to Simply Typed Formal Systems
Shin-ya Katsumata
97-109
A Faster Algorithm for Minimum Cycle Basis of Graphs
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail and Katarzyna Paluch
153-178
The Black-Box Complexity of Nearest Neighbor Search
Robert Krauthgamer and James R. Lee
31-57
Regular Solutions of Language Inequalities and Well Quasi-orders
Michal Kunc
882-893
A Calculus of Coroutines
J. Laird
73-96
Almost Optimal Decentralized Routing in Long-Range Contact Networks
Emmanuelle Lebhar and Nicolas Schabanel
97-112
Word Problems on Compressed Words
Markus Lohrey
171-211
Complexity of Pseudoknot Prediction in Simple Models
Rune B. Lyngsø
507-518
Property Testing of Regular Tree Languages
Frédéric Magniez and Michel de Rougemont
101-130
Entropy as a Fixed Point
Keye Martin
45-59
Transparent Long Proofs: A First PCP Theorem for
NP\mathbb R\mbox{NP}_{\mathbb R}
K. Meer
45-70
A Time Lower Bound for Satisfiability
Dieter van Melkebeek and Ran Raz
157-160
Some Results on Effective Randomness
Wolfgang Merkle, Nenad Mihailović and Theodore A. Slaman
29-41
A Polynomial Quantum Query Lower Bound for the Set Equality Problem
Gatis Midrijānis
75-86
Succinct Representations of Functions
J. Ian Munro and S. Srinivasa Rao
59-74
A Note on Karr’s Algorithm
Markus Müller-Olm and Helmut Seidl
479-504
The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs
S. Nikoletseas, C. Raptopoulos and P. Spirakis
3-26
Efficient Consistency Proofs for Generalized Queries on a Committed Database
Rafail Ostrovsky, Charles Rackoff and Adam Smith
111-124
A
2 \frac182 \frac{1}{8}-Approximation Algorithm for Rectangle Tiling
Katarzyna Paluch
135-152
Extensional Theories and Rewriting
Grigore Roşu
365-400
Hardness of String Similarity Search and Other Indexing Problems
S. Cenk Sahinalp and Andrey Utis
1099-1110
A Syntactic Characterization of Distributive LTL Queries
Marko Samer and Helmut Veith
81-90
Online Scheduling with Bounded Migration
Peter Sanders, Naveen Sivadasan and Martin Skutella
47-58
On the Expressive Power of Monadic Least Fixed Point Logic
Nicole Schweikardt
69-84
Counting in Trees for Free
Helmut Seidl, Thomas Schwentick, Anca Muscholl and Peter Habermehl
195-216
Games with Winning Conditions of High Borel Complexity
Olivier Serre
53-68
Propositional PSPACE Reasoning with Boolean Programs Versus Quantified Boolean Formulas
Alan Skelley
131-155
LA, Permutations, and the Hajós Calculus
Michael Soltys
177-204
A Calibration of Ineffective Theorems of Analysis in a Hierarchy of Semi-classical Logical Principles
Michael Toftdal
1201-1213
Efficiently Computing Succinct Trade-Off Curves
Sergei Vassilvitskii and Mihalis Yannakakis
25-46
On Randomization Versus Synchronization in Distributed Systems
Hagen Völzer
211-229
A New Algorithm for Optimal Constraint Satisfaction and Its Implications
Ryan Williams
139-152
On the Power of Ambainis’s Lower Bounds
Shengyu Zhang
Back matter