Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 57 Issue 4, April 2010

Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors
B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, A. Wigderson
Article No.: 20
DOI: 10.1145/1734213.1734214

We present new explicit constructions of deterministic randomness extractors, dispersers and related objects. We say that a distribution X on binary strings of length n is a δ-source if X assigns probability at...

Ultra-low-dimensional embeddings for doubling metrics
T.-H. Hubert Chan, Anupam Gupta, Kunal Talwar
Article No.: 21
DOI: 10.1145/1734213.1734215

We consider the problem of embedding a metric into low-dimensional Euclidean space. The classical theorems of Bourgain, and of Johnson and Lindenstrauss say that any metric on n points embeds into an O(log n)-dimensional...

Tight failure detection bounds on atomic object implementations
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui
Article No.: 22
DOI: 10.1145/1734213.1734216

This article determines the weakest failure detectors to implement shared atomic objects in a distributed system with crash-prone processes. We first determine the weakest failure detector for the basic register object. We then use that to...

Set constraints with projections
Witold Charatonik Leszek Pacholski
Article No.: 23
DOI: 10.1145/1734213.1734217

Set constraints form a constraint system where variables range over the domain of sets of trees. They give a natural formalism for many problems in program analysis. Syntactically, set constraints are conjunctions of inclusions between expressions...

Finding a maximum matching in a sparse random graph in O(n) expected time
Prasad Chebolu, Alan Frieze, P'all Melsted
Article No.: 24
DOI: 10.1145/1734213.1734218

We present a linear expected time algorithm for finding maximum cardinality matchings in sparse random graphs. This is optimal and improves on previous results by a logarithmic factor.

Routing betweenness centrality
Shlomi Dolev, Yuval Elovici, Rami Puzis
Article No.: 25
DOI: 10.1145/1734213.1734219

Betweenness-Centrality measure is often used in social and computer communication networks to estimate the potential monitoring and control capabilities a vertex may have on data flowing in the network. In this article, we define the Routing...

An axiomatic approach to personalized ranking systems
Alon Altman, Moshe Tennenholtz
Article No.: 26
DOI: 10.1145/1734213.1734220

Personalized ranking systems and trust systems are an essential tool for collaboration in a multi-agent environment. In these systems, trust relations between many agents are aggregated to produce a personalized trust rating of the agents. In this...