Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 63 Issue 3, September 2016

Section: Distributed Computing

The Locality of Distributed Symmetry Breaking
Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider
Article No.: 20
DOI: 10.1145/2903137

Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and...

Section: Learning Theory

Sample Compression Schemes for VC Classes
Shay Moran, Amir Yehudayoff
Article No.: 21
DOI: 10.1145/2890490

Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. Roughly speaking, a sample compression scheme of size k means that given an arbitrary list of...

Section: Probabilistic Algorithms

Random Walks That Find Perfect Objects and the Lovász Local Lemma
Dimitris Achlioptas, Fotis Iliopoulos
Article No.: 22
DOI: 10.1145/2818352

We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser’s entropic method proof of the Lovász Local Lemma (LLL)...

Section: Number-theoretic Computation

On the Complexity of the Orbit Problem
Ventsislav Chonev, Joël Ouaknine, James Worrell
Article No.: 23
DOI: 10.1145/2857050

We consider higher-dimensional versions of Kannan and Lipton’s Orbit Problem—determining whether a target vector space ν may be reached from a starting point x under repeated applications of a linear transformation...

Section: Computer-aided Verification

Formally Reasoning About Quality
Shaull Almagor, Udi Boker, Orna Kupferman
Article No.: 24
DOI: 10.1145/2875421

In recent years, there has been a growing need and interest in formally reasoning about the quality of software and hardware systems. As opposed to traditional verification, in which one considers the question of whether a system satisfies a given...

Section: Logic and Computation

Semantics Out of Context: Nominal Absolute Denotations for First-Order Logic and Computation
Murdoch J. Gabbay
Article No.: 25
DOI: 10.1145/2700819

Call a semantics for a language with variables absolute when variables map to fixed entities in the denotation. That is, a semantics is absolute when the denotation of a variable a is a copy of itself in the denotation.


Section: Randomized Algorithms and Probabilistic Analysis

Analyzing Network Coding (Gossip) Made Easy
Bernhard Haeupler
Article No.: 26
DOI: 10.1145/2629696

We introduce projection analysis—a new technique to analyze the stopping time of protocols that are based on random linear network coding (RLNC). Projection analysis drastically simplifies, extends, and strengthens previous results on RLNC...

Section: Invited Articles Section

Invited Articles Foreword
Eva Tardos
Article No.: 27e
DOI: 10.1145/2940319

Section: Complexity

Approximation Resistance from Pairwise-Independent Subgroups
Siu On Chan
Article No.: 27
DOI: 10.1145/2873054

We show optimal (up to a constant factor) NP-hardness for a maximum constraint satisfaction problem with k variables per constraint (Max-kCSP) whenever k is larger than the domain size. This follows from our main result...

Section: Computational Biology

Improved Algorithms for Constructing Consensus Trees
Jesper Jansson, Chuanqi Shen, Wing-Kin Sung
Article No.: 28
DOI: 10.1145/2925985

A consensus tree is a single phylogenetic tree that summarizes the branching structure in a given set of conflicting phylogenetic trees. Many different types of consensus trees have been proposed in the literature; three of the most...