Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 53 Issue 3, May 2006

Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk
Pages: 307-323
DOI: 10.1145/1147954.1147955
In this article, we show several results obtained by combining the use of stable distributions with pseudorandom generators for bounded space. In particular:---We show that, for any p ∈ (0, 2], one can maintain (using only...

Dependent rounding and its applications to approximation algorithms
Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan
Pages: 324-360
DOI: 10.1145/1147954.1147956
We develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to improved (approximation) algorithms for various problems....

Interface surfaces for protein-protein complexes
Yih-En Andrew Ban, Herbert Edelsbrunner, Johannes Rudolph
Pages: 361-378
DOI: 10.1145/1147954.1147957
Protein-protein interactions, which form the basis for most cellular processes, result in the formation of protein interfaces. Believing that the local shape of proteins is crucial, we take a geometric approach and present a definition of an...

Split-ordered lists: Lock-free extensible hash tables
Ori Shalev, Nir Shavit
Pages: 379-405
DOI: 10.1145/1147954.1147958
We present the first lock-free implementation of an extensible hash table running on current architectures. Our algorithm provides concurrent insert, delete, and find operations with an expected O(1) cost. It consists of very simple code,...

Probabilistic parsing strategies
Mark-Jan Nederhof, Giorgio Satta
Pages: 406-436
DOI: 10.1145/1147954.1147959
We present new results on the relation between purely symbolic context-free parsing strategies and their probabilistic counterparts. Such parsing strategies are seen as constructions of push-down devices from grammars. We show that preservation of...

The generalized two-server problem
René A. Sitters, Leen Stougie
Pages: 437-458
DOI: 10.1145/1147954.1147960
We consider the generalized on-line two-server problem in which each server moves in its own metric space. Requests for service arrive one-by-one and every request is represented by two points: one in each metric space. The problem is to move, at...

Alpha-structural recursion and induction
Andrew M. Pitts
Pages: 459-506
DOI: 10.1145/1147954.1147961
The nominal approach to abstract syntax deals with the issues of bound names and α-equivalence by considering constructions and properties that are invariant with respect to permuting names. The use of permutations gives rise to an...

Computing with highly mixed states
Andris Ambainis, Leonard J. Schulman, Umesh Vazirani
Pages: 507-531
DOI: 10.1145/1147954.1147962
Device initialization is a difficult challenge in some proposed realizations of quantum computers, and as such, must be treated as a computational resource. The degree of initialization can be quantified by k, the number of clean qubits in the...