Table of Contents
New Developments in Quantum Algorithms (Invited Talk) Andris Ambainis 1
Persistent Homology under Non-uniform Error (Invited Talk) Paul Bendich Herbert Edelsbrunner Michael Kerber Amit Patel 12
Information Complexity of Online Problems (Invited Talk) Juraj Hromkovic Rastislav Královic Richard Královic 24
Algorithmic Lower Bounds for Problems on Decomposable Graphs (Abstract of Invited Talk) Daniel Lokshtanov 37
Do We Really Understand the Crossing Numbers" (Invited Talk) Bojan Mohar 38
Balanced Queries: Divide and Conquer Dmitri Akatov Georg Gottlob 42
Slowly Synchronizing Automata and Digraphs Dmitry Ananichev Vladimir Gusev Mikhail Volkov 55
Weights of Exact Threshold Functions László Babai Kristoffer Arnsfelt Hansen Vladimir V. Podolskii Xiaoming Sun 66
Proof Systems and Transformation Games Yoram Bachrach Michael Zuckerman Michael Wooldridge Jeffrey S. Rosenschein 78
Scheduling Real-Time Mixed-Criticality Jobs Sanjoy K. Baruah Vincenzo Bonifaci Gianlorenzo D'Angelo Haohan Li Alberto Marchetti-Spaccamela Nicole Megow Leen Stougie 90
A DEXPTIME-Complete Dolev-Yao Theory with Distributive Encryption A. Baskar R. Ramanujam S.P. Suresh 102
On Problem Kernels for Possible Winner Determination under the k-Approval Protocol Nadja Betzler 114
Counting Minimum (s, t)-Cuts in Weighted Planar Graphs in Polynomial Time Ivona Bezáková Adam J. Friedlander 126
Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree Davide Biló Luciano Gualà Guido Proietti 138
Improved Approximability and Non-approximability Results for Graph Diameter Decreasing Problems Davide Bilò Luciano Gualà Guido Proietti 150
Distance Constraint Satisfaction Problems Manuel Bodirsky Victor Dalmau Barnaby Martin Michael Pinsker 162
Faster Algorithms on Branch and Clique Decompositions Hans L. Bodlaender Erik Jan van Leeuwen Johan M.M. van Rooij Martin Vatshelle 174
Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks Beate Bollig 186
Robust Computations with Dynamical Systems Olivier Bournez Daniel S. Graça Emmanuel Hainry 198
On Factor University in Symbolic Spaces Laurent Boyer Guillaume Theyssier 209
Toward a Deterministic Polynomial Time Algorithm with Optimal Additive Query Complexity Nader H. Bshouty Hanna Mazzawi 221
Resource Combinatory Algebras Alberto Carraro Thomas Ehrhard Antonino Salibra 233
Randomness for Free Krishnendu Chatterjee Laurent Doyen Hugo Gimbert Thomas A. Henzinger 246
Qualitative Analysis of Partially-Observable Markov Decision Processes Krishnendu Chatterjee Laurent Doyen Thomas A. Henzinger 258
All Symmetric Predicates in NSPACE (n2) Are Stably Computable by the Mediated Population Protocol Model Ioannis Chatzigiannakis Othon Michail Stavros Nikolaou Andreas Pavlogiannis Paul G. Spirakis 270
Online Clustering with Variable Sized Clusters János Csirik Leah Epstein Csanád Imreh Asaf Levin 282
Deterministic Rendezvous of Asynchronous Bounded-Memory Agents in Polygonal Terrains Jurek Czyzowicz Adrian Kosowski Andrzej Pelc 294
Counting Classes and the Fine Structure between NC1 and L Samir Datta Meena Mahajan B.V. Raghavendra Rao Michael Thomas Heribert Vollmer 306
The Average Complexity of Moore's State Minimization Algorithm Is O (n log log n) Julien David 318
Connected Searching of Weighted Trees Dariusz Dereniowski 330
Iterated Regret Minimization in Game Graphs Emmanuel Filiot Tristan Le Gall Jean-François Raskin 342
Properties of Visibly Pushdown Transducers Emmanuel Filiot Jean-François Raskin Pierre-Alain Reynier Frédéric Servais Jean-Marc Talbot 355
Second-Order Algebraic Theories (Extended Abstract) Marcelo Fiore Ola Mahmoud 368
Frame Definability for Classes of Trees in the μ-calculus Gaëlle Fontaine Thomas Place 381
Evaluating Non-square Sparse Bilinear Forms on Multiple Vector Pairs in the I/O-Model Gero Greiner Riko Jacob 393
Finding and Counting Vertex-Colored Subtrees Sylvain Guillemot Florian Sikora 405
Limiting Negations in Bounded Treewidth and Upward Planar Circuits Jing He Hongyu Liang Jayalal M. N. Sarma 417
On the Topological Complexity of MSO+U and Related Automata Models Szczepan Hummel Michal Skrzypczak Szymon Torunczyk 429
Least and Greatest Solutions of Equations over Sets of Integers Artur Jez Alexander Okhotin 441
Improved Simulation of Nondeterministic Turing Machines Subrahmanyam Kalyanasundaram Richard J. Lipton Kenneth W. Regan Farbod Shokrieh 453
The Prize-Collecting Edge Dominating Set Problem in Trees Naoyuki Kamiyama 465
The Multivariate Resultant Is NP-hard in Any Characteristic Bruno Grenet Pascal Koiran Natacha Portier 477
Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems Stefan Kratsch Dániel Marx Magnus Wahlström 489
Meta-Envy-Free Cake-Cutting Protocols Yoshifumi Manabe Tatsuaki Okamoto 501
Two Variables and Two Successors Amaldev Manuel 513
Harnessing MLF with the Power of System F Giulio Manzonetto Paolo Tranquilli 525
Describing Average- and Longtime-Behavior by Weighted MSO Logics Manfred Droste Ingmar Meinecke 537
Solving MINONES-2-SAT as Fast as VERTEX COVER Neeldhara Misra N.S. Narayanaswamy Venkatesh Raman Bal Sri Shankar 549
Unambiguous Finite Automata over a Unary Alphabet Alexander Okhotin 556
The Complexity of Finding Reset Words in Finite Automata Jörg Olschewski Michael Ummels 568
Does Treewidth Help in Modal Satisfiability" (Extended Abstract) M. Praveen 580
Asynchronous Omega-Regular Games with Partial Information Bernd Puchala 592
Parity Games with Partial Information Played on Graphs of Bounded Complexity Bernd Puchala Roman Rabinovich 604
Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets Philippe Schnoebelen 616
Enumeration of the Monomials of a Polynomial and Related Complexity Classes Yann Strozecki 629
Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs Siamak Tazari 641
Semi-linear Parikh Images of Regular Expressions via Reduction Bahareh Badban Mohammad Torabi Dashti 653
Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds Kenya Ueno 665
Mesh Deformation of Dynamic Smooth Manifolds with Surface Correspondences Ho-Lun Cheng Ke Yan 677
Counting Dependent and Independent Strings Marius Zimand 689
Impossibility of Independence Amplification in Kolmogorov Complexity Theory Marius Zimand 701
Author Index 713
