Invited Talks |
Molecular Assembly and Computation: From Theory to Experimental Demonstrations / John H. Reif |
Towards a Predictive Computational Complexity Theory / Madhav V. Marathe |
Equivariant Syntax and Semantics / Andrew M. Pitts |
L(A) = L(B)? Decidability Results from Complete Formal Systems / Géraud Sénizergues (Gödel Prize 2002) |
Discrete Tomography: Reconstruction under Periodicity Constraints / Alberto Del Lungo ; Andrea Frosini ; Maurice Nivat ; Laurent Vuillon |
Local and Global Methods in Data Mining: Basic Techniques and Open Problems / Heikki Mannila |
Program Debugging and Validation Using Semantic Approximations and Partial Specifications / M. Hermenegildo ; G. Puebla ; F. Bueno ; P. López García |
Best Papers |
Inapproximability Results for Equations over Finite Groups / Lars Engebretsen ; Jonas Holmerin ; Alexander Russell |
A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs / Seth Pettie |
On Families of Graphs Having a Decidable First Order Theory with Reachability / Thomas Colcombet |
Contributions |
Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet / Alex Fabrikant ; Elias Koutsoupias ; Christos H. Papadimitriou |
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game / Dimitris Fotakis ; Spyros Kontogiannis ; Marios Mavronicolas ; Paul Spirakis |
Control Message Aggregation in Group Communication Protocols / Sanjeev Khanna ; Joseph (Seffi) Naor ; Dan Raz |
Church-Rosser Languages vs. UCFL / Tomasz Jurdziński ; Krzysztof Loryś |
Intersection of Regular Languages and Star Hierarchy / Sebastian Bala |
On the Construction of Reversible Automata for Reversible Languages / Sylvain Lombardy |
Priority Queues, Pairing, and Adaptive Sorting / Amr Elmasry |
Exponential Structures for Efficient Cache-Oblivious Algorithms / Michael A. Bender ; Richard Cole ; Rajeev Raman |
Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations / Russell Impagliazzo ; Nathan Segerlind |
On the Complexity of Resolution with Bounded Conjunctions / Juan Luis Esteban ; Nicola Galesi ; Jochen Messner |
Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes / Aggelos Kiayias ; Moti Yung |
Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials / Yuval Ishai ; Eyal Kushilevitz |
Exponential Lower Bound for Static Semi-algebraic Proofs / Dima Grigoriev ; Edward A. Hirsch ; Dmitrii V. Pasechnik |
Paths Problems in Symmetric Logarithmic Space / Andreas Jakoby ; Maciej Liśkiewicz |
Scheduling Search Procedures / Peter Damaschke |
Removable Online Knapsack Problems / Kazuo Iwama ; Shiro Taketomi |
New Bounds for Variable-Sized and Resource Augmented Online Bin Packing / Leah Epstein ; Steve Seiden ; Rob van Stee |
The Quest for Small Universal Cellular Automata / Nicolas Ollinger |
Hyperbolic Recognition by Graph Automata / Christophe Papazian ; Eric Rémila |
Quantum and Stochastic Branching Programs of Bounded Width / Farid Ablayev ; Cristopher Moore ; Christopher Pollett |
Spanning Trees with Bounded Number of Branch Vertices / Luisa Gargano ; Pavol Hell ; Ladislav Stacho ; Ugo Vaccaro |
Energy Optimal Routing in Radio Networks Using Geometric Data Structures / René Beier ; Peter Sanders ; Naveen Sivadasan |
Gossiping with Bounded Size Messages in ad hoc Radio Networks / Malin Christersson ; Leszek G&acedil;sieniec ; Andrzej Lingas |
The Kolmogorov-Loveland Stochastic Sequences Are Not Closed under Selecting Subsequences / Wolfgang Merkle |
The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications / Robert A. Hearn ; Erik D. Demaine |
Constraint Satisfaction Problems in Non-deterministic Logarithmic Space / Víctor Dalmau |
Cache Oblivious Distribution Sweeping / Gerth Stølting Brodal ; Rolf Fagerberg |
One-Probe Search / Anna Östlin ; Rasmus Pagh |
New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems / Moses Charikar ; Piotr Indyk ; Rina Panigrahy |
Measuring the Probabilistic Powerdomain / Keye Martin ; Michael Mislove ; James Worrell |
Games Characterizing Levy-Longo Trees / C.-H.L. Ong ; P. Di Gianantonio |
Comparing Functional Paradigms for Exact Real-Number Computation / Andrej Bauer ; Martín Hötzel Escardó ; Alex Simpson |
Random Sampling from Boltzmann Principles / Philippe Duchon ; Philippe Flajolet ; Guy Louchard ; Gilles Schaeffer |
On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures / Amalia Duch ; Conrado Martínez |
Bialgebraic Modelling of Timed Processes / Marco Kick |
Testing Labelled Markov Processes / Franck van Breugel ; Steven Shalit |
Why Computational Complexity Requires Stricter Martingales / John M. Hitchcock ; Jack H. Lutz |
Correspondence Principles for Effective Dimensions |
A Total Approach to Partial Algebraic Specification / José Meseguer ; Grigore Roşu |
Axiomatising Divergence / Markus Lohrey ; Pedro R. D'Argenio ; Holger Hermanns |
A Spatial Logic for Querying Graphs / Luca Cardelli ; Philippa Gardner ; Giorgio Ghelli |
Improving Time Bounds on Maximum Generalised Flow Computations by Contracting the Network / Tomasz Radzik |
Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION / Piotr Berman ; Marek Karpinski |
Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths / Camil Demetrescu ; Giuseppe F. Italiano |
Synthesis of Uninitialized Systems / Thomas A. Henzinger ; Sriram C. Krishnan ; Orna Kupferman ; Freddy Y.C. Mang |
Infinite-State High-Level MSCs: Model-Checking and Realizability / Blaise Genest ; Anca Muscholl ; Helmut Seidl ; Marc Zeitoun |
Universal Inherence of Cycle-Free Context-Free Ambiguity Functions / Klaus Wich |
Histogramming Data Streams with Fast Per-Item Processing / Sudipto Guha ; S. Muthukrishnan ; Martin J. Strauss |
Finding Frequent Items in Data Streams / Kevin Chen ; Martin Farach-Colton |
Symbolic Strategy Synthesis for Games on Pushdown Graphs / Thierry Cachat |
Strong Bisimilarity and Regularity of Basic Process Algebra Is PSPACE-Hard / Jiří Srba |
Solving the String Statistics Problem in Time <$>{\cal O}<$>(n log n) / Rune B. Lyngsø ; Christian N.S. Pedersen |
A PTAS for Distinguishing (Sub)string Selection / Xiaotie Deng ; Guojun Li ; Zimao Li ; Bin Ma ; Lusheng Wang |
On the Theory of One-Step Rewriting in Trace Monoids / Dietrich Kuske |
Navigating with a Browser / Michail Bielecki ; Jan Hidders ; Jan Paredaens ; Jerzy Tyszkiewicz ; Jan Van den Bussche |
Improved Results for Stackelberg Scheduling Strategies / V.S. Anil Kumar |
Call Control in Rings / Udo Adamy ; Christoph Ambuehl ; R. Sai Anand ; Thomas Erlebach |
Preemptive Scheduling in Overloaded Systems / Marek Chrobak ; John Noga ; Jiří Sgall ; Tomáš Tichý ; Nodari Vakhania |
The Equivalence Problem of Finite Substitutions on ab*c, with Applications / J. Karhumäki ; L.P. Lisovik |
Deciding DPDA Equivalence Is Primitive Recursive / Colin Stirling |
Two-Way Alternating Automata and Finite Models / Mikolaj Bojańczyk |
Approximating Huffman Codes in Parallel / Yakov Nekrich |
Seamless Integration of Parallelism and Memory Hierarchy / Carlo Fantozzi ; Andrea Pietracaprina ; Geppino Pucci |
The Communication Complexity of Approximate Set Packing and Covering / Noam Nisan |
Antirandomizing the Wrong Game / Benjamin Doerr |
Fast Universalization of Investment Strategies with Provably Good Relative Returns / Karhan Akcoglu ; Petros Drineas ; Ming-Yang Kao |
Randomized Pursuit-Evasion in Graphs / Micah Adler ; Harald Räcke ; Christian Sohler ; Berthold Vöcking |
The Essence of Principal Typings / J. B. Wells |
Complete and Tractable Local Linear Time Temporal Logics over Traces / Bharat Adsul ; Milind Sohoni |
An Elementary Expressively Complete Temporal Logic for Mazurkiewicz Traces / Paul Gastin ; Madhavan Mukund |
Random Numbers and an Incomplete Immune Recursive Set / Vasco Brattka |
A Banach-Mazur Computable But Not Markov Computable Function on the Computable Real Numbers / Peter Hertling |
Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem / Artur Czumaj ; Hairong Zhao |
Finding a Path of Superlogarithmic Length / Andreas Björklund ; Thore Husfeldt |
Linear Time Algorithms on Chordal Bipartite and Strongly Chordal Graphs / Ryuhei Uehara |
Improved Inapproximability Results for Vertex Cover on k-Uniform Hypergraphs |
Efficient Testing of Hypergraphs / Yoshiharu Kohayakawa ; Brendan Nagle ; Vojtěch Rödl |
Optimal Net Surface Problems with Applications / Xiaodong Wu ; Danny Z. Chen |
Wagner's Theorem on Realizers / Nicolas Bonichon ; Bertrand Le Saëc ; Mohamed Mosbah |
Circular Arrangements / Vincenzo Liberatore |
Author Index |
Invited Talks |
Molecular Assembly and Computation: From Theory to Experimental Demonstrations / John H. Reif |
Towards a Predictive Computational Complexity Theory / Madhav V. Marathe |