enter search term and/or author name
We prove that any total boolean function of rank r can be computed by a deterministic communication protocol of complexity O(&sqrt; ċ log(r)). Equivalently, any graph whose adjacency matrix has rank r has chromatic...
Removing and Adding Edges for the Traveling Salesman Problem
Tobias Mömke, Ola Svensson
Article No.: 2
We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges...
Gianfranco Bilardi, Andrea Pietracaprina, Geppino Pucci, Michele Scquizzato, Francesco Silvestri
Article No.: 3
A framework is proposed for the design and analysis of network-oblivious algorithms, namely algorithms that can run unchanged, yet efficiently, on a variety of machines characterized by different degrees of parallelism and communication...
Recompression: A Simple and Powerful Technique for Word Equations
Article No.: 4
In this article, we present an application of a simple technique of local recompression, previously developed by the author in the context algorithms for compressed strings [Jeż 2014a, 2015b, 2015a], to word equations. The technique is based...
Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations
Shahar Dobzinski, Jan Vondrák
Article No.: 5
A long-standing open question in algorithmic mechanism design is whether there exist computationally efficient truthful mechanisms for combinatorial auctions, with performance guarantees close to those possible without considerations of...
An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets
Pierre Fraigniaud, Amos Korman
Article No.: 6
In this article, we solve the ancestry-labeling scheme problem, which aims at assigning the shortest possible labels (bit strings) to nodes of rooted trees, so ancestry queries between any two nodes can be answered by inspecting their...
The evaluation of SPARQL algebra queries on various kinds of annotated RDF graphs can be seen as a particular case of the evaluation of these queries on RDF graphs annotated with elements of so-called spm-semirings. Spm-semirings extend...
Communication is a central elements in software development. As a potential typed foundation for structured communication-centered programming, session types have been studied over the past decade for a wide range of process calculi and...
Parameterized Verification of Asynchronous Shared-Memory Systems
Javier Esparza, Pierre Ganty, Rupak Majumdar
Article No.: 10
We characterize the complexity of the safety verification problem for parameterized systems consisting of a leader process and arbitrarily many anonymous and identical contributors. Processes communicate through a shared, bounded-value register....