enter search term and/or author name
Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors
B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, A. Wigderson
Article No.: 20
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
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
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 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
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.
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
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...