Selfish Behavior and Stability of the Internet:A Game-Theoretic Analysis of TCP (2008)
Aditya Akella, Srinivasan Seshancmu, Richard Karp, Scott Shenkerchristos Papadimitriou
ABSTRACT For years, the conventional wisdom [7, 22] has been that the continued stability of the Internet depends on the widespread deployment of "socially responsible " congestion...
1 Load Balancing in Structured P2P Systems (2007)
Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, Ion Stoica
Most P2P systems that provide a DHT abstraction distribute objects among "peer nodes " by choosing random identifiers for the objects. This could result in an O(log N) imbalance....
1 Load Balancing in Structured P2P Systems (2007)
Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, Ion Stoica
Most P2P systems that provide a DHT abstraction distribute objects among "peer nodes " by choosing random identifiers for the objects. This could result in an O(log N) imbalance....
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker
Hash tables-- which map "keys " onto "values "-- are an essential building block in modern software systems. We believe a similar functionality would be equally...
Sylvia Ratnasamy, Mark Handley, Richard Karp, Scott Shenker
Most currently proposed solutions to application-level multicast organize the group members into an application-level mesh over which a Distance-Vector routing protocol, or a similar algorithm, is...
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker
Hash tables-- which map "keys " onto "values "-- are an essential building block in modern software systems. We believe a similar functionality would be equally...
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker
Hash tables-- which map "keys " onto "values "-- are an essential building block in modern software systems. We believe a similar functionality would be equally...
Paul Beame, Richard Karp, Michael Saks
Abstract. We consider several problems related to the use of resolution-based methods for determining whether a given boolean formula in conjunctive normal form is satisable. First, building on work...
Load Balancing in Dynamic Structured P2P Systems (2004)
Brighten Godfrey Karthik, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, Ion Stoica
Most P2P systems that provide a DHT abstraction distribute objects randomly among "peer nodes" in a way that results in some nodes having \Theta(log N) times as many objects as the average...
Optimal and Global Time Synchronization in Sensornets (2003)
Richard Karp, Jeremy Elson, Deborah Estrin, Scott Shenker
A model of optimally precise and globally consistent clock synchronization, using the model provided by Reference-Broadcast Synchronization.
Load balancing in structured p2p systems (2003)
Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, Ion Stoica
Most P2P systems that provide a DHT abstraction distribute objects among “peer nodes ” by choosing random identifiers for the objects. This could result in an O(log N) imbalance. Besides, P2P...
Load balancing in structured p2p systems (2003)
Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, Ion Stoica
Most P2P systems that provide a DHT abstraction distribute objects among “peer nodes ” by choosing random identifiers for the objects. This could result in an O(log N) imbalance. Besides, P2P...
Load balancing in structured p2p systems (2003)
Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, Ion Stoica
Most P2P systems that provide a DHT abstraction distribute objects among “peer nodes ” by choosing random identifiers for the objects. This could result in an O(log N) imbalance. Besides, P2P...
Optimal and global time synchronization in sensornets (2003)
Richard Karp, Jeremy Elson, Deborah Estrin, Scott Shenker
Time synchronization is necessary in many distributed systems, but achieving synchronization in sensornets, which combine stringent precision requirements with severe resource constraints, is...
Optimal and Global Time Synchronization in Sensornets (2003)
Richard Karp, Jeremy Elson, Deborah Estrin, Scott Shenker
Time synchronization is necessary in many distributed systems, but achieving synchronization in sensornets, which combine stringent precision requirements with severe resource constraints, is...
Load balancing in structured p2p systems (2003)
Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, Ion Stoica
Most P2P systems that provide a DHT abstraction distribute objects among “peer nodes ” by choosing random identifiers for the objects. This could result in an O(log N) imbalance. Besides, P2P...
Genetics Content in Introductory Biology Courses for Non-Science Majors: Theory and Practice (2002)
ADAM M. HOTT, CARL A. HUETHER, JOSEPH D. McINERNEY, CAROL CHRISTIANSON, ROBERT FOWLER, HARVEY BENDER, ...
Competitive Paging Algorithms (2002)
Fiat, Amos, Karp, Richard, Luby, Mike, McGeoch, Lyle, Sleator, Daniel, Young, Neal E.
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. This paper introduces the marking algorithm, a simple randomized...
Parallel and Distributed Computing. (2002)
Kaplansky,Irving, Karp,Richard
The Berkeley Mathematical Sciences Research Institute (MSRI) featured a program in computational complexity during 1985-86. A substantial part of the program was devoted to parallel and distributed...
Topologically-aware overlay construction and server selection (2002)
Sylvia Ratnasamy, Mark Handley, Richard Karp, Scott Shenker
A number of large-scale distributed Internet applications could potentially benefit from some level of knowledge about the relative proximity between its participating host nodes. For example, the...
Discovering Local Structure in Gene Expression Data: The Order-Preserving Submatrix Problem (2002)
Amir Ben-dor, Benny Chor, Richard Karp, Zohar Yakhini
This paper concerns the discovery of patterns in gene expression matrices, in which each element gives the expression level of a given gene in a given experiment. Most existing methods for pattern...
Topologically-aware overlay construction and server selection (2002)
Sylvia Ratnasamy, Mark H, Richard Karp, Scott Shenker
Abstract — A number of large-scale distributed Internet applications could potentially benefit from some level of knowledge about the relative proximity between its participating host nodes. For...
The efficiency of resolution and Davis-Putnam procedures (2002)
Paul Beame, Richard Karp, Toniann Pitassi, Michael Saks
We consider several problems related to the use of resolution-based methods for determining whether a given boolean formula in conjunctive normal form is satisfiable. First, building on work of...
Search Strategies in Inter-Domain Traffic Engineering (2002)
Kartikeya Chandrayana, Kartikeya Ch, Yin Zhang, Matthew Roughan, Subhabrata Sen, Richard Karp
Inter-domain Traffic Engineering (TE) capabilities can significantly improve end-to-end network performance by allowing an ISP to route its traffic around congestion or failure occurring in other ISP...
Topologically-aware overlay construction and server selection (2002)
Sylvia Ratnasamy, Mark H, Richard Karp, Scott Shenker
Abstract — A number of large-scale distributed Internet applications could potentially benefit from some level of knowledge about the relative proximity between its participating host nodes. For...
Topologically-aware overlay construction and server selection (2002)
Sylvia Ratnasamy, Mark H, Richard Karp, Et Scott Shenker, Présenté Par, Dekar Lyes
Plan de la présentation II. Modèle proposé par l’article III. Application du modèle aux overlay networks o Structuré
Application-level Multicast using Content-Addressable Networks (2001)
Sylvia Ratnasamy, Mark Handley, Richard Karp, Scott Shenker
Abstract. Most currently proposed solutions to application-level multicast organize the group members into an application-level mesh over which a DistanceVector routing protocol, or a similar...
A Scalable Content-Addressable Network (2001)
Sylvia Ratnasamy Paul, Paul Francis, Mark H, Richard Karp, Scott Shenker, Written Vladimir Eske
Contents 1 Motivation 2 2 Basic CAN architecture 3 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Data Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3...
Application-level multicast using content-addressable networks (2001)
Sylvia Ratnasamy, Mark H, Richard Karp, Scott Shenker
Abstract. Most currently proposed solutions to application-level multicast organize the group members into an application-level mesh over which a Distance-Vector routing protocol, or a similar...
Optimization Problems in Congestion Control (2000)
Richard Karp, Christos Papadimitriou
One of the crucial elements in the Internet’s success is its ability to adequately control congestion. This paper defines and solves several optimization problems related to Internet congestion...
Optimization Problems in Congestion Control (2000)
Richard Karp, Elias Koutsoupias, Christos Papadimitriou, Scott Shenker
One of the crucial elements in the Internet's success is its ability to adequately control congestion. This paper defines and solves several optimization problems related to Internet congestion...
Universal DNA Tag Systems: A Combinatorial Design Scheme (2000)
Amir Ben-Dor, Richard Karp, Benno Schwikowski, Zohar Yakhini
Custom-designed DNA arrays offer the possibility of simultaneously monitoring thousands of hybridization reactions. These arrays show great potential for many medical and scientific applications such...
Algorithms for Choosing Differential Gene Expression Experiments (1999)
Richard Karp, Roland Stoughton, Ka Yee Yeung
Understanding biological systems at the level of genes and proteins is a major challenge. In this paper we represent the interactions among external environmental inputs and genes in a biological...
Transitive Reduction in Parallel via Branchings. (1998)
Gibbons, Phillip, Karp, Richard, Ramachandran, Vijaya, Soroker, Danny, Tarjan, Robert
This document studies the following problem: given a strongly connected digraph, find a minimal strongly connected spanning subgraph of it. The main result is a parallel algorithm for this problem,...
Transitive Reduction in Parallel via Branchings, (1998)
Gibbons, Phillip, Karp, Richard, Remachandran, Vijaya, Soroker, Danny, Tarjan, Robert
We study the following problem: given a strongly connected digraph, find a minimal strongly connected spanning subgraph of it. Our main result is a parallel algorithm for this problem, which runs in...
Algorithms for Optical Mapping (1998)
Optical mapping is a novel technique for determining the restriction sites on a DNA molecule by directly observing a number of partially digested copies of the molecule under a light microscope. The...
The Rank of Sparse Random Matrices over Finite Fields (1997)
Johannes Blömer, Richard Karp, Emo Welzl
Let M be a random matrix over GF[q] such that for each entry M ij in M and for each non-zero field element ff the probability Pr[M ij = ff] is p=(q \Gamma 1), where p = (log n \Gamma c)=n and c is an...
On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas (1997)
Paul Beame, Richard Karp, Toniann Pitassi, Michael Saks
We study the complexity of proving unsatisfiability for random k-CNF formulas with clause density D = m=n where m is number of clauses and n is the number of variables. We prove the first nontrivial...
The Rank of Sparse Random Matrices over Finite Fields (1997)
Johannes Blömer, Emo Welzl, Emo Welzl, Richard Karp, Richard Karp
. Let M be a random matrix over GF[q] such that for each entry M ij in M and for each non-zero field element ff the probability Pr[M ij = ff] is p=(q \Gamma 1), where p = (log n \Gamma c)=n and c is...
AWARDS AND DISTINCTIONS (1996)
Advisers Steve Hanks, Richard Anderson, Advisers Larry Ruzzo, Richard Karp
Artificial Intelligence, with an emphasis on design and analysis of algorithms for problems in machine learning and decision making under uncertainty, as well as exploring applications to various...
An XOR-Based Erasure-Resilient Coding Scheme (1995)
Johannes Blömer, Malik Kalfane, Richard Karp, Marek Karpinski, Michael Luby, David Zuckerman
An (m; n; b; r)-erasure-resilient coding scheme consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of n packets each...
An Optimal Algorithm for Monte Carlo Estimation (1995)
Paul Dagum, Richard Karp, Michael Luby, Sheldon Ross
A typical approach to estimate an unknown quantity is to design an experiment that produces a random variable Z distributed in [0; 1] with E[Z] = , run this experiment independently a number of times...
Johannes Blomer, Malik Kalfane, Richard Karp, Marek Karpinski, Michael Luby, David Zuckerman
An (m; n; b; r)-erasure-resilient coding scheme consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of n packets each...
LogP: Towards a Realistic Model of Parallel Computation (1993)
David Culler, Richard Karp, David Patterson, Abhijit Sahay, Klaus Erik Schauser, Eunice Santos, ...
A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real...
LogP: Towards a Realistic Model of Parallel Computation (1993)
David Culler, Richard Karp, Ramesh Subramonian, Thorsten Von Eicken
A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real...
Eicken. LogP: Towards a realistic model of parallel computation (1993)
David Culler, Richard Karp, David Patterson, Abhijit Sahay, Ramesh Subramonian, Thorsten Von Eicken
A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real...
Optimal broadcast and summation in the LogP model (1993)
Richard Karp, Abhijit Sahay, Eunice Santos
We consider several natural broadcasting problems for the LogP model of distributed memory machines recently proposed by Culler et al. For each of these problems, we present algorithms that yield an...
Principles of Metareasoning (1991)
Stuart Russell, Eric Wefald, Maurice Karnaugh, Richard Karp, David Mcallester, Devika Subramanian, ...
In this paper we outline a general approach to the study of metareasoning, not in the sense of explicating the semantics of explicitly specified meta-level control policies, but in the sense of...
Transitive compaction in parallel via branchings (1991)
Phillip Gibbons, Richard Karp, Vijaya Ramachandran, Danny Soroker, Robert Tarjan
We study the following problem: given a strongly connected digraph, find a minimal strongly connected spanning subgraph of it. Our main result is a parallel algorithm for this problem, which runs in...
Transitive compaction in parallel via branchings (1991)
Phillip Gibbons, Richard Karp, Vijaya Ramachandran, Danny Soroker, Robert Tarjan
We study the following problem: given astrongly connected digraph, find a minimal strongly connected spanning subgraph of it. Our main result is a parallel algorithm for this problem, which runs in...
A randomized trial of cefepime (BMY-28142) and ceftazidime for the treatment of pneumonia (1991)
Edelstein, Howard, Chirurgi, Valerie, Oster, Sharon, Karp, Richard, Cassano, Karen, Aiken, Stephanie, ...
Cefepime is a new cephalosporin with a broad antimicrobial spectrum that includes Staphylococcus aureus and Pseudomonas aeruginosa. To study the efficacy and safety of cefepime for treatment of...
Ceftibuten versus cefaclor for the treatment of bronchitis (1991)
Chirurgi, Valerie A., Edelstein, Howard, Oster, Sharon E., Karp, Richard, Cassano, Karen B., Aiken, Stephanie, ...
Ceftibuten is an oral third generation cephalosporin with potent antimicrobial activity against Enterobacteriaceae, β-lactamase positive Haemophilia influenzae, Moraxella catarrhalis, Neisseria...