272 citations · 652 across the 10 of their papers we have counts for
10 papers
Measured descent: A new embedding method for finite metrics
Robert Krauthgamer, James R. Lee, Manor Mendel +1
We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability me…
Fast Construction of Nets in Low Dimensional Metrics, and Their Applications
Sariel Har-Peled, Manor Mendel
We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain i…
Multi-Embedding of Metric Spaces
Yair Bartal, Manor Mendel
Metric embedding has become a common technique in the design of algorithms. Its applicability is often dependent on how high the embedding's distortion is. For example, embedding f…
Metric structures in L_1: Dimension, snowflakes, and average distortion
James R. Lee, Manor Mendel, Assaf Naor
We study the metric properties of finite subsets of L_1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weight…
On Metric Ramsey-type Dichotomies
Yair Bartal, Nathan Linial, Manor Mendel +1
The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of…
Online Companion Caching
Manor Mendel, Steven S. Seiden
This paper is concerned with online caching algorithms for the (n,k)-companion cache, defined by Brehob et. al. In this model the cache is composed of two components: a k-way set-a…