Manor Mendel

  1. A note on dichotomies for metric transforms.

    Authors: Manor Mendel, Assaf Naor
    Subjects: Metric Geometry
    Abstract

    We show that for every nondecreasing concave function w:R+ --> R+ with
    w(0)=0, either every finite metric space embeds with distortion arbitrarily
    close to 1 into a metric space of the form (X,w o d) for some metric d on X, or
    there exists a=a(w)>0 and n_0=n_0(w)\in N such that for all n>n_0, any
    embedding of {0,...,n} into a metric space of the form (X,w o d) incurs
    distortion at least n^a.

  2. Improved bounds in the metric cotype inequality for Banach spaces.

    Authors: Manor Mendel, Assaf Naor, Ohad Giladi
    Subjects: Functional Analysis
    Abstract

    It is shown that if (X, ||.||_X) is a Banach space with Rademacher cotype q
    then for every integer n there exists an even integer m< n^{1+1/q}$ such that
    for every f:Z_m^n --> X we have \sum_{j=1}^n \Avg_x [ ||f(x+ (m/2) e_j)-f(x)
    ||_X^q ] < C m^q \Avg_{\e,x} [ ||f(x+\e)-f(x) ||_X^q ], where the expectations
    are with respect to uniformly chosen x\in Z_m^n and \e\in \{-1,0,1\}^n, and all
    the implied constants may depend only on q and the Rademacher cotype q constant
    of X.

  3. Towards a Calculus for Non-Linear Spectral Gaps [Extended Abstract].

    Authors: Manor Mendel, Assaf Naor
    Subjects: Metric Geometry
    Abstract

    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} d_X(f(x),g(y))^2\le \frac{\gamma_+}{|E|}
    \sum_{xy\in E} d_X(f(x),g(y))^2.

  4. Towards a Calculus for Non-Linear Spectral Gaps [Extended Abstract].

    Authors: Manor Mendel, Assaf Naor
    Subjects: Metric Geometry
    Abstract

    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} d_X(f(x),g(y))^2\le \frac{\gamma_+}{|E|}
    \sum_{xy\in E} d_X(f(x),g(y))^2.

  5. Fast C-K-R Partitions of Sparse Graphs.

    Authors: Manor Mendel, Chaya Schwob
    Subjects: Data Structures and Algorithms
    Abstract

    We present fast algorithms for constructing probabilistic embeddings and
    approximate distance oracles in sparse graphs. The main ingredient is a fast
    algorithm for sampling the probabilistic partitions of Calinescu, Karloff, and
    Rabani in sparse graphs.

Syndicate content