Dear 254 folks: you can use this message board to discuss embedding-related issues.

Here is a proof for a lemma about the doubling constant of k-combs that was omitted from Gupta, Krauthgamer and Lee's paper "Bounded Geometries, Fractals, and Low-distortion Embeddings" and wouldn't fit in my presentation.

http://morrison.ucsd.edu/~bmcfee/notes-bounded.pdf

The result Brian presented is for metrics which (1) have a small doubling
constant and (2) are trees. The intersection of these two groups seems
very small indeed! If any of you can come up with an example of such a
metric that is substantially different from a straight line, I'd be very
interested to see it. (eg. Consider a tree which is a union of k paths;
how does the doubling constant depend on k, roughly?)

It seems like the complete binary tree with edge weights decaying exponentially (say halving) at each level should have a bounded doubling constant (lambda = 3?).

The union of k paths is difficult to analyze unless you have some bound on the diameter of the tree, or at least a minimum length for each path, hence the gamma-bad k-comb definition.

Edited by author 03-01-2007 11:30 PM
PLANAR GRAPH PARTITIONS: (Rao et al.)

I was wondering why _three_ BFS are needed in order to obtain delta-partition of a given planar graph. Apparently, plane can be split into cells of size delta x delta by only two types of lines: horizontal and vertical (they correspond in some sense to two BFS over our plane). Then why two BFS don't suffice for planar graphs?

Now it seems to me that two BFS _do_ suffice to delta-partition any planar graph. A reason for that is that from the inner BFS we can get K3,2 (not only K3,1), then we can extend it to K3,3 using the outer BFS.

Any opinions as to whether this is correct?

Konstantin,

I have a question about your "splitting the plane into cells":
Are you assuming there is an obvious embedding from the planar graph metric into the euclidean plane first? When you talk of cells of size "delta x delta" I understand that you have the points of the original metric somehow laid out on a rectangular grid, then partition the points into squares on that grid. But you don't mean to look at the diameter of components of that partition in the original "shortest path" metric. Is that a correct understanding?

Fjola,

I didn't mean any embedding of planar graphs into planes.

Simply, the "fact" that plane can be partitioned using only two BFS suggests that the same can be done for planar graphs.

The techniques you presented seem to suffice for this.

Embedding l2 into l1

It seems that random projections should yield constant distortion embeddings from l2 into l1. As a crude estimate, if x is a unit vector in l2^D and A is a d-by-D matrix of Gaussian random variables, then in expectation, Ax/d has norm about 0.8. Large deviation bounds or concentration of measure (and d=O(log n)) can then do the rest as in the JL lemma.

Does this seem plausible? Using Dvorestsky's theorem would probably be of the same flavor, but might give a lower-dimension embedding.

Hi class,
just wanted to mention that Lawrence was correct in pointing out that the distortion for embedding NEG metrics into L2 achieved in Lee's paper was
log n ^{3/4}, not log n ^{4/3}, which would've been inferior to the Bourgain embedding.

Also, remember--the proof technique we focused on, based on finding large well-separated sets in NEG metrics, only leads to an embedding preserving a single distance scale [tau, 2tau]. To get a low-distortion embedding one has to follow up with the technical machinery of the Gluing Lemma, which wasn't covered.