Shi Li will present his research seminar/general exam on Wednesday May 19 at 10AM in Room 402. the members of his committee are: Moses Charikar (advisor), Sanjeev Arora, and Bob Tarjan. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ---------------------------------------------------- Title : Vertex Sparsifiers and Abstract Rounding Algorithms The notion of vertex sparsification (in particular cut-sparsification) is introduced by Moitra. It was shown that for any graph $G = (V, E)$ and a subset of $k$ terminals $K \subset V$, there is a polynomial time algorithm to construct a graph $H = (K, E_H)$ on just the terminal set so that simultaneously for all cuts $(A, K-A)$, the value of the minimum cut in $G$ separating $A$ from $K -A$ is approximately the same as the value of the corresponding cut in $H$. Then approximation algorithms can be run directly on $H$ as a proxy for running on $G$, yielding approximation guarantees independent of the size of the graph. In this work, we consider how well cuts in the sparsifier $H$ can approximate the minimum cuts in $G$, and whether algorithms that use such reductions need to incur a multiplicative penalty in the approximation guarantee depending on the quality of the sparsifier. We give a construction for $O(log k/\log \log k)$-quality cut sparsifers, which matches the best existential result. This is done by solving a mixed covering and matching linear programming derived from the 0-sum game used in the existential proof. We give the first super-constant lower bounds for how well a cut-sparsifier $H$ can simultaneously approximate all minimum cuts in $G$. We prove a lower bound of $\Omega(\log^{1/4} k)$ -- this is polynomially-related to the known upper bound of $O(\log k/\log \log k)$. This is an exponential improvement on the $\Omega(\log \log k)$ bound given in \cite{LM} which in fact was for a stronger vertex sparsification guarantee, and did not apply to cut sparsifiers. If we restrict the cut sparsifers to be from a linear combination of 0-extensions, we can show a better lower bound of $\Omega(\sqrt{log k})$. This restriction is quite reasonable since all known constructions, as well as exsitential proofs, are based on 0-extensions. Despite this negative result, we show that for many natural problems, we do not need to incur a multiplicative penalty for our reduction. Roughly speaking, we show that many graph partitioning problems can be reduced to correspodent problems restricted to trees, at the price of $O(\log k)$ in the approximation ratio. For many problems, this saves an $O(\log k/\log\log k)$ multiplicative factor in the approximation ratio, compared to the algorithm where we first sparsify the graph and then solve the problem on the smaller graph. This result helps to explain the intrinsic robustness of graph partitioning problems - i.e. why does $O(\log k)$ always seem to be the right answer for the approximation ratio? Papers : [AFH+ 04] Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Eva Tardos. Approximate classification via earthmover metrics. In SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1079-1087, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics. [CKR01] Gruia Calinescu, Howard Karloff, and Yuval Rabani. Approximation algorithms for the 0-extension problem. In SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 8-16, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics. [FHRT03] Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, and Kunal Talwar. An improved approximation algorithm for the 0-extension problem. In SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 257-265, Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics. [KKL88] J. Kahn, G. Kalai, and N. Linial. The influence of variables on boolean functions. In SFCS '88: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 68-80, Washington, DC, USA, 1988. IEEE Computer Society. [Moi09] Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In FOCS, pages 3-12, 2009. [FRT03] Fakcharoenphol, Jittat, Rao, Satish, and Talwar, Kunal: A tight bound on approximating arbitrary metrics by tree metrics, STOC '03, ACM, 448-455, 2003 [AHK05] Arora, Sanjeev, Hazan, Elad, and Kale, Satyen: The multiplicative weights update method: a meta algorithm and applications, 2005 [You01] Young, Neal E.: Sequential and Parallel Algorithms for Mixed Packing and Covering, In 42nd Annual IEEE Symposium on Foundations of Computer Science, 538-546, 2001 Books : Computational complexity, a modern approach, by Sanjeev Arora and Boaz Barak, 2009. Chapters : 0 ~ 9, 11, 14, 19, 22 Appromixation Algorithms, by Vijay V. Vazirani, 2001 Chapters : 4, 11, 12, 15, 18 ~ 21, 26