A Complexity Dichotomy for Partition Functions with Mixed Signs
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum and Marc Thurley
Locally Decodable Quantum Codes
Jop Briët and Ronald de Wolf
Ambiguity and Communication
Juraj Hromkovič and Georg Schnitger
Nonclairvoyant Speed Scaling for Flow and Energy
Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto
Marchetti-Spaccamela and Kirk Pruhs
Error-Correcting Data Structures
Ronald de Wolf
Tractable Structures for Constraint Satisfaction with Truth Tables
Dániel Marx
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression
Danny Hermelin, Gad M. Landau, Shir Landau and Oren Weimann
Compressed Representations of Permutations, and Applications
Jérémy Barbay and Gonzalo Navarro
Randomness on Computable Probability Spaces. A Dynamical Point of View
Peter Gács, Mathieu Hoyrup and Cristóbal Rojas
Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
Marius Zimand
The Price of Anarchy in Cooperative Network Creation Games
Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini and Morteza Zadimoghaddam
Undecidable Properties of Limit Set Dynamics of Cellular Automata
Pietro Di Lena and Luciano Margara
Polynomial Kernelizations for MIN F+Π1 and MAX NP
Stefan Kratsch
Approximating Acyclicity Parameters of Sparse Hypergraphs
Fedor Fomin, Petr Golovach and Dimitrios Thilikos
A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
Kenya Ueno
Büchi Complementation Made Tight
Sven Schewe
A Generalization of Nemhauser and Trotter's Local Optimization Theorem
Michael R. Fellows, Jiong Guo, Hannes Moser and Rolf Niedermeier
Strong Completeness of Coalgebraic Modal Logics
Lutz Schröder and Dirk Pattinson
Testing Linear-Invariant Non-Linear Properties
Arnab Bhattacharyya, Victor Chen, Madhu Sudan and Ning Xie
Efficient Isomorphism Testing for a Class of Group Extensions
François Le Gall
Kolmogorov Complexity and Solovay Functions
Laurent Bienvenu and Rod Downey
On Approximating Multi-Criteria TSP
Bodo Manthey
Fragments of First-Order Logic over Infinite Words
Volker Diekert and Manfred Kufleitner
Optimal Cache-Aware Suffix Selection
Gianni Franceschini, Roberto Grossi and S. Muthukrishnan
Equations over Sets of Natural Numbers with Addition Only
Artur Jeż and Alexander Okhotin
On the Borel Inseparability of Game Tree Languages
Szczepan Hummel, Henryk Michalewski and Damian Niwiński
Generating Shorter Bases for Hard Random Lattices
Joël Alwen and Chris Peikert
An Approximation Algorithm for l∞-Fitting Robinson Structures to Distances
Victor Chepoi and Morgan Seston
Improved Approximations for Guarding 1.5-Dimensional Terrains
Khaled Elbassioni, Erik Krohn, Domagoj Matijević, Julián Mestre and Domagoj Ševerdija
Economical Caching
Matthias Englert, Heiko Röglin, Jacob Spönemann and Berthold Vöcking
Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
André Gronemeier
More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
Roberto Grossi, Alessio Orlandi, Rajeev Raman and S. Srinivasa Rao
The Dynamic Complexity of Formal Languages
Wouter Gelade, Marcel Marquardt and Thomas Schwentick
Cover Time and Broadcast Time
Robert Elsässer and Thomas Sauerwald
Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties
Mahdi Cheraghchi and Amin Shokrollahi
Semi-Online Preemptive Scheduling: One Algorithm for All Variants
Tomáš Ebenlendr and Jiří Sgall
Quantum Query Complexity of Multilinear Identity Testing
Vikraman Arvind and Partha Mukhopadhyay
Hardness and Algorithms for Rainbow Connectivity
Sourav Chakraborty, Eldar Fischer, Arie Matsliah and Raphael Yuster
Qualitative Reachability in Stochastic BPA Games
Tomáš Brázdil, Václav Brožek, Antonín Kučera and Jan Obdržálek
Reverse Engineering Prefix Tables
Julien Clément, Maxime Crochemore and Giuseppina Rindone
Computing Graph Roots Without Short Cycles
Babak Farzad, Lap Chi Lau, Van Bang Le and Nguyen Ngoc Tuy
A Polynomial Kernel for Multicut In Trees
Nicolas Bousquet, Jean Daligault, Stéphan Thomassé and Anders Yeo
Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
Fabian Kuhn
Enumerating Homomorphisms
Andrei A. Bulatov, Víctor Dalmau, Martin Grohe and Dániel Marx
Forward Analysis for WSTS, Part I: Completions
Alain Finkel and Jean Goubault-Larrecq
An Order on Sets of Tilings Corresponding to an Order on Languages
Nathalie Aubrun and Mathieu Sablik
Shortest Paths Avoiding Forbidden Subpaths
Mustaq Ahmed and Anna Lubiw
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh and Yngve Villanger
On Local Symmetries and Universality in Cellular Automata
Laurent Boyer and Guillaume Theyssier
Random Fruits on the Zielonka Tree
Florian Horn
Weak MSO with the Unbounding Quantifier
Mikołaj Bojańczyk
On the Average Complexity of Moore's State Minimization Algorithm
Frédérique Bassino, Julien David and Cyril Nicaud
Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata
Daniel Kirsten and Sylvain Lombardy
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
Glencora Borradaile, Erik D. Demaine and Siamak Tazari