We study streaming algorithms for the fundamental geometric problem of computing the cost
of the Euclidean Minimum Spanning Tree (MST) on an n-point set X⊂ ℝ d. In the streaming …

A partition of a weighted graph is-sparse if every cluster has diameter at most, and every ball
of radius intersects at most clusters. Similarly, is-scattering if instead for balls, we require that …

A spanning tree T of graph G is a ρ-approximate universal Steiner tree (UST) for root vertex r
if, for any subset of vertices S containing r, the cost of the minimal subgraph of T connecting …

We give new data-dependent locality sensitive hashing schemes (LSH) for the Earth Mover's
Distance (EMD), and as a result, improve the best approximation for nearest neighbor …

Max-Cut is a fundamental problem that has been studied extensively in various settings. We
design an algorithm for Euclidean Max-Cut, where the input is a set of points in ℝ d, in the …

We design new algorithms for $ k $-clustering in high-dimensional Euclidean spaces. These
algorithms run in the Massively Parallel Computation (MPC) model, and are fully scalable …

The Johnson-Lindenstrauss (JL) Lemma introduced the concept of dimension reduction via
a random linear map, which has become a fundamental technique in many computational …

We consider a generalization of the Steiner tree problem, the Steiner forest problem, in the
Euclidean plane: the input is a multiset, partitioned into color classes. The goal is to find a …

Hashmap is a fundamental data structure in computer science. There has been extensive
research on constructing hashmaps that minimize the number of collisions leading to …

We study streaming algorithms for the fundamental geometric problem of computing the cost
of the Euclidean Minimum Spanning Tree (MST) on an $ n $-point set $ X\subset\mathbb …