Reid Andersen Email : [reidan] at microsoft dot com I am currently a postdoc in the theory group at Microsoft Research, Redmond. I received my Ph.D. from the math department at UCSD in 2007. My thesis advisor is professor Fan Chung Graham. My research interests include: local approximation algorithms, algorithms for web-scale graphs and datasets, graph partitioning and community identification. Curriculum Vitae (current) Research Statement (slightly outdated, from spring 2007)

Publications

• Trust-based recommendation systems: an axiomatic approach. WWW 2008.
  with Christian Borgs, Jennifer T. Chayes, Uriel Feige, Abraham D. Flaxman,
  Adam Kalai, Vahab S. Mirrokni, Moshe Tennenholtz [pdf]
• An algorithm for improving graph partitions. SODA 2008.
  with Kevin Lang [pdf]
• A local algorithm for finding dense subgraphs. SODA 2008. [pdf]
• Local computation of PageRank contributions. WAW 2007.
  with Christian Borgs, Jennifer T. Chayes, John E. Hopcraft, Vahab S. Mirrokni, Shang-Hua Teng [pdf]
  Journal version, to appear in Internet Mathematics [pdf]
• Local partitioning for directed graphs using PageRank. WAW 2007
  with Fan Chung, Kevin Lang [pdf]
  Journal version, to appear in Internet Mathematics [pdf]
• Finding dense and isolated submarkets in a sponsored search spending graph. CIKM 2007.
  with Kevin Lang [pdf]
• Detecting sharp drops in PageRank and a simplified local partitioning algorithm. TAMC 2007
  with Fan Chung [pdf]
• Spectral independence number and densest subgraph of a graph.
  The Journal of Universal Computer Science 13(11), 2007.
  with Sebastian Cioaba [pdf]
• Local graph partitioning using PageRank vectors. [pdf]
  FOCS 2006. with Fan Chung and Kevin Lang

Journal version: Using PageRank to partition a graph locally.
To appear in Internet Mathematics. [pdf]

• Communities from seed sets. WWW 2006.
  with Kevin Lang. [pdf]

• Analyzing the small world phenomenon using a hybrid model with local network flow. WAW 2004.
  with Fan Chung and Linyuan Lu. [pdf]

  Journal version: Modeling the small-world phenomenon with local network flow.
  Internet Mathematics 2(3), 2006 .
  with Fan Chung and Linyuan Lu. [pdf]

• Drawing power law graphs 12th International Symposium on Graph Drawing 2004.
  with Fan Chung and Linyuan Lu. [pdf]

  Journal version: Drawing power law graphs using a local/global decomposition.
  Algorithmica 47(4): 397 (2007), with Fan Chung and Linyuan Lu. [pdf]

• On disjoint path pairs with wavelength continuity constraint in WDM networks [pdf]
  IEEE INFOCOM 2004. with Fan Chung, Arunabha Sen, and Guoliang Xue.