enter search term and/or author name
Stable distributions, pseudorandom generators, embeddings, and data stream computation
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
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
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
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
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
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
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
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...