Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 54 Issue 4, July 2007

(Almost) Tight bounds and existence theorems for single-commodity confluent flows
Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta
Article No.: 16
DOI: 10.1145/1255443.1255444

A flow of a commodity is said to be confluent if at any node all the flow of the commodity leaves along a single edge. In this article, we study single-commodity confluent flow problems, where we need to route given node demands to a single...

A new look at survey propagation and its generalizations
Elitza Maneva, Elchanan Mossel, Martin J. Wainwright
Article No.: 17
DOI: 10.1145/1255443.1255445

This article provides a new conceptual perspective on survey propagation, which is an iterative algorithm recently introduced by the statistical physics community that is very effective in solving random k-SAT problems even with...

Optimal pants decompositions and shortest homotopic cycles on an orientable surface
Éric Colin De Verdière, Francis Lazarus
Article No.: 18
DOI: 10.1145/1255443.1255446

We consider the problem of finding a shortest cycle (freely) homotopic to a given simple cycle on a compact, orientable surface. For this purpose, we use a pants decomposition of the surface: a set of disjoint simple cycles that cut the...

On deciding well-definedness for query languages on trees
Stijn Vansummeren
Article No.: 19
DOI: 10.1145/1255443.1255447

The well-definedness problem for a database query language consists of checking, given an expression and an input type, that the expression never yields a runtime error on any input adhering to the input type. In this article, we study the...

Periodicity and unbordered words: A proof of the extended duval conjecture
Tero Harju, Dirk Nowotka
Article No.: 20
DOI: 10.1145/1255443.1255448

The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this article. Consider a finite word w of length n. We call a word bordered if it has a proper prefix, which is...

Sampling from large matrices: An approach through geometric functional analysis
Mark Rudelson, Roman Vershynin
Article No.: 21
DOI: 10.1145/1255443.1255449

We study random submatrices of a large matrix A. We show how to approximately compute A from its random submatrix of the smallest possible size O(rlog r) with a small error in the spectral norm, where r...