Algorithms in varied fields use the idea of maintaining a distribution over a certain set and
use the multiplicative update rule to iteratively change these weights. Their analyses are …

In this paper, we show that any n point metric space can be embedded into a distribution
over dominating tree metrics such that the expected stretch of any edge is O (log n). This …

We give a O (√ log n)-approximation algorithm for the sparsest cut, edge expansion,
balanced separator, and graph conductance problems. This improves the O (log n) …

Our goal in this paper is to show that many of the tools of signal processing, adapted Fourier
and wavelet analysis can be naturally lifted to the setting of digital data clouds, graphs, and …

Random projection is a simple geometric technique for reducing the dimensionality of a set
of points in Euclidean space while preserving pairwise distances approximately. The …

We develop the algorithmic theory of vertex separators, and its relation to the embeddings of
certain metric spaces. Unlike in the edge case, we show that embeddings into L1 (and even …

This paper introduces a lightweight, scalable and accurate framework, called Meridian, for
performing node selection based on network location. The framework consists of an overlay …

An n-point metric space (X, D) can be represented by an n× n $ n\times n $ https://s3-euw1-
ap-pe-df-pch-content-public-p. s3. eu-west-1. amazonaws. com/9781315119601/fb8178cb …

We prove that every n-point metric space of negative type (in particular, every n-point subset
of L1) embeds into a Euclidean space with distortion O (√ log n log log n), a result which is …

Metric Embedding plays an important role in a vast range of application areas such as
computer vision, computational biology, machine learning, networking, statistics, and …