Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 61 Issue 4, July 2014

Section: Algorithms, Graph Algorithms

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
Yuri Faenza, Gianpaolo Oriolo, Gautier Stauffer
Article No.: 20
DOI: 10.1145/2629600

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(|V|(|E| + |V| log|V|))-time, drastically improving the previous best known complexity bound. This...

Section: Analysis of Algorithms

The Convergence of Bird Flocking
Bernard Chazelle
Article No.: 21
DOI: 10.1145/2629613

We bound the time it takes for a group of birds to stabilize in a standard flocking model. Each bird averages its velocity with its neighbors lying within a fixed radius. We resolve the worst-case complexity of this natural algorithm by providing...

Section: Communication Complexity, Lower Bounds, Matrix Ranks

An Additive Combinatorics Approach Relating Rank to Communication Complexity
Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi
Article No.: 22
DOI: 10.1145/2629598

Identifying complexity measures that bound the communication complexity of a {0,1}-valued matrix M is one the most fundamental problems in communication complexity. Mehlhorn and Schmidt [1982] were the first to suggest matrix-rank as one...

Section: Computational Complexity

Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
Holger Dell, Dieter Van Melkebeek
Article No.: 23
DOI: 10.1145/2629620

Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of...

Section: Logics and Meanings of Programs

A Logic for True Concurrency
Paolo Baldan, Silvia Crafa
Article No.: 24
DOI: 10.1145/2629638

We propose a logic for true concurrency whose formulae predicate about events in computations and their causal dependencies. The induced logical equivalence is hereditary history-preserving bisimilarity, and fragments of the logic can be...

Section: Invited Articles Section

Invited Articles Foreword
Victor Vianu
Article No.: 25
DOI: 10.1145/2632167

Section: Programming Languages

Ranking Functions for Linear-Constraint Loops
Amir M. Ben-Amram, Samir Genaim
Article No.: 26
DOI: 10.1145/2629488

In this article, we study the complexity of the problems: given a loop, described by linear constraints over a finite set of variables, is there a linear or lexicographical-linear ranking function for this loop? While existence of such functions...

Denotational Semantics with Nominal Scott Domains
Steffen Lösch, Andrew M. Pitts
Article No.: 27
DOI: 10.1145/2629529

When defining computations over syntax as data, one often runs into tedious issues concerning α-equivalence and semantically correct manipulations of binding constructs. Here we study a semantic framework in which these issues can be...