David Liben-Nowell's publications

[back to my home page]

Please note that the copyrights on the following papers are owned by their respective copyright holders.

Social Networks

• Joshua R. Davis, Zachary Goldman, Jacob Hilty, Elizabeth N. Koch, David Liben-Nowell, Alexa Sharp, Tom Wexler, and Emma Zhou.
  Equilibria and Efficiency Loss in Games on Networks.
  In Proceedings of SocialCom'09, August 2009.
  (to appear.)
  
  
• David Liben-Nowell and Jon Kleinberg.
  Tracing Information Flow on a Global Scale Using Internet Chain-Letter Data.
  Proceedings of the National Academy of Sciences, 105(12):4633–4638, 25 March 2008.
  

  We are very interested in gathering additional data about the spread of the chain-letter petitions described in this paper. Please visit http://petitions.cs.carleton.edu or http://petitions.cs.cornell.edu to learn more or to help.

  [ http://petitions.cs.carleton.edu | pdf | bibtex | abstract ]
  
  

• David Barbella, George Kachergis, David Liben-Nowell, Anna Sallstrom, and Ben Sowell.
  Depth of Field and Cautious-Greedy Routing in Social Networks.
  In Proceedings of ISAAC'07, December 2007.
  [ ps | pdf | bibtex | abstract ]
  
  
• Esteban Arcaute, Ning Chen, Ravi Kumar, David Liben-Nowell, Mohammad Mahdian, Hamid Nazerzadeh, and Ying Xu.
  Deterministic Decentralized Search in Random Graphs.
  In Proceedings of WAW'07, December 2007.
  [ ps | pdf | bibtex | abstract ]
  
  
• Ravi Kumar, David Liben-Nowell, and Andrew Tomkins.
  Navigating Low-Dimensional and Hierarchical Population Networks.
  In Proceedings of ESA'06, September 2006.
  [ ps | pdf | bibtex | abstract ]
  
  
• David Liben-Nowell, Jasmine Novak, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins.
  Geographic Routing in Social Networks.
  In Proceedings of the National Academy of Sciences, 102(33):11623-11628, August 2005.
  [ ps | pdf | published pdf | bibtex | abstract ]
  
  
• David Liben-Nowell.
  An Algorithmic Approach to Social Networks.
  Ph.D. Thesis, MIT Computer Science and Artificial Intelligence Laboratory, June 2005.
  [ pdf | bibtex | abstract ]
  
  
• David Liben-Nowell and Jon Kleinberg.
  The Link-Prediction Problem for Social Networks.
  In Journal of the American Society for Information Science and Technology, 58(7):1019–1031, May 2007. Previously in Proceedings of CIKM'03.
  [ ps | pdf | published version | bibtex | abstract ]
  
  
• Daniel Gruhl, R. Guha, David Liben-Nowell, and Andrew Tomkins.
  Information Diffusion through Blogspace.
  In SIGKDD Explorations, 6(2):43-52, December 2004 (special issue on web-content mining). Previously in Proceedings of WWW'04.
  [ pdf | bibtex | abstract ]

Game Theory

• Esteban Arcaute, Adam Kirsch, Ravi Kumar, David Liben-Nowell, and Sergei Vassilvitskii.
  On Threshold Behavior in Query Incentive Networks.
  In Proceedings of EC'07.
  [ ps | pdf | bibtex | abstract ]
  
  
• Matt Lepinski, David Liben-Nowell, Seth Gilbert, and April Rasala Lehman.
  Playing Games in Many Possible Worlds.
  In Proceedings of EC'06.
  [ ps | pdf | bibtex | abstract ]

Data Streams

• David Liben-Nowell, Erik Vee, and An Zhu.
  Finding Longest Increasing and Common Subsequences in Streaming Data.
  In Journal of Combinatorial Optimization, 11(2):155-175, March 2006. Previously in Proceedings of COCOON'05.
  [ ps | pdf | bibtex | abstract ]

Peer-to-Peer Systems

• David Liben-Nowell, Hari Balakrishnan, and David Karger.
  Analysis of the Evolution of Peer-to-Peer Networks.
  In Proceedings of PODC 2002.
  An abbreviated preliminary version appears in Proceedings of IPTPS 2002 under the title "Observations on the Dynamic Evolution of Peer-to-Peer Networks".
  [ ps | pdf | bibtex | abstract ]
  
  
• Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan.
  Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications.
  In IEEE/ACM Transactions on Networking, 11(1), February 2003.
  [ ps | pdf | bibtex | abstract ]

Computational Biology

• David Liben-Nowell.
  Gossip is Synteny: Incomplete Gossip and the Syntenic Distance between Genomes.
  In Journal of Algorithms, 43(2), May 2002. Previously in Proceedings of SODA '01.
  [ ps | pdf | bibtex | abstract ]
  
  
• Jon Kleinberg and David Liben-Nowell.
  The Syntenic Diameter of the Space of N-Chromosome Genomes.
  In David Sankoff and Joseph H. Nadeau (Eds.), Comparative Genomics, Kluwer Academic Press, 2000, pp. 185-197.
  (Conference on Gene Order Dynamics, Comparative Maps, and Multigene Families (DCAF), September 2000.)
  [ ps | pdf | bibtex | abstract ]
  
  
• David Liben-Nowell and Jon Kleinberg.
  Structural Properties and Tractability Results for Linear Synteny.
  In Journal of Discrete Algorithms, 2(2), June 2004. Previously in Proceedings of CPM '00.
  [ ps | pdf | bibtex | abstract ]
  
  
• David Liben-Nowell.
  On the Structure of Syntenic Distance.
  In Journal of Computational Biology 8(1), February 2001. Previously in Proceedings of CPM '99.
  [ ps | pdf | bibtex | abstract ]

Complexity of Games

• Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, and David Liben-Nowell.
  Tetris is Hard, Even to Approximate.
  In International Journal of Computational Geometry and Applications, 14(1-2):41-68, April 2004.
  A previous version appears in Proceedings of COCOON'03 by Erik D. Demaine, Susan Hohenberger, and David Liben-Nowell.
  A two-page version appears in Proceedings of Fall Workshop on Computational Geometry 2002 by the same authors.
  [ ps | ps.gz | pdf | 2-page ps | 2-page pdf | bibtex | abstract ]