Deterministic Decentralized Search in Random Graphs (2009)
Esteban Arcaute, Ning Chen, Ravi Kumar, David Liben-nowell, Mohammad Mahdian, Hamid Nazerzadeh, ...
Abstract. We study a general framework for decentralized search in random graphs. Our main focus is on deterministic memoryless search algorithms that use only local information to reach their...
Chord: A scalable peer-to-peer lookup protocol for internet applications (2009)
Ion Stoica, Robert Morris, David Liben-nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is the efficient location of the node that stores a desired data item. This paper presents Chord, a distributed lookup protocol that...
David Liben-nowell, Ravi Kumar, Prabhakar Raghavan, Jasmine Novak, Andrew Tomkins
We live in a “small world, ” where two arbitrary people are likely connected by a short chain of intermediate friends. With scant information about a target individual, people can successively...
David Liben-nowell, Jon Kleinberg
The syntenic dista nce between two species is the minimum number of fusions, fissions, and translocations required to transform one genome into the other. The linear syntenic distance, a restricted...
Deterministic Decentralized Search in Random Graphs (2008)
Esteban Arcaute, Ning Chen, Ravi Kumar, David Liben-nowell, Mohammad Mahdian, Hamid Nazerzadeh, ...
Abstract. We study a general framework for decentralized search in random graphs. Our main focus is on deterministic memoryless search algorithms that use only local information to reach their...
David Liben-nowell, An Zhu, Erik Vee
We present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data-streaming model. To decide if the LIS of a given stream...
Daniel Gruhl, David Liben-nowell, R. Guha, Andrew Tomkins
We study the dynamics of information propagation in environments of low-overhead personal publishing, using a large collection of weblogs over time as our example domain. We characterize and model...
ABSTRACT Playing Games in Many Possible Worlds (2008)
Matt Lepinski, David Liben-nowell, Seth Gilbert, April Rasala Lehman
In traditional game theory, players are typically endowed with exogenously given knowledge of the structure of the game—either full omniscient knowledge or partial but fixed information. In real...
March Madness is (NP-)Hard (draft) (2007)
David Liben-nowell, Moses Liskov, Chris Peikert, Abhi Shelat, Adam Smith, Grant Wang
Abstract. We formally dene the March-Madness decision problem (inspired by popular betting pools for the NCAA basketball tournament), and prove it NP-complete. 1
The Link Prediction Problem for Social Networks (2007)
David Liben-nowell, Jon Kleinberg
Given a snapshot of a social network, can we infer which new interactions among its members are likely to occur in the near future? We formalize this question as the link prediction problem, and...
Tetris is Hard, Even to Approximate (2007)
Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, David Liben-nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled...
David Liben-nowell, Erik Vee, An Zhu
In this paper, we present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data streaming model. For the problem of...
Navigating Low-Dimensional and Hierarchical Population Networks (2006)
Ravi Kumar, David Liben-nowell, Andrew Tomkins
Abstract. Social networks are navigable small worlds, in which two arbitrary people are likely connected by a short path of intermediate friends that can be found by a “decentralized ” routing...
Theoretical Analysis of Geographic Routing in Social Networks (2005)
Kumar, Ravi, Liben-Nowell, David, Novak, Jasmine, Raghavan, Prabhakar, Tomkins, Andrew
We introduce a formal model for geographic social networks, and introduce the notion of rank-based friendship, in which the probability that a person v is a friend of a person u is inversely...
Theoretical Analysis of Geographic Routing in Social Networks (2005)
Kumar, Ravi, Liben-Nowell, David, Novak, Jasmine, Raghavan, Prabhakar, Tomkins, Andrew
We introduce a formal model for geographic social networks, and introduce the notion of rank-based friendship, in which the probability that a person v is a friend of a person u is inversely...
An algorithmic approach to social networks (2005)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.
An algorithmic approach to social networks / (2005)
Social networks consist of a set of individuals and some form of social relationship that ties the individuals together. In this thesis, we use algorithmic techniques to study three aspects of social...
An algorithmic approach to social networks (2005)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.
Finding longest increasing and common subsequences in streaming data (2005)
David Liben-nowell, Erik Vee, An Zhu
In this paper, we present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data streaming model. For the problem of...
Information Diffusion Through Blogspace (2004)
Gruhl, D, Guha, R, Liben-Nowell, David, Tomkins, A
We study the dynamics of information propagation in environments of low-overhead personal publishing, using a large collection of weblogs over time as our example domain. We characterize and model...
Information Diffusion Through Blogspace (2004)
We study the dynamics of information propagation in environments of low-overhead personal publishing, using a large collection of weblogs over time as our example domain. We characterize and model...
Information Diffusion Through Blogspace (2004)
We study the dynamics of information propagation in environments of low-overhead personal publishing, using a large collection of weblogs over time as our example domain. We characterize and model...
Information Diffusion through Blogspace (2004)
Daniel Gruhl, David Liben-nowell, R. Guha, A. Tomkins
We study the dynamics of information propagation in environments of low-overhead personal publishing, using a large collection of weblogs over time as our example domain. We characterize and model...
Information Diffusion Through Blogspace (2004)
We study the dynamics of information propagation in environments of low-overhead personal publishing, using a large collection of weblogs over time as our example domain. We characterize and model...
Finding Longest Increasing and Common Subsequences in Streaming Data (2003)
Liben-Nowell, David, Vee, Erik, Zhu, An
In this paper, we present algorithms and lower bounds for the Longest Increasing Subsequence(LIS) and Longest Common Subsequence (LCS) problems in the data streaming model.
Finding Longest Increasing and Common Subsequences in Streaming Data (2003)
Liben-Nowell, David, Vee, Erik, Zhu, An
In this paper, we present algorithms and lower bounds for the Longest Increasing Subsequence(LIS) and Longest Common Subsequence (LCS) problems in the data streaming model.
Tetris is Hard, Even to Approximate (2003)
Erik D. Demaine, Susan Hohenberger, David Liben-nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled...
c ○ World Scientific Publishing Company TETRIS IS HARD, EVEN TO APPROXIMATE ∗ (2003)
Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, David Liben-nowell
Communicated by Binhai Zhu In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given...
Chord: a scalable peer-to-peer lookup protocol for internet applications (2003)
Ion Stoica, Robert Morris, David Liben-nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, ...
Abstract—A fundamental problem that confronts peer-to-peer applications is the efficient location of the node that stores a desired data item. This paper presents Chord, a distributed lookup...
Tetris is Hard, Even to Approximate (2003)
Erik D. Demaine, Susan Hohenberger, David Liben-nowell
Abstract. In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of...
Tetris is Hard, Even to Approximate (2003)
Erik D. Demaine, Susan Hohenberger, David Liben-nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled...
Tetris is Hard, Even to Approximate (2003)
Erik D. Demaine, Susan Hohenberger, David Liben-nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled...
Chord: a scalable peer-to-peer lookup protocol for internet applications (2003)
Ion Stoica, Robert Morris, David Liben-nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is the efficient location of the node that stores a desired data item. This paper presents Chord, a distributed lookup protocol that...
Chord: a scalable peer-to-peer lookup protocol for internet applications (2003)
Ion Stoica, Robert Morris, David Liben-nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is the efficient location of the node that stores a desired data item. This paper presents Chord, a distributed lookup protocol that...
Tetris is Hard, Even to Approximate (2003)
Erik D. Demaine, Susan Hohenberger, David Liben-nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given conguration of lled squares;...
Tetris is Hard, Even to Approximate (2003)
Erik D. Demaine, Susan Hohenberger, David Liben-nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled...
Tetris is Hard, Even to Approximate (2003)
Erik D. Demaine, Susan Hohenberger, David Liben-nowell
g the online version. It is also natural to let m and n grow, since a relatively simple dynamic program solves the case of m n = O(1) in time poly(p). NP-hardness of maximizing rows cleared. We rst...
The Link Prediction Problem for Social Networks (2003)
David Liben-nowell, Jon Kleinberg
Given a snapshot of a social network, can we infer which new interactions among its members are likely to occur in the near future? We formalize this question as the link prediction problem, and...
Tetris is Hard, Even to Approximate (2003)
Erik Demaine Susan, Susan Hohenberger, David Liben-nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given con guration of lled squares;...
Tetris is Hard, Even to Approximate (2003)
Erik D. Demaine, Susan Hohenberger, David Liben-nowell
The game of Tetris. In the popular computer game of Tetris, we are given an initial m-by-n gameboard, which is a partially filled rectangular grid. The player is given, one by one, a sequence of p...
Tetris is Hard, Even to Approximate (2002)
Demaine, Erik D., Hohenberger, Susan, Liben-Nowell, David
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled...
Observations on the dynamic evolution of peer-to-peer networks (2002)
David Liben-nowell, Hari Balakrishnan, David Karger
A fundamental theoretical challenge in peer-to-peer systems is proving statements about the evolution of the system while nodes are continuously joining and leaving. Because the system will operate...
Analysis of the evolution of peer-to-peer systems (2002)
David Liben-nowell, Hari Balakrishnan, David Karger
In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system...
Tetris Is Hard, Erik D. Demaine, Susan Hohenberger, David Liben-nowell
, when given a sequence of p pieces, and the inapproximability of the third objective to within a factor of 2 \Gamma ", for any " ? 0. Our results hold under several variations on...
Gossip is synteny: incomplete gossip and syntenic distance between genomes (2002)
The syntenic distance between two genomes is given by the minimum number of fusions, fissions, and translocations required to transform one into the other, ignoring the order of genes within...
Observations on the Dynamic Evolution of Peer-to-Peer Networks (2002)
David Liben-nowell, Hari Balakrishnan, David Karger
A fundamental theoretical challenge in peer-to-peer systems is proving statements about the evolution of the system while nodes are continuously joining and leaving. Because the system will operate...
Gossip is Synteny: Incomplete Gossip and the Syntenic Distance between Genomes (2002)
The syntenic distance between two genomes is given by the minimum number of fusions, fissions, and translocations required to transform one into the other, ignoring the order of genes within...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Liben-nowell, David Karger, M. Frans, Kaashoek Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is to e#ciently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Liben-nowell, David Karger, M. Frans, Kaashoek Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Liben-nowell, David Karger, M. Frans, Kaashoek Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications (2001)
Ion Stoica, Robert Morris, David Liben-nowell, David Karger, M. Frans, Kaashoek Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that...
Gossip is Synteny: Incomplete Gossip and an Exact Algorithm for Syntenic Distance (2001)
The syntenic distance between two genomes is given by the minimum number of fusions, ssions, and translocations required to transform one into the other, ignoring the order of genes within...
Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications (2001)
Ion Stoica, Robert Morris, David Liben-nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is the efficient location of the node that stores a desired data item. This paper presents Chord, a distributed lookup protocol that...
Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications (2001)
Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, ...
A fundamental problem that confronts peer-to-peer applications is the efficient location of the node that stores a desired data item. This paper presents Chord, a distributed lookup protocol that...
The syntenic diameter of the space of n-chromosome genomes (2000)
Jon Kleinberg, David Liben-nowell
A number of distance measures have recently been proposed for the purpose of determining evolutionary similarity among genomes of dierent species. For each of these measures, a natural but often...
Structural Properties and Tractability Results for Linear Synteny (2000)
David Liben-nowell, Jon Kleinberg
he syntenic distance between two species is the minimum number of fusions, fissions, and translocations required to transform one genome into the other. The linear syntenic distance, a restricted...
The Syntenic Diameter of the Space of N-Chromosome Genomes (2000)
Jon Kleinberg, David Liben-nowell
this paper, we settle the diameter problem for the syntenic distance over n-chromosome genomes. Note that because we allow for an arbitrary number N of genes, the space of all possible n-chromosome...
The Syntenic Diameter Of The Space Of N-Chromosome Genomes (2000)
Jon Kleinberg, David Liben-nowell
A number of distance measures have recently been proposed for the purpose of determining...
The Syntenic Diameter of the Space of N-Chromosome Genomes (2000)
Jon Kleinberg, David Liben-nowell
A number of distance measures have recently been proposed for the purpose of determining evolutionary similarity among genomes of di#erent species. For each of these measures, a natural but often...
Structural Properties and Tractability Results for Linear Synteny (2000)
David Liben-nowell, Jon Kleinberg
The syntenic dista nce between two species is the minimum number of fusions, fissions, and translocations required to transform one genome into the other. The linear syntenic distance, a restricted...
The syntenic diameter of the space of N-chromosomes genomes (2000)
Jon Kleinberg, David Liben-nowell
A number of distance measures have recently been proposed for the purpose of determining evolutionary similarity among genomes of different species. For each of these measures, a natural but often...
On the Structure of Syntenic Distance (1999)
This paper examines some of the rich structure of the syntenic distance model of evolutionary distance, introduced by Ferretti, Nadeau, and Sanko. The syntenic distance between two genomes is the...
On the Structure of Syntenic Distance (1999)
. This paper examines some of the rich structure of the syntenic distance model of evolutionary distance, introduced by Ferretti, Nadeau, and Sanko. The syntenic distance between two genomes is the...
On the Structure of Syntenic Distance (1999)
This paper examines some of the rich structure of the syntenic distance model of evolutionary distance, introduced by Ferretti, Nadeau, and Sanko. The syntenic distance between two genomes is the...
On the Structure of Syntenic Distance (1999)
This paper examines some of the rich structure of the syntenic distance model of evolutionary distance, introduced by Ferretti, Nadeau, and Sankoff. The syntenic distance between two genomes is the...
On the Structure of Syntenic Distance (1998)
This paper examines some of the rich structure of the syntenic distance measure of the evolutionary distance between genomes. This model, introduced by Ferretti, Nadeau, and Sankoff, abstracts away...
On the Structure of Syntenic Distance (1998)
This paper examines some of the rich structure of the syntenic distance measure of the evolutionary distance between genomes. This model, introduced by Ferretti, Nadeau, and Sankoff, abstracts away...
Geographic routing in social networks
Liben-Nowell, David, Novak, Jasmine, Kumar, Ravi, Raghavan, Prabhakar, Tomkins, Andrew
We live in a “small world,” where two arbitrary people are likely connected by a short chain of intermediate friends. With scant information about a target individual, people can successively...
Geographic routing in social networks
Liben-Nowell, David, Novak, Jasmine, Kumar, Ravi, Raghavan, Prabhakar, Tomkins, Andrew
We live in a “small world,” where two arbitrary people are likely connected by a short chain of intermediate friends. With scant information about a target individual, people can successively...
Tracing information flow on a global scale using Internet chain-letter data
Liben-Nowell, David, Kleinberg, Jon
Although information, news, and opinions continuously circulate in the worldwide social network, the actual mechanics of how any single piece of information spreads on a global scale have been a...