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