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 …

In this paper, we show that for several clustering problems one can extract a small set of
points, so that using those core-sets enable us to perform approximate clustering efficiently …

The edit distance between two strings S and R is defined to be the minimum number of
character inserts, deletes, and changes needed to convert R to S. Given a text string t of …

Given a set of points P⊂ Rd and value ε> 0, an ε-core-setS⊂ P has the property that the
smallest ball containing S has radius within 1+ ε of the radius of the smallest ball containing …

We prove the existence of small core-sets for solving approximate k-center clustering and
related problems. The size of these core-sets is considerably smaller than the previously …

We design top trees as a new simpler interface for data structures maintaining information in
a fully dynamic forest. We demonstrate how easy and versatile they are to use on a host of …

We study the minimum enclosing ball (MEB) problem for sets of points or balls in high
dimensions. Using techniques of second-order cone programming and" core-sets", we have …

We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying
assignment x∈{0, 1} n to a CNF formula φ is shared between two parties, where Alice …

We develop a simple combinatorial algorithm for computing the smallest enclosing ball of a
set of points in high dimensional Euclidean space. The resulting code is in most cases faster …

Abstract We study (1+ e)-factor approximation algorithms for several well-known
optimization problems on a given npoint set:(a) diameter,(b) width,(c) smallest enclosing …