Source author record

Mohammad Moharrami

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.MG Discrete Mathematics Data Structures and Algorithms math.CO

Catalog footprint

Research overview

5works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

A lower bound on dimension reduction for trees in \ell_1

There is a constant c > 0 such that for every $ε\in (0,1)$ and $n \geq 1/ε^2$ , the following holds. Any mapping from the $n$ -point star metric into $\ell_1^d$ with bi-Lipschitz distortion $1+ε$ requires dimension $d \geq {c\log n\over ε^2\log (1/ε)}.$

preprint2012arXiv

A node-capacitated Okamura-Seymour theorem

The classical Okamura-Seymour theorem states that for an edge-capacitated, multi-commodity flow instance in which all terminals lie on a single face of a planar graph, there exists a feasible concurrent flow if and only if the cut conditions are satisfied. Simple examples show that a similar theorem is impossible in the node-capacitated setting. Nevertheless, we prove that an approximate flow/cut theorem does hold: For some universal c > 0, if the node cut conditions are satisfied, then one can simultaneously route a c-fraction of all the demands. This answers an open question of Chekuri and Kawarabayashi. More generally, we show that this holds in the setting of multi-commodity polymatroid networks introduced by Chekuri, et. al. Our approach employs a new type of random metric embedding in order to round the convex programs corresponding to these more general flow problems.

preprint2012arXiv

On the Hausdorff dimension of ultrametric subsets in R^n

For every e>0, any subset of R^n with Hausdorff dimension larger than (1-e)n must have ultrametric distortion larger than 1/(4e).

preprint2011arXiv

Dimension reduction for finite trees in L_1

We show that every n-point tree metric admits a (1+eps)-embedding into a C(eps) log n-dimensional L_1 space, for every eps > 0, where C(eps) = O((1/eps)^4 log(1/eps)). This matches the natural volume lower bound up to a factor depending only on eps. Previously, it was unknown whether even complete binary trees on n nodes could be embedded in O(log n) dimensions with O(1) distortion. For complete d-ary trees, our construction achieves C(eps) = O(1/eps^2).

preprint2011arXiv

On the optimality of gluing over scales

We show that for every $α> 0$ , there exist $n$ -point metric spaces (X,d) where every "scale" admits a Euclidean embedding with distortion at most $α$ , but the whole space requires distortion at least $Ω(\sqrt{α\log n})$ . This shows that the scale-gluing lemma [Lee, SODA 2005] is tight, and disproves a conjecture stated there. This matching upper bound was known to be tight at both endpoints, i.e. when $α= Θ(1)$ and $α= Θ(\log n)$ , but nowhere in between. More specifically, we exhibit $n$ -point spaces with doubling constant $λ$ requiring Euclidean distortion $Ω(\sqrt{\log λ\log n})$ , which also shows that the technique of "measured descent" [Krauthgamer, et. al., Geometric and Functional Analysis] is optimal. We extend this to obtain a similar tight result for $L_p$ spaces with $p > 1$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.