Harmonic maps on amenable groups and a diffusive lower bound for random walks (2009)
We prove that on any infinite, connected, locally finite, transitive graph G, the probability of the random walk being within $\eps \sqrt{t}$ of the origin after t steps is at most $O(\eps)$. A...
Pathwidth, trees, and random embeddings (2009)
Lee, James R., Sidiropoulos, Anastasios
We prove that, for every $k=1,2,...,$ every shortest-path metric on a graph of pathwidth $k$ embeds into a distribution over random trees with distortion at most $c$ for some $c=c(k)$. A well-known...
On the optimality of gluing over scales (2009)
Jaffe, Alexander, Lee, James R., Moharrami, Mohammad
We show that for every $\alpha > 0$, there exist $n$-point metric spaces (X,d) where every "scale" admits a Euclidean embedding with distortion at most $\alpha$, but the whole space requires...
Anupam Gupta, Robert Krauthgamer, James R. Lee
fractals, and low-distortion embeddings
Anupam Gupta, Robert Krauthgamer, James R. Lee
fractals, and low-distortion embeddings
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows (2008)
Biswal, Punyashloka, Lee, James R., Rao, Satish
We present a new method for upper bounding the second eigenvalue of the Laplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric...
Eigenvectors of random graphs: Nodal domains (2008)
Dekel, Yael, Lee, James R., Linial, Nathan
We initiate a systematic study of eigenvectors of random graphs. Whereas much is known about eigenvalues of graphs and how they reflect properties of the underlying graph, relatively little is known...
Eigenvalue multiplicity and volume growth (2008)
Lee, James R., Makarychev, Yury
Let $G$ be a finite group with symmetric generating set $S$, and let $c = \max_{R > 0} |B(2R)|/|B(R)|$ be the doubling constant of the corresponding Cayley graph, where $B(R)$ denotes an $R$-ball in...
Coarse differentiation and multi-flows in planar graphs (2008)
Lee, James R., Raghavendra, Prasad
We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound Chakrabarti, Jaffe, Lee, and Vincent for this class, and resolving...
Guy Kortsarz, Robert Krauthgamer, James R. Lee
In the survivable network design problem (SNDP), the goal is to nd a minimum-cost spanning subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in...
such that G occurs as a (not necessarily induced) subgraph (2007)
Robert Krauthgamer, James R. Lee, Of Z
We resolve the following conjecture raised by Levin together
James R. Lee, Assaf Naor, An Immediate
We show that any embedding of the level k diamond graph of Newman and Rabinovich [4] into L p, 1
We study the metric properties of finite subsets of L1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs, including...
Almost Euclidean subspaces of \ell_1^N via expander codes (2007)
Guruswami, Venkatesan, Lee, James R., Razborov, Alexander
We give an explicit (in particular, deterministic polynomial time) construction of subspaces X of R^N of dimension (1-o(1))N such that for every element x in X, |x|_1 and N^{1/2} |x|_2 are equivalent...
Trees and Markov convexity (2007)
Lee, James R., Naor, Assaf, Peres, Yuval
We show that an infinite weighted tree admits a bi-Lipschitz embedding into Hilbert space if and only if it does not contain arbitrarily large complete binary trees with uniformly bounded distortion....
The Embedding Distortion Bounds from Coloring Finding the Coloring (2007)
Low-distortion Embeddings, Anupam Gupta, Robert Krauthgamer, James R. Lee
◮ Given a tree metric, we’ll use path partitions to embed the vertices into ℓp for 1 ≤ p ≤ ∞. ◮ We’ll bound the distortion of the embedding in terms of the doubling constant...
In [Rao, SoCG 1999], it is shown that every n-point Euclidean metric with polynomial spread admits a Euclidean embedding with k-dimensional distortion bounded by O ( √ log n log k), a result which...
Euclidean distortion and the Sparsest Cut (2005)
Arora, Sanjeev, Lee, James R., Naor, Assaf
We prove that every $n$-point metric space of negative type (and, in particular, every $n$-point subset of $L_1$) embeds into a Euclidean space with distortion $O(\sqrt{\log n} \cdot\log \log n)$, a...
Euclidean distortion and the Sparsest Cut (2005)
Sanjeev Arora, James R. Lee, Assaf Naor
Bi-Lipschitz embeddings of finite metric spaces, a topic originally studied in geometric analysis and Banach space theory, became an integral part of theoretical computer science following work of...
Euclidean distortion and the Sparsest Cut (2005)
Sanjeev Arora, James R. Lee, Assaf Naor
We prove that every n-point metric space of negative type (and, in particular, every npoint subset of L1) embeds into a Euclidean space with distortion O ( √ log n · log log n), a result which is...
Distance scales, embeddings, and metrics of negative type (2005)
We introduce a new number of new techniques for the construction of low-distortion embeddings of a finite metric space. These include a generic Gluing Lemma which avoids the overhead typically...
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...
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,...
The black-box complexity of nearest neighbor search (2004)
Robert Krauthgamer, James R. Lee
We define a natural notion of efficiency for approximate nearest-neighbor (ANN) search in general n-point metric spaces, namely the existence of a randomized algorithm which answers (1 +...
Navigating nets: Simple algorithms for proximity search (Extended Abstract) (2004)
Robert Krauthgamer, James R. Lee
Robert Krauthgamer # James R. Lee + Abstract We present a simple deterministic data structure for maintaining a set S of points in a general metric space, while supporting proximity search (nearest...
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...
The black-box complexity of nearest neighbor search (2004)
Robert Krauthgamer, James R. Lee
We define a natural notion of efficiency for approximate nearest-neighbor (ANN) search in general n-point metric spaces, namely the existence of a randomized algorithm which answers (1 +...
The black-box complexity of nearest neighbor search (2004)
Robert Krauthgamer, James R. Lee
Abstract. We define a natural notion of efficiency for approximate nearest-neighbor (ANN) search in general n-point metric spaces, namely the existence of a randomized algorithm which answers...
The Black-Box Complexity of Nearest Neighbor Search (2004)
Robert Krauthgamer, James R. Lee, U. C. Berkeley
We define a natural notion of e#ciency for approximate nearest-neighbor (ANN) search in general n-point metric spaces, namely the existence of a randomized algorithm which answers (1+#)-approximate...
The intrinsic dimensionality of graphs (2003)
Robert Krauthgamer, James R. Lee
We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [Combinatorica, 1995]. For a graph G, let dim(G) be the smallest d such that G occurs as a (not...
Bounded geometries, fractals, and low-distortion embeddings (2003)
Anupam Gupta, Robert Krauthgamer, James R. Lee
The doubling constant of a metric space (X, d) is the smallest value # such that every ball in X can be covered by # balls of half the radius. The doubling dimension of X is then defined as dim(X) =...
Hardness of Approximation for Vertex-Connectivity Network Design Problems (2003)
Guy Kortsarz, Robert Krauthgamer, James R. Lee, Unless Np
In the survivable network design problem (SNDP), the goal is to find a minimum-cost spanning subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in...
Extending Lipschitz functions via random metric partitions (2003)
James Lee Berkeley, James R. Lee, Assaf Naor
this paper to the higher order Whitney extension problem
Bounded geometries, fractals, and low-distortion embeddings (2003)
Anupam Gupta, Robert Krauthgamer, James R. Lee
Abstract The doubling constant of a metric space (X, d) is thesmallest value * such that every ball in X can be covered by * balls of half the radius. The doubling dimension of X isthen defined as...
The intrinsic dimensionality of graphs (2003)
Robert Krauthgamer, James R. Lee
We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [Combinatorica, 1995]. For a graph G, let dim(G) be the smallest d such that G occurs as a (not...
The intrinsic dimensionality of graphs (2003)
Robert Krauthgamer, James R. Lee
Abstract We resolve the following conjecture raised by Levin together with Linial, London, and Ra-binovich [Combinatorica, 1995]. For a graph G, let dim(G) be the smallest d such that G occursas a...
Hardness of approximation for vertex-connectivity network-design problems (2002)
Guy Kortsarz, Robert Krauthgamer, James R. Lee
In the survivable network design problem (SNDP), the goal is to find a minimum-cost subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in which...
Hardness of approximation for vertex-connectivity network-design problems (2002)
Guy Kortsarz, Robert Krauthgamer, James R. Lee
In the survivable network design problem (SNDP), the goal is to find a minimum-cost spanning subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in...
We show that any embedding of the level k diamond graph of Newman and Rabinovich [6] into Lp, 1 < p ≤ 2, requires distortion at least � k(p − 1) + 1. An immediate corollary is that there...
Typescript.
Typescript.