Adriana Karagiozova will present her preFPO on Thursday January 25 at 3PM in Room 402. The members of her committee are Moses Charikar, advisor; Bernard Chazelle, Bob Tarjan, readers; Boaz Barak, Bob Sedgewick, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. -------------------------------------- Aspects of Network Design and Metric Space Embeddings In this talk I will present results on several problems in network design and metric space embeddings: 1) Multicommodity buy-at-bulk network design We seek to design a cheap network that satisfies the demands between the terminals of multiple source-sink pairs, where the edge costs experience economies of scale. We give the first non-trivial approximation algorithm for the general case of the problem. 2) Terminal Backup Given a graph with terminals, non-terminals and edge costs we want to find a forest that connects each terminal to at least one other terminal. We give a simple polynomial time algorithm that finds the cheapest such forest. In the process we show that a version of 3D matching, useful for tasks that involve splitting into groups of at least two members, is solvable in polynomial time. 3) Metric Ramsey phenomena A Ramsey theorem on metric spaces asks if given an arbitrary metric space, what is the size of the largest subspace that embeds into $\ell_p$ with distortion at most some target $\alpha$. Previous work shows a phase transition at $\alpha = 2$ for $p > 2$. We show that such a phase transition occurs at $\alpha = 2$ for all $p \geq 1$. 4) Embedding series-parallel graphs into $\ell_1$ We give an embedding of any n-point series-parallel metrics into $\ell_1$ with distortion O(\sqrt{\log n / \log s}), where every coordinate of the embedding is s-Lipschitz. Using this embedding we obtain various other results, among which is matching the dimension-reduction lower bound of Brinkman and Charikar.