Zhifeng Sun

Research Interests

Approximation algorithms, algorithmic game theory, and networking.


Network effects of risk behavior change following prophylactic interventions
with V.S. Kumar, R. Rajaraman, and R. Sundaram

On the Complexity of Information Spreading in Dynamic Networks
with C. Dutta, G. Pandurangan, R. Rajaraman, and E. Viola
In proceedings of SODA 2013

Discovery through Gossip
with B. Haeupler, G. Pandurangan, D. Peleg, and R. Rajaraman
In proceedings of SPAA 2012
[conference version] [presentation]

Existence Theorems and Approximation Algorithms for Generalized Network Security Games
with V.S. Kumar, R. Rajaraman, and R. Sundaram
In proceedings of ICDCS 2010
[conference version] [full version] [presentation]

Approximation Algorithms for Key Management in Secure Multicast
with A. Chan, R. Rajaraman, and F. Zhu
In proceedings of COCOON 2009
[conference version] [full version] [presentation]

Some writeups

Survey articles:

A survey on Multicut problem and its variants
A survey on Epidemic problems

Lecture scribes:

Primes is in P
Undirected graph reachability problem
Nash equilibrium and its proof using Fix Point Theorems
Multicommodity flow and Sparsest cut 1
Multicommodity flow and Sparsest cut 2

Feige and Krauthgamer published a paper on Bisection Problem in 2000, which gives a combinatorial algorithm with polylogarithmic approximation ratio. The algorithm contains lots of technical pieces, and is hard to keep all of them in mind or understand the intuition behind them. I wrote a sketch, trying to give a high level structure of the algorithm and some intuition. (In 2008, Racke improved the approximation ratio to O(log n) as a result of his Racke decomposition)

Original paper
My sketch