Search ACM DL

Search Issue

enter search term and/or author name

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

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

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

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

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

**Invited Articles Foreword**

Victor Vianu

Article No.: 25

DOI: 10.1145/2632167

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