[talks] S Li general exam

[Melissa Lawson]

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