Markov Convexity and Local Rigidity of Distorted Metrics [Extended Abstract] ∗ (2009)
The geometry of discrete tree metrics is studied from the following perspectives: (1) Markov p-convexity, which was shown by Lee, Naor, and Peres to be a property of p-convex Banach space, is shown...
Towards a Calculus for Non-Linear Spectral Gaps [Extended Abstract] (2009)
Given a finite regular graph G=(V,E) and a metric space (X,d_X), let $gamma_+(G,X) denote the smallest constant $\gamma_+>0$ such that for all f,g:V\to X we have: \frac{1}{|V|^2}\sum_{x,y\in V}...
C-K-R Partitions of Sparse Graphs (2008)
We present fast algorithms for constructing probabilistic embeddings and approximate distance oracles in sparse graphs. The main ingredient is an algorithm for sampling the probabilistic partitions...
We introduce the notion of the scaled Enflo type of a metric space, and show that for Banach spaces, scaled Enflo type p is equivalent to Rademacher type p. 1.
Markov Convexity and Local Rigidity of Distorted Metrics (2008)
The geometry of discrete tree metrics is studied from the following perspectives: 1. Markov p-convexity, which was shown by Lee, Naor, and Peres to be a property of p-convex Banach space, is shown...
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
In this note, we consider the metric Ramsey problem for the normed spaces # p. Namely, given some 1
These are notes from talks given at ICMS, Edinburgh, 4/2007 (``Geometry and Algorithms workshop") and at Bernoulli Center, Lausanne 5/2007 (``Limits of graphs in group theory and computer science")....
Scaled Enflo type is equivalent to Rademacher type (2007)
We introduce the notion of the scaled Enflo type of a metric space, and show that for Banach spaces, scaled Enflo type p is equivalent to Rademacher type p.
Talks ’ Subjects for Seminar 22952 2007/B (2007)
Zeev Nutov, Manor Mendel, Tamir Tassa, Michael Langberg
This seminar aims to create a research forum on algorithms and theory in Computer Science and to train students to understand scientific papers, to extract topics and research questions from what...
Annals of Mathematics, 162 (2005), 643–710 On metric Ramsey-type phenomena (2007)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky’s theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric...
Maximum gradient embeddings and monotone clustering (2006)
Let (X,d_X) be an n-point metric space. We show that there exists a distribution D over non-contractive embeddings into trees f:X-->T such that for every x in X, the expectation with respect to D of...
Truly Online Paging with Locality of Reference (2006)
The competitive analysis fails to model locality of reference in the online paging problem. To deal with it, Borodin et. al. introduced the access graph model, which attempts to capture the locality...
Talks ’ Subjects for Seminar 22952 2007/A (2006)
Zeev Nutov, Manor Mendel, Tamir Tassa, Michael Langberg
This seminar aims to create a research forum on algorithms and theory in Computer Science and to train students to understand scientific papers, to extract topics and research questions from what...
Ramsey partitions and proximity data structures (2005)
This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate...
On metric Ramsey-type phenomena (2005)
Bartal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky's theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric space...
Scaled Enflo type is equivalent to Rademacher type (2005)
We introduce the notion of scaled Enflo type of a metric space, and show that for Banach spaces, scaled Enflo type p is equivalent to Rademacher type p.
We introduce the notion of cotype of a metric space, and prove that for Banach spaces it coincides with the classical notion of Rademacher cotype. This yields a concrete version of Ribe's theorem,...
On metric Ramsey-type phenomena (2005)
Mendel, Manor, Naor, Assaf, Linial, Nathan, Bartal, Yair
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky¿s theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric...
Randomized k-server algorithms for growth-rate bounded graphs (2005)
Abstract The k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total...
Fast construction of nets in low dimensional metrics, and their applications (2005)
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 improved algorithms...
We introduce the notion of metric cotype, a property of metric spaces related to a property of normed spaces, called Rademacher cotype. Apart from settling a long standing open problem in metric...
We introduce the notion of cotype of a metric space, and prove that for Banach spaces it coincides with the classical notion of Rademacher cotype. This yields a concrete version of Ribe’s theorem,...
Measured descent: A new embedding method for finite metrics (2004)
Krauthgamer, Robert, Lee, James R., Mendel, Manor, Naor, Assaf
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 measure. This...
Fast Construction of Nets in Low Dimensional Metrics, and Their Applications (2004)
Har-Peled, Sariel, Mendel, Manor
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 improved algorithms...
Multi-Embedding of Metric Spaces (2004)
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 finite metric space...
Metric structures in L_1: Dimension, snowflakes, and average distortion (2004)
Lee, James R., Mendel, Manor, Naor, Assaf
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 weighted graphs,...
Limitations to Frechet's Metric Embedding Method (2004)
Batal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embedding. The authors...
Online Companion Caching (2004)
Mendel, Manor, Seiden, Steven S.
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-associative cache...
On Metric Ramsey-type Dichotomies (2004)
Bartal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
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 finite metric...
Better algorithms for unfair metrical task systems and applications (2004)
Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these...
Randomized k-server algorithms for growth-rate bounded graphs (2004)
The paper referred to in the title is withdrawn.
Euclidean quotients of finite metric spaces (2004)
This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M, what is the largest quotient of (a subset of) M which...
On metric Ramsey-type phenomena (2004)
Bartal, Yair, Linial, Nathan, Mendel, Manor, Naor, Assaf
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky's theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric space...
Ramsey-type theorems for metric spaces with applications to online problems (2004)
Bartal, Yair, Bollobas, Bela, Mendel, Manor
A nearly logarithmic lower bound on the randomized competitive ratio for the metrical task systems problem is presented. This implies a similar lower bound for the extensively studied k-server...
Dimension reduction for ultrametrics (2004)
Abstract We prove that an ultrametric on n points can be embedded in `dp with distortion at most 1 + ", and d = O("-2 log n). This bound matches the best known bound for the special...
Measured descent: A new embedding method for finite metrics (2004)
Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
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 measure.
Measured descent: A new embedding method for finite metrics (2004)
Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
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 measure. This...
Measured descent: A new embedding method for finite metrics (2004)
Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
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 measure. This...
Limitations to Fréchet metric embedding method (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Abstract Fr'echet's classical isometric embedding argument has evolved to become a major toolin the study of metric spaces. An important example of a Fr'echet embedding is...
On metric Ramsey-type phenomena (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The main question studied in this article may be viewed as a non-linear analogue of Dvoretzky’s Theorem in Banach space theory or as part of Ramsey Theory in combinatorics. Given a finite metric...
Multi-embeddings and path-approximation of metric spaces (2003)
Metric embeddings have become a frequent tool in the design of algorithms. The applicability is often dependent on how high the embedding's distortion is. For example embedding into ultrametrics...
Euclidean Quotients of Finite Metric Spaces (2003)
Manor Mendel School, Manor Mendel, Assaf Naor
This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M and # 1, what is the largest quotient of (a subset of) M...
On metric Ramsey-type phenomena (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky’s theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric...
Limitations to Fréchet's Metric Embedding Method (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embedding [4]....
On Metric Ramsey-type Dichotomies (2002)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
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 finite metric...
On Metric Ramsey-type Dichotomies (2002)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
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 finite metric...
Online companion caching (2002)
Amos Fiat, Manor Mendel, Steven S. Seiden
Steve Seiden died in a tragic accident on June 11, 2002. The other authors would like to dedicate this paper to his memory. Abstract. This paper is concerned with online cachingalgorithms for the (n,...
This paper gives a nearly logarithmic lower bound on the randomized competitive ratio for the Metrical Task Systems model [BLS92]. This implies a similar lower bound for the extensively studied...
Refined Locality of Reference for Paging (1998)
In this paper we refine the locality of reference concept captured by the access graph model to allow temporal changes in the behavior of the underlying process. We formalize this by introducing the...
Truly Online Paging with Locality of Reference (1997)
The competitive analysis fails to model locality of reference in the online paging problem. To deal with it, Borodin et. al. introduced the access graph model for the paging problem, which attempts...
this article we review articles that attempt to solve the following problem: "Given a dynamic changing undirected graph and two vertices in the graph, are the two vertices biconnected? 2-edge...