Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 60 Issue 4, August 2013

The HOM problem is decidable
Guillem Godoy, Omer Giménez
Article No.: 23
DOI: 10.1145/2501600

We close affirmatively a question that has been open for long time: decidability of the HOM problem. The HOM problem consists in determining, given a tree homomorphism H and a regular tree language L represented by a tree automaton,...

Decomposing combinatorial auctions and set packing problems
Georg Gottlob, Gianluigi Greco
Article No.: 24
DOI: 10.1145/2505987

Combinatorial auctions allow bidders to bid on bundles of items rather than just on single items. The winner determination problem in combinatorial auctions is the problem of determining the allocation of items to bidders such that the sum of the...

Matrix sparsification and nested dissection over arbitrary fields
Noga Alon, Raphael Yuster
Article No.: 25
DOI: 10.1145/2505989

The generalized nested dissection method, developed by Lipton et al. [1979], is a seminal method for solving a linear system Ax=b where A is a symmetric positive definite matrix. The method runs extremely fast whenever...

All-pairs shortest paths in O(n2) time with high probability
Yuval Peres, Dmitry Sotnikov, Benny Sudakov, Uri Zwick
Article No.: 26
DOI: 10.1145/2505988

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O(n2), in expectation...

Invited articles foreword
Victor Vianu
Article No.: 27
DOI: 10.1145/2508028.2508032

Data exchange beyond complete data
Marcelo Arenas, Jorge Pérez, Juan Reutter
Article No.: 28
DOI: 10.1145/2505985

In the traditional data exchange setting, source instances are restricted to be complete in the sense that every fact is either true or false in these instances. Although natural for a typical database translation scenario, this restriction...

Game semantics for a polymorphic programming language
J. Laird
Article No.: 29
DOI: 10.1145/2505986

This article presents a game semantics for higher-rank polymorphism, leading to a new model of the calculus System F, and a programming language which extends it with mutable variables. In contrast to previous game models of polymorphism, it is...