Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 63 Issue 1, March 2016

Section: Communication Complexity

Communication is Bounded by Root of Rank
Shachar Lovett
Article No.: 1
DOI: 10.1145/2724704

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...

Section: Approximation Algorithms

Removing and Adding Edges for the Traveling Salesman Problem
Tobias Mömke, Ola Svensson
Article No.: 2
DOI: 10.1145/2739008

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...

Section: Parallel Computing

Network-Oblivious Algorithms
Gianfranco Bilardi, Andrea Pietracaprina, Geppino Pucci, Michele Scquizzato, Francesco Silvestri
Article No.: 3
DOI: 10.1145/2812804

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...

Section: Word Equations

Recompression: A Simple and Powerful Technique for Word Equations
Artur Jeż
Article No.: 4
DOI: 10.1145/2743014

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...

Section: Economics and Computation

Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations
Shahar Dobzinski, Jan Vondrák
Article No.: 5
DOI: 10.1145/2786754

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...

Section: Algorithms & Data Structures

An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets
Pierre Fraigniaud, Amos Korman
Article No.: 6
DOI: 10.1145/2794076

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...

Section: Database Systems & Theory

Algebraic Structures for Capturing the Provenance of SPARQL Queries
Floris Geerts, Thomas Unger, Grigoris Karvounarakis, Irini Fundulaki, Vassilis Christophides
Article No.: 7
DOI: 10.1145/2810037

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...

Section: Invited Articles Section

Invited Articles Foreword
Eva Tardos
Article No.: 8
DOI: 10.1145/2875947

Section: Concurrent, Distributed, and Parallel Languages

Multiparty Asynchronous Session Types
Kohei Honda, Nobuko Yoshida, Marco Carbone
Article No.: 9
DOI: 10.1145/2827695

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...

Section: Computer-aided Verification

Parameterized Verification of Asynchronous Shared-Memory Systems
Javier Esparza, Pierre Ganty, Rupak Majumdar
Article No.: 10
DOI: 10.1145/2842603

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....