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.

You can also look at a chronology-based version of this list.

A textbook!

David Liben-Nowell.
Connecting Discrete Mathematics and Computer Science.
Cambridge University Press, 2022.
(A textbook for computer science students learning discrete math. Second edition became available in 2022!)
(The preliminary edition was published in 2016, and the first edition in 2017, by John Wiley & Sons, under the title Discrete Mathematics for Computer Science.)

Psycholinguistics

David Liben-Nowell, Julia Strand, Alexa Sharp, Tom Wexler, and Kevin Woods.
The Danger of Testing by Selecting Controlled Subsets, with Applications to Spoken-Word Recognition
Journal of Cognition, 2(1):1–15, January 2019.
[ pdf | published version | bibtex | abstract ]
Violet Brown, Xi Chen, Maryam Hedayati, Camden Sikes, Julia Strand, Tegan Wilson, and David Liben-Nowell.
Node Ordering for Rescalable Network Summarization (or, the Apparent Magic of Word Frequency and Age of Acquisition in the Lexicon).
In Proceedings of the 7th International Conference on Complex Networks and Their Applications, pages 66–80, December 2018.
[ pdf | published version | abstract | bibtex ]
Julia Strand and David Liben-Nowell.
Making Long-Distance Relationships Work: Quantifying Lexical Competition with Hidden Markov Models.
In Journal of Memory and Language, October 2016.
[ pdf | abstract | bibtex | code and data ]

Social Networks

Patty Commins, David Liben-Nowell, Tina Liu, and Kiran Tomlinson.
Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions.
In Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), June 2020.
[ pdf | arXiv | published version | bibtex | abstract ]
Justin Cheng, Jon Kleinberg, Jure Leskovec, David Liben-Nowell, Bogdan State, Karthik Subbian, and Lada Adamic.
Do Diffusion Protocols Govern Cascade Growth?.
In Proceedings of the Twelfth International Conference on Web and Social Media (ICWSM 2018), pages 32–41, June 2018.
[ pdf | abstract | bibtex ]
Desislava Hristova, David Liben-Nowell, Anastasios Noulas, Cecilia Mascolo.
If You've Got the Money, I've Got the Time: Spatio-Temporal Footprints of Spending at Sports Events on Foursquare.
In Proceedings of CityLab16 workshop (at ICWSM 2016), April 2016.
[ pdf | abstract | bibtex ]
David Liben-Nowell, Carissa Knipe, and Calder Coalson.
Indifferent Attachment: The Role of Degree in Ranking Friends.
In Proceedings of ASONAM 2013, August 2013.
[ published pdf | longer pdf | abstract | bibtex ]
Flavio Chierichetti, Jon Kleinberg, David Liben-Nowell.
Reconstructing Patterns of Information Diffusion from Incomplete Observations.
In Proceedings of NeurIPS 2011, December 2011.
[ pdf | bibtex | abstract ]
Peter DeScioli, Robert Kurzban, Elizabeth N. Koch, David Liben-Nowell.
Best Friends: Alliances, Friend Ranking, and the MySpace Social Network.
Perspectives on Psychological Science, 6(1):6–8, January 2011.
[ published paper | pdf | bibtex | abstract ]
David Liben-Nowell.
Wayfinding in Social Networks.
In Graham Cormode and Marina Thottan (Eds.), Algorithms for Next Generation Networks (Computer Communications and Networks), Springer, 2010.
[ pdf | bibtex | abstract ]
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 Internet Mathematics, 7(3):178–205, 2011. Previously in Proceedings of SocialCom'09.
[ pdf | bibtex | abstract ]
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.
[ http://petitions.cs.carleton.edu | pdf | bibtex | abstract ]
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.
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 Internet Mathematics, 5(1):141–154, 2009. Previously in Proceedings of WAW'07.
[ 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

David Liben-Nowell, Alexa Sharp, Tom Wexler, and Kevin Woods.
Computing Shapley Value in Cooperative Supermodular Games.
In Proceedings of COCOON'12, August 2012.
[ pdf | bibtex | abstract ]
Russell Buehler, Zach Goldman, David Liben-Nowell, Yuechao Pei, Jamie Quadri, Alexa Sharp, Sam Taggart, Tom Wexler, and Kevin Woods.
The Price of Civil Society.
In Proceedings of WINE'11, December 2011.
[ pdf | published pdf | bibtex | abstract ]
Joshua R. Davis, David Liben-Nowell, Alexa Sharp, and Tom Wexler.
Mediated Equilibria in Load-Balancing Games.
In Chicago Journal of Theoretical Computer Science, 2011(5). Previously in Proceedings of WINE'09.
[ journal pdf | conference pdf | bibtex | abstract ]
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 ]

CS Education

Anna N. Rafferty, David Liben-Nowell, Dave Musicant, Emy Farley, Allie Lyman, and Ann May.
Playing with Matches: Adopting Gale–Shapley for Managing Student Enrollments Beyond CS2.
In Proceedings of 55th ACM Technical Symposium on Computer Science Education (SIGCSE 2024), March 2024.
[ pdf | bibtex | abstract ]
David Liben-Nowell and Anna N. Rafferty.
Student Motivations and Goals for CS1: Themes and Variations.
In Proceedings of 53rd ACM Technical Symposium on Computer Science Education (SIGCSE 2022), March 2022.
[ 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 ]
David Liben-Nowell, Moses Liskov, Chris Peikert, abhi shelat, Adam Smith, Grant Wang.
March Madness is (NP-)Hard
Unpublished manuscript, March 2002.
[ pdf | bibtex | abstract ]

Last updated: 24 March 2022.