<p>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. </p>

CC BY-SA 3.0
2014-04-10T15:36:23.380Z
2014-04-10T15:36:23.380Z
Chandra Chekuri
<p>In general there are all kinds of lower bounds for embedding an <em>arbitrary</em> metric on the hypercube into $\ell_1$. For example, the edit distance <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.149.9265" rel="nofollow">cannot be embedded with better than $\log n$ distortion</a>. Note that the Hamming distance itself embeds isometrically in $\ell_1$, so you can't expect to prove any nontrivial lower bound over <em>all</em> metrics on the hypercube.</p>

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

CC BY-SA 3.0
2014-04-09T21:43:17.057Z
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.
NAg
CC BY-SA 3.0
2014-04-10T00:53:30.643Z
Maybe you should clarify what "supported" means then. If it means "assigning weights to edges and taking shortest paths", then it is supported.
Suresh Venkat
CC BY-SA 3.0
2014-04-10T14:13:16.087Z
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?
NAg
CC BY-SA 3.0
2014-04-10T17:12:14.813Z
"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.
Suresh Venkat
CC BY-SA 3.0
2014-04-10T17:42:14.073Z
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
NAg
CC BY-SA 3.0
2014-04-10T18:12:34.613Z
Actually I think Chandra's answer is clearer though :). You should go back to accepting his.
Suresh Venkat
CC BY-SA 3.0
2014-04-09T17:11:33.083Z
2014-04-09T17:11:33.083Z
Suresh Venkat
<p>I am quite new to the area of metric embeddings so this question might turn out to be extremely easy.</p>

<p>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$ ? </p>

<p>Any references would be highly appreciated.</p>

<boolean-functions><metrics><metric-spaces>
L1 - embeddability of metrics supported on the Hypercube
NAg
# L1 - embeddability of metrics supported on the Hypercube

(Asked by: username_0 on 2014-04-09)

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.

**Tags:** boolean-functions, metrics, metric-spaces


---

## 2 answers

### Answer by username_1 on 2014-04-10. Score: 4 | Accepted answer

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.


---

### Answer by username_2 on 2014-04-09. Score: 4

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.149.9265). 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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: Maybe you should clarify what "supported" means then. If it means "assigning weights to edges and taking shortest paths", then it is supported.  
> **username_0**: 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?  
> **username_2**: "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.  
> **username_0**: 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  
> **username_2**: Actually I think Chandra's answer is clearer though :). You should go back to accepting his.  

---

