Zhifeng Sun

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

PLOS ONE 2013

On the Complexity of Information Spreading in Dynamic Networks

with C. Dutta, G. Pandurangan, R. Rajaraman, and E. Viola

In proceedings of SODA 2013

[pdf]

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]

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)