Maximizing the spread of influence through a social network (2009)
David Kempe, Jon Kleinberg, Éva Tardos
Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations,...
The Evolutionary Capacity of Protein Structures (2008)
In nature, one finds large collections of different protein sequences exhibiting roughly the same three-dimensional structure, and this observation underpins the study of structural protein families....
AlgorithmsforSubsetSelectioninLinearRegression ABSTRACT (2008)
We study the problem of selecting a subset of k random variables to observe that will yield the best linear prediction of another variable of interest, given the pairwise correlations between the...
Dimitris Achlioptas, David Kempe, Aaron Clauset
Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining its graph...
ABSTRACT Pricing of Partially Compatible Products (2008)
David Kempe, Adam Meyerson, Nainesh Solanki
In this paper, we examine a duopolistic market where the two firms compete to sell a system of components. Components are digital (firms have unlimited supply at no marginal cost), and customers are...
Dimitris Achlioptas, David Kempe, Aaron Clauset
Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining its graph...
ABSTRACT A Decentralized Algorithm for Spectral Analysis (2008)
In many large network settings, such as computer networks, social networks, or hyperlinked text documents, much information can be obtained from the network’s spectral properties. However,...
Fast Asynchronous Byzantine Agreement and Leader Election with Full Information (2008)
Bruce Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani
We resolve two long-standing open problems in distributed computation by showing that both Byzantine agreement and Leader Election can be solved in sub-exponential time in the asynchronous full...
Abstract On Profit-Maximizing Envy-free Pricing (2008)
Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe
We study the problem of pricing items for sale to consumers so as to maximize the seller’s revenue. We assume that for each consumer, we know the maximum amount he would be willing to pay for each...
ABSTRACT Pricing of Partially Compatible Products (2008)
David Kempe, Adam Meyerson, Nainesh Solanki
In this paper, we examine a duopolistic market where the two firms compete to sell a system of components. Components are digital (firms have unlimited supply at no marginal cost), and customers are...
The Evolutionary Capacity of Protein Structures (2008)
Leonid Meyerguz, David Kempe, Ron Elber, Jon Kleinberg
In nature, one finds large collections of different protein sequences exhibiting roughly the same three-dimensional structure, and this observation underpins the study of structural protein families....
Competitive Influence Maximization in Social Networks (2008)
Shishir Bharathi, David Kempe, Mahyar Salek
Abstract. Social networks often serve as a medium for the diffusion of ideas or innovations. An individual’s decision whether to adopt a product or innovation will be highly dependent on the...
False-Name-Proof Mechanisms for Hiring a Team (2008)
Atsushi Iwasaki, David Kempe, Yasumasa Saito, Mahyar Salek, Makoto Yokoo
Abstract. We study the problem of hiring a team of selfish agents to perform a task. Each agent is assumed to own one or more elements of a set system, and the auctioneer is trying to purchase a...
Abstract On Profit-Maximizing Envy-free Pricing (2008)
Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe
We study the problem of pricing items for sale to consumers so as to maximize the seller’s revenue. We assume that for each consumer, we know the maximum amount he would be willing to pay for each...
ABSTRACT A Decentralized Algorithm for Spectral Analysis (2008)
In many large network settings, such as computer networks, social networks, or hyperlinked text documents, much information can be obtained from the network’s spectral properties. However,...
A Knapsack Secretary Problem with Applications (2008)
Moshe Babaioff, Nicole Immorlica, David Kempe
Fellowship. Portions of this work were completed while the author was a postdoctoral fellow at UC Berkeley. Abstract. We consider situations in which a decision-maker with a fixed budget faces a...
Abstract On Profit-Maximizing Envy-free Pricing (2008)
Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe
We study the problem of pricing items for sale to consumers so as to maximize the seller’s revenue. We assume that for each consumer, we know the maximum amount he would be willing to pay for each...
Abstract Connectivity and Inference Problems for Temporal Networks (2008)
David Kempe, Jon Kleinbergý, Amit Kumarþ
Many network problems are based on fundamental relationships involving time. Consider, for example, the problems of modeling the flow of information through a distributed network, studying the spread...
The Evolutionary Capacity of Protein Structures (2008)
Leonid Meyerguz, David Kempe, Ron Elber, Jon Kleinberg
In nature, one finds large collections of different protein sequences exhibiting roughly the same three-dimensional structure, and this observation underpins the study of structural protein families....
Many network problems are based on fundamental relationships involving time. Consider, for example, the problems of modeling the flow of information through a distributed network, studying the spread...
On the Weakness of Conditional Equations in Algebraic Specification (2007)
In the initial semantics approach to algebraic specification, one usually restricts oneself to conditional equations. It is well-known that this restriction does not affect expressiveness, at least...
Communities in Graphs | Project for CS 685 (2007)
Ara Hayrapetyan, David Kempe, Zoya Svitkina
Since its creation about ten years ago, the World Wide Web (WWW) has evolved not only into an extensive and sophisticated information storage, but also a large and complex social structure. In...
Many network problems are based on fundamental relationships involving time. Consider, for example, the problems of modeling the flow of information through a distributed network, studying the spread...
Modularity-Maximizing Network Communities via Mathematical Programming (2007)
In many networks, it is of great interest to identify "communities", unusually densely knit groups of individuals. Such communities often shed light on the function of the networks or underlying...
KIV zur Verifikation von ASM-Spezifikationen am Beispiel der DLX-Pipelining Architektur. (2007)
Giese, Martin, Kempe, David, Schoenegge, Arno
In der hier beschriebenen Fallstudie wurde das KIV-System (Karlsruhe Interactive Verifier) zur Verifikation von ASM-Spezifikationen (Abstract State Machines) eingesetzt. Diese Fallstudie behandelt...
AMBROSia: An Autonomous Model-Based Reactive Observing System (2007)
Caron, David A., Das, Abhimanyu, Dhariwal, Amit, Golubchik, Leana, Govindan, Ramesh, Kempe, David, ...
Observing systems facilitate scientific studies by instrumenting the real world and collecting corresponding measurements, with the aim of detecting and tracking phenomena of interest. Our AMBROSia...
Elliot Anshelevich, David Kempe
Motivated by preventative vaccination in a graph against the worst-case outbreak of an infectious disease, we propose new important graph cut problems. In the most basic problem Min-Max Component...
Recall systems: Efficient learning and use of category indices (2007)
Omid Madani, Wiley Greiner, David Kempe, Mohammad R. Salavatipour
We introduce the framework of recall systems for efficient learning and retrieval of categories when the number of categories is large. A recallsystem here is a simple feature-based intermediate...
A knapsack secretary problem with applications (2007)
Moshe Babaioff, Nicole Immorlica, David Kempe
Fellowship. Portions of this work were completed while the author was a postdoctoral
A Generic Multi-Scale Modeling Framework for Reactive Observing Systems: An Overview (2006)
Golubchik, Leana, Caron, David A., Das, Abhimanyu, Dhariwal, Amit, Govindan, Ramesh, Kempe, David, ...
Observing systems facilitate scientific studies by instrumenting the real world and collecting corresponding measurements, with the aim of detecting and tracking phenomena of interest. A wide range...
Marko Grobelink, Daniel M. Abrams, Dimitris Achlioptas, Aaron Clauset, David Kempe
[2] Nasreen AbdulJaleel and Yan Qu. Domain term extraction and structuring via link analysis. In Dunja Mladenic, Natasha Milic-Frayling, and
Michael J. Collins, David Kempe, Jared Saia, Maxwell Young
We consider an integer-subset representation problem motivated by a medical application in radiation therapy. We prove NP-completeness, derive nontrivial bounds, and report on the performance of a...
Dimitris Achlioptas, David Kempe, Aaron Clauset, Cristopher Moore
Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining its graph...
On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs (2005)
Achlioptas, Dimitris, Clauset, Aaron, Kempe, David, Moore, Cristopher
Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining its graph...
Ara Hayrapetyan, David Kempe, Martin Pál, Zoya Svitkina
Abstract. We introduce the Minimum-size bounded-capacity cut (MinSBCC) problem, in which we are given a graph with an identified source and seek to find a cut minimizing the number of nodes on the...
Ara Hayrapetyan, David Kempe, Martin Pál, Zoya Svitkina
Abstract. We introduce the Minimum-size bounded-capacity cut (MinSBCC) problem, in which we are given a graph with an identified source and seek to find a cut minimizing the number of nodes on the...
Multi-robot forest coverage (2005)
Xiaoming Zheng, Sonal Jain, Sven Koenig, David Kempe
Abstract — One of the main applications of mobile robots is terrain coverage: visiting each location in known terrain. Terrain coverage is crucial for lawn mowing, cleaning, harvesting,...
Ara Hayrapetyan, David Kempe, Martin Pál, Zoya Svitkina
Abstract. We introduce the Minimum-size bounded-capacity cut (MinSBCC) problem, in which we are given a graph with an identified source and seek to find a cut minimizing the number of nodes on the...
Auction-based multi-robot routing (2005)
Michail G. Lagoudakis, Evangelos Markakis, David Kempe, Pinar Keskinocak, Anton Kleywegt, Sven Koenig, ...
Abstract — Recently, auction methods have been investigated as effective, decentralized methods for multi-robot coordination. Experimental research has shown great potential, but has not been...
On the Complexity of the “Reflections ” game (2003)
The game “Reflections ” is a puzzle game that has been around and entertaining users in various versions for many years. A single player tries to hit a given set of light bulbs with a laser beam,...
Maximizing the Spread of Influence Through a Social Network (2003)
Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations,...
Maximizing the Spread of Influence Through a Social Network (2003)
Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations,...
Maximizing the Spread of Influence Through a Social Network (2003)
David Kempe, Jon Kleinberg, Eva Tardos
Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations,...
Gossip-Based Computation of Aggregate Information (2003)
David Kempe, Alin Dobra, Johannes Gehrke
between computers, and a resulting paradigm shift from centralized to highly distributed systems. With massive scale also comes massive instability, as node and link failures become the norm rather...
Maximizing the Spread of Influence Through a Social Network (2003)
Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations,...
Combinatorial optimization problems in self-assembly (2002)
Adleman, Leonard, Cheng, Qi, Goel, Ashish, Huang, Ming-Deh, Kempe, David, Moisset De Espanés, Pablo, ...
Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in...
Protocols and impossibility results for gossip-based communication mechanisms (2002)
In recent years, gossip-based algorithms have gained prominence as a methodology for designing robust and scalable communication schemes in large distributed systems. The premise underlying...
Stability of load balancing algorithms in dynamic adversarial systems (2002)
Elliot Anshelevich, David Kempe, Jon Kleinberg
Abstract. In the dynamic load balancing problem, we seek to keep the job load roughly evenly distributed among the processors of a given network. The arrival and departure of jobs is modeled by an...
Stability of load balancing algorithms in dynamic adversarial systems (2002)
Elliot Anshelevich, David Kempe, Jon Kleinberg
In the dynamic load balancing problem, we seek to keep the job load roughly evenly distributed among the processors of a given network. The arrival and departure of jobs is modeled by an adversary...
Protocols and impossibility results for gossip-based communication mechanisms (2002)
In recent years, gossip-based algorithms have gained prominence as a methodology for designing robust and scalable communication schemes in large distributed systems. The premise underlying...
Protocols and impossibility results for gossip-based communication mechanisms (2002)
In recent years, gossip-based algorithms have gained prominence as a methodology for designing robust and scalable communication schemes in large distributed systems. The premise underlying...
Combinatorial optimization problems in self-assembly (2002)
Leonard Adleman, Ashish Goel, Qi Cheng, Ming-deh Huang, Paul Wilhelm, ...
Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in...
Spatial gossip and resource location protocols (2001)
David Kempe, Jon Kleinberg, Alan Demers
The dynamic behavior of a network in which information is changing continuously over time requires robust and efficient mechanisms for keeping nodes updated about new information. Gossip protocols...
Spatial gossip and resource location protocols (2001)
David Kempe, Jon Kleinberg, Alan Demers
The dynamic behavior of a network in which information is changing continuously over time requires robust and efficient mechanisms for keeping nodes updated about new information. Gossip protocols...
Spatial gossip and resource location protocols (2001)
David Kempe, Jon Kleinberg, Alan Demers
Abstract The dynamic behavior of a network in which information is changing continuously over timerequires robust and efficient mechanisms for keeping nodes updated about new information. Gossip...
Spatial gossip and resource location protocols (2001)
David Kempe, Jon Kleinberg, Alan Demers
The dynamic behavior of a network in which information is changing continuously over time requires robust and e#cient mechanisms for keeping nodes updated about new information. Gossip protocols are...
Spatial gossip and resource location protocols (2001)
David Kempe, Jon Kleinberg, Alan Demers
The dynamic behavior of a network in which information is changing continuously over time requires robust and efficient mechanisms for keeping nodes updated about new information. Gossip protocols...
Connectivity and Inference Problems for Temporal Networks (2000)
David Kempe, Jon Kleinberg, Amit Kumar
Many network problems are based on fundamental relationships involving time. Consider, for example, the problems of modeling the flow of information through a distributed network, studying the spread...
On the Power of Quantifiers in First-Order Algebraic Specification (1998)
. The well-known completeness theorem of Bergstra & Tucker [BT82, BT87] states that all computable data types can be specified without quantifiers, i.e., quantifiers can be dispensed with---at...