Let X be a normed space that satisfies the Johnson-Lindenstrauss lemma (J--L lemma, in short) in the sense that for any integer n and any x₁,...,x_n ε X there exists a linear mapping L: ...

In the kernel clustering problem we are given a large $n\times n$positive semi-definite matrix $A=(a_{ij})$ with$\sum_{i,j=1}^na_{ij}=0$ and a small $k\times k$ positivesemi-definite matrix $B=(b_{ij})$. The goal is to find a partition$S_1,\ldots,S_k$ ...

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 here to be equivalent to p-convexity of Banach spaces.
...
Keywords: bd-ramsey, markov convexity, metric dichotomy, p-convexity, tree metrics, uniform convexity

Let $$ N_{\mathbb{F}} $$ ...

For p ≥ 2 we consider the problem of, given an n × n matrix A = (a_ij) whose diagonal entries vanish, approximating in polynomial time the number {display equation} (where optimization is taken over ...

Given a metric space $(X,d_X)$, $c \ge 1$, $r > 0$, and $p,q \in [0,1]$, a distribution over mappings $\mathscr{H} : X \to \mathbb{N}$ is called a $(r,cr,p,q)$-sensitive hash family if any two points in $X$ at distance at most $r$ are mapped by $\mathscr{H}$ ...

We show that every n-point metric of negative type (in particular, every n-point subset of L ₁) admits a Fréchet embedding into Euclidean space with distortion $O(\sqrt{\log n}\cdot \log \log n)$, a result which ...

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A = \left\{ {aijk} \right\}_{i,j,k = 1}^n such that for all i,j,k \in \left\{ {1, \ldots ,n} \right\} we have a_{ijk}= a_{ikj}= a_{kji}= a_{jik}= a_{kij}= a_{jki} ...

Let (X,d X ) be an n-point metric space. We show that there exists a distribution

In this article we introduce the notion of nearest-neighbor-preserving embeddings. These are randomized embeddings between two metric spaces which preserve the (approximate) nearest-neighbors. We give two examples of such embeddings for Euclidean metrics ...