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)