The Berkeley algorithms reading group, Spring 2002

Time: every Friday at 2pm
Place: 606 Soda There are usually one or more papers that you should at least look over before coming, so that we can have a more effective discussion.

Past semesters' reading group topics: Fall 2001

To subscribe or unsubscribe, click here.

Date Speaker Topic & paper reference

February 1 Robert Krauthgamer The Euclidean distortion of a complete binary tree
Bourgain (Israel J. Math, 1986) showed that this quantity is $\Theta(\log\log n)$ for an $n$-vertex complete binary tree. I will present Bourgain's upper bound (i.e. an embedding) and a simpler, more recent, lower bound due to Linial and Saks (Disc. & Comp. Geom., to appear; see here also).

Februray 8 Chris Harrelson Bourgain Embeddings
In another paper (Israel J. Math, 1985), Bourgain showed that any $n$-point metric can be embedded in any Euclidean space with $O(\log n)$ distortion. I will give a proof of an embedding into $l_\infty$ and $l_{1,2}$. For references, see some scribe notes from CS 271 last semester and chapter 15 (pp. 349-356) of an upcoming book by J. Matousek.

February 15 Steve Chien Lower bounds for hypercubes and expanders
Once again, we will look at parts of chapter 15 from Matousek's book (find it here). Steve will be discussing two things: (1) an $\Omega(\sqrt{\log n})$ distortion lower bound for embedding the ($l_1$) Hamming/hyper cube into $l_2$; (2) an $\Omega(\log n)$ distortion lower bound for embedding an expander into any $l_p$ metric.

February 22 Satish Rao Planar graph decompositions and embeddings
Satish will first talk about a theorem regarding the decomposition of planar graphs that appeared in a paper by Klein, Plotkin and Rao (get it here). If time allows, we'll even hear a bit about Satish's algorithm for embedding planar graphs into $l_2$ with $\sqrt{n}$ distortion (get it here).
(This talk was cancelled...perhaps it will be rescheduled later in the semester.)

March 1 Eran Halperin Bartal trees
I am going to talk about approximating metrics using probabilistic trees, due to Bartal. The relevant papers are: "Probabilistic Approximation of Metric Spaces and its Algorithmic Applications", Yair Bartal. "On Approximating Arbitrary Metrics by Tree Metrics", Yair Bartal. The papers can be found here.

March 8 Jittat Fakcharoenphol Power outage: delayed until next week

March 15 Jittat Fakcharoenphol Embedding outerplanar graphs using the Okamura-Seymour theorem
I will continue the discussion on embedding graphs into distributions of trees. I will show an $O(1)$-distortion embedding of an outerplanar graph into a probabilistic tree metric. This result is not very surprising, since outerplanar graphs can be embedded isometrically into $l_1$ space. This result follows from the Okamura-Seymour theorem on multicommodity flows in planar graphs where all the terminals lie on the same face, which shows that max-flow equals min-cut in such case. In fact, the statement of the theorem is much stronger, i.e., it gives the existance of disjoint paths. I will show the result and prove the Okamura-Seymour theorem.
Th graph embedding result is due to Gupta et al, and is available here.

March 22 No speaker Friday before spring break

March 29 No speaker Spring break

April 5 Satish Rao See abstract for February 22.

April 12 Chris Harrelson Girth and Euclidean distortion
I will discuss the recent result relating the girth of a graph and the best possible Euclidean distortion of that graph. It says that for any $k$-regular graph $G$, $k \ge 3$, with girth $g$, any $l_2$ embedding of $G$ incurs a distortion of $\Omega(\sqrt{g})$.
(reference)

April 19 No speaker

April 26 James Lee Constant distortion $\ell_1$ embeddings.
It has been conjectured that any metric supported on a planar graph can be embedded into $\ell_1$ with constant distortion. Earlier it was shown that outerplanar graphs can be embedded into a distribution over dominating trees with expected constant distortion. I will show that this approach alone cannot be used to resolve the above conjecture by exhibiting a family of series-parallel graphs which require $\Omega(\log n)$ distortion when embedded into any such distribution. I will then present a different approach which gives constant distortion embeddings for series-parallel graphs (may be omitted). These results are from Gupta, et al. and are available here.
Finally, I will show how to achieve constant distortion embeddings for k-outerplanar graphs (again, by embedding them into a distribution over dominating trees). This paper (from the same authors) is here (note: not intended for distribution).

May 3 Kevin Chen Permutation distances
The distance between two permutations is studied in many applied fields, including comp. bio. (the evolutionary distance between two genomes) and informational retrieval (rank aggregation). There are several commonly used metrics defined on the group of permutations on n elements, including:
reversal distance: how many reversals of contiguous segments does it take to transform one permutation into another

Kendall's Tau metric: how many inversions does one permutation have relative to another

Ulam's metric: n - the length of the longest increasing or decreasing subsequence
and others.
I'm going to give a few examples of embeddings of these metrics into more well-known metrics like L_p, which means that algorithms already designed for L_p metrics (e.g. nearest neighbor algorithms) can be directly used for permutation metrics as well.
This talk will feature results culled from Ajtai et al. Approx. counting of inversions in a data stream (STOC 2002), Cormode et al. Permutation Editing and Matching via Embeddings, and Kececioglu & Sankoff Exact and approx. algs. for sorting by reversals, w/ application to genome rearrangement. (Algorithmica 13:1/2, 1995) Papers: Ajtai et al and Cormode et al.

May 17 Andrej Bogdanov Derandomizations of the Johnson-Lindenstrauss lemma
I will focus on a paper by Engebretsen, Indyk and O'Donnell on a derandomized Johnson-Lindenstrauss lemma, which is good for deradomizing approximation algorithms based on semidefinite programs. Their original proof is somewhat tedious, so I will present an alternative "discretized" version of the lemma due to Achlioptas. As motivating applications, we will see derandomized versions of max-cut and graph coloring.

Lars Engebretsen, Piotr Indyk and Ryan O'Donnell. Derandomized dimensionality reduction with applications. 13th Symposium on Discrete Algorithms, 2002. [paper]

Dimitris Achlioptas. Database-friendly random projections. Principles of Database Systems, 2001. [paper]

Date	Speaker	Topic & paper reference
February 1	Robert Krauthgamer	The Euclidean distortion of a complete binary tree Bourgain (Israel J. Math, 1986) showed that this quantity is $\Theta(\log\log n)$ for an $n$-vertex complete binary tree. I will present Bourgain's upper bound (i.e. an embedding) and a simpler, more recent, lower bound due to Linial and Saks (Disc. & Comp. Geom., to appear; see here also).
Februray 8	Chris Harrelson	Bourgain Embeddings In another paper (Israel J. Math, 1985), Bourgain showed that any $n$-point metric can be embedded in any Euclidean space with $O(\log n)$ distortion. I will give a proof of an embedding into $l_\infty$ and $l_{1,2}$. For references, see some scribe notes from CS 271 last semester and chapter 15 (pp. 349-356) of an upcoming book by J. Matousek.
February 15	Steve Chien	Lower bounds for hypercubes and expanders Once again, we will look at parts of chapter 15 from Matousek's book (find it here). Steve will be discussing two things: (1) an $\Omega(\sqrt{\log n})$ distortion lower bound for embedding the ($l_1$) Hamming/hyper cube into $l_2$; (2) an $\Omega(\log n)$ distortion lower bound for embedding an expander into any $l_p$ metric.
February 22	Satish Rao	Planar graph decompositions and embeddings Satish will first talk about a theorem regarding the decomposition of planar graphs that appeared in a paper by Klein, Plotkin and Rao (get it here). If time allows, we'll even hear a bit about Satish's algorithm for embedding planar graphs into $l_2$ with $\sqrt{n}$ distortion (get it here). (This talk was cancelled...perhaps it will be rescheduled later in the semester.)
March 1	Eran Halperin	Bartal trees I am going to talk about approximating metrics using probabilistic trees, due to Bartal. The relevant papers are: "Probabilistic Approximation of Metric Spaces and its Algorithmic Applications", Yair Bartal. "On Approximating Arbitrary Metrics by Tree Metrics", Yair Bartal. The papers can be found here.
March 8	Jittat Fakcharoenphol	Power outage: delayed until next week
March 15	Jittat Fakcharoenphol	Embedding outerplanar graphs using the Okamura-Seymour theorem I will continue the discussion on embedding graphs into distributions of trees. I will show an $O(1)$-distortion embedding of an outerplanar graph into a probabilistic tree metric. This result is not very surprising, since outerplanar graphs can be embedded isometrically into $l_1$ space. This result follows from the Okamura-Seymour theorem on multicommodity flows in planar graphs where all the terminals lie on the same face, which shows that max-flow equals min-cut in such case. In fact, the statement of the theorem is much stronger, i.e., it gives the existance of disjoint paths. I will show the result and prove the Okamura-Seymour theorem. Th graph embedding result is due to Gupta et al, and is available here.
March 22	No speaker	Friday before spring break
March 29	No speaker	Spring break
April 5	Satish Rao	See abstract for February 22.
April 12	Chris Harrelson	Girth and Euclidean distortion I will discuss the recent result relating the girth of a graph and the best possible Euclidean distortion of that graph. It says that for any $k$-regular graph $G$, $k \ge 3$, with girth $g$, any $l_2$ embedding of $G$ incurs a distortion of $\Omega(\sqrt{g})$. (reference)
April 19	No speaker
April 26	James Lee	Constant distortion $\ell_1$ embeddings. It has been conjectured that any metric supported on a planar graph can be embedded into $\ell_1$ with constant distortion. Earlier it was shown that outerplanar graphs can be embedded into a distribution over dominating trees with expected constant distortion. I will show that this approach alone cannot be used to resolve the above conjecture by exhibiting a family of series-parallel graphs which require $\Omega(\log n)$ distortion when embedded into any such distribution. I will then present a different approach which gives constant distortion embeddings for series-parallel graphs (may be omitted). These results are from Gupta, et al. and are available here. Finally, I will show how to achieve constant distortion embeddings for k-outerplanar graphs (again, by embedding them into a distribution over dominating trees). This paper (from the same authors) is here (note: not intended for distribution).
May 3	Kevin Chen	Permutation distances The distance between two permutations is studied in many applied fields, including comp. bio. (the evolutionary distance between two genomes) and informational retrieval (rank aggregation). There are several commonly used metrics defined on the group of permutations on n elements, including: reversal distance: how many reversals of contiguous segments does it take to transform one permutation into another Kendall's Tau metric: how many inversions does one permutation have relative to another Ulam's metric: n - the length of the longest increasing or decreasing subsequence and others. I'm going to give a few examples of embeddings of these metrics into more well-known metrics like L_p, which means that algorithms already designed for L_p metrics (e.g. nearest neighbor algorithms) can be directly used for permutation metrics as well. This talk will feature results culled from Ajtai et al. Approx. counting of inversions in a data stream (STOC 2002), Cormode et al. Permutation Editing and Matching via Embeddings, and Kececioglu & Sankoff Exact and approx. algs. for sorting by reversals, w/ application to genome rearrangement. (Algorithmica 13:1/2, 1995) Papers: Ajtai et al and Cormode et al.
May 17	Andrej Bogdanov	Derandomizations of the Johnson-Lindenstrauss lemma I will focus on a paper by Engebretsen, Indyk and O'Donnell on a derandomized Johnson-Lindenstrauss lemma, which is good for deradomizing approximation algorithms based on semidefinite programs. Their original proof is somewhat tedious, so I will present an alternative "discretized" version of the lemma due to Achlioptas. As motivating applications, we will see derandomized versions of max-cut and graph coloring. Lars Engebretsen, Piotr Indyk and Ryan O'Donnell. Derandomized dimensionality reduction with applications. 13th Symposium on Discrete Algorithms, 2002. [paper] Dimitris Achlioptas. Database-friendly random projections. Principles of Database Systems, 2001. [paper]