5
$\begingroup$

I am quite new to the area of metric embeddings so this question might turn out to be extremely easy.

Consider a metric supported on the edges of a boolean hypercube. By supported I mean every edge of the boolean hypercube has a non negative distance associated with it and the metric is defined by the length of the shortest path according to the distance function between any two vertices. Can we put upper bounds/lower bounds on the distortion when we embed such a metric into $l_1$ ?

Any references would be highly appreciated.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

Think of the hypercube as a graph $G$. Allowing arbitrary edge lengths implies that you can use edge lengths $0$ and $\infty$ to get a minor of $G$ on which you can put edge lengths. The hypercube has sufficiently large expansion that it contains, as a minor, a clique of size about $\sqrt{N}$ (ignoring polylog factors) where $N$ is the number of nodes of the hypercube. This implies you can basically have any finite metric on a set of size about $\sqrt{N}$ supported on the hyper cube. Thus the worst-case lower bounds will apply so you will get an $\Omega(\log N)$ lower bound.

Improve this answer
$\endgroup$
0
4
$\begingroup$

In general there are all kinds of lower bounds for embedding an arbitrary metric on the hypercube into $\ell_1$. For example, the edit distance cannot be embedded with better than $\log n$ distortion. Note that the Hamming distance itself embeds isometrically in $\ell_1$, so you can't expect to prove any nontrivial lower bound over all metrics on the hypercube.

p.s I don't think the boolean-ness matters at all.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for the answer. The paper that you suggested does give lower bounds on the edit distance metric (I have not read the paper but just read the result). However I dont think edit distance can be 'supported' on the edges of the hypercube. I have also found(but not read) some other examples of lower bounds on sparsest cut involving quotients of the hypercube but none purely supported on the edge set of the hypercube. $\endgroup$
    – NAg
    Apr 9, 2014 at 21:43
  • $\begingroup$ Maybe you should clarify what "supported" means then. If it means "assigning weights to edges and taking shortest paths", then it is supported. $\endgroup$
    – Suresh Venkat
    Apr 10, 2014 at 0:53
  • $\begingroup$ I am sorry but I couldnt get your above comment. So when I say edges I mean the standard edges of the Hypercube, the ones that go between pairs of vertices that are at Hamming Distance 1. Now if we want to 'support' the edit distance then for any pair that is at Hamming Distance 1 since the edit distance is also 1. the edge between them will have to be given a weight $\geq 1$. Now all edges have weight $\geq 1$ therefore distance between any pair has to be greater than the Hamming distance and hence Edit distance cannot be supported. Could you please point out the flaw in my reasoning? $\endgroup$
    – NAg
    Apr 10, 2014 at 14:13
  • $\begingroup$ "distance between any pair has to be greater than the Hamming distance". I guess this is moot because of Chandra's answer, but in his answer he's setting edges to weight 0 to get a minor: this seems to contradict your statement. $\endgroup$
    – Suresh Venkat
    Apr 10, 2014 at 17:12
  • $\begingroup$ I am sorry when I made the previous comment I didnt realize that you were saying that we can support an edit distance metric on $\sim \sqrt{N}$ vertices(as Chandra clarified) on the a cube of $n$ vertices, i thought you had suggested supporting an edit distance on $n$ points. That was naive of me. Thanks for the answers $\endgroup$
    – NAg
    Apr 10, 2014 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.