Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 61 Issue 3, May 2014

Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition
Krishnendu Chatterjee, Monika Henzinger
Article No.: 15
DOI: 10.1145/2597631

The computation of the winning set for Büchi objectives in alternating games on graphs is a central problem in computer-aided verification with a large number of applications. The long-standing best known upper bound for solving the problem...

Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces
Malte Helmert, Patrik Haslum, Jörg Hoffmann, Raz Nissim
Article No.: 16
DOI: 10.1145/2559951

Many areas of computer science require answering questions about reachability in compactly described discrete transition systems. Answering such questions effectively requires techniques to be able to do so without building the entire system. In...

Computing All Maps into a Sphere
Martin Čadek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, Uli Wagner
Article No.: 17
DOI: 10.1145/2597629

Given topological spaces X,Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps XY. We consider a computational version, where X,Y are given as...

Tight Bounds for Asynchronous Renaming
Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, Rachid Guerraoui
Article No.: 18
DOI: 10.1145/2597630

This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace.

We first...

The Cost of Fault Tolerance in Multi-Party Communication Complexity
Binbin Chen, Haifeng Yu, Yuda Zhao, Phillip B. Gibbons
Article No.: 19
DOI: 10.1145/2597633

Multi-party communication complexity involves distributed computation of a function over inputs held by multiple distributed players. A key focus of distributed computing research, since the very beginning, has been to tolerate failures. It is...