dblp.uni-trier.dewww.uni-trier.de

Richard M. Karp

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2009
189EEConstantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, Elad Verbin: Sorting and selection in posets. SODA 2009: 392-401
2008
188EERichard M. Karp: Computer Science as a Lens on the Sciences. ICDCS 2008: 1-2
187EEIgor Ulitsky, Richard M. Karp, Ron Shamir: Detecting Disease-Specific Dysregulated Pathways Via Analysis of Clinical Expression Profiles. RECOMB 2008: 347-359
186EEHenry Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou: Linked decompositions of networks and the power of choice in Polya urns. SODA 2008: 993-1002
185EERichard M. Karp: George Dantzig's impact on the theory of computation. Discrete Optimization 5(2): 174-185 (2008)
184EEConstantinos Daskalakis, Alexandros G. Dimakis, Richard M. Karp, Martin J. Wainwright: Probabilistic Analysis of Linear Programming Decoding. IEEE Transactions on Information Theory 54(8): 3565-3578 (2008)
2007
183EERichard M. Karp: Computer Science as a Lens on the Sciences: The Example of Computational Molecular Biology. BIBM 2007: 5
182EERichard M. Karp: Streaming Algorithms for Selection and Approximate Sorting. FSTTCS 2007: 9-20
181EELucian Popa, Afshin Rostamizadeh, Richard M. Karp, Christos H. Papadimitriou, Ion Stoica: Balancing traffic load in wireless networks with curveball routing. MobiHoc 2007: 170-179
180EEConstantinos Daskalakis, Alexandros G. Dimakis, Richard M. Karp, Martin J. Wainwright: Probabilistic analysis of linear programming decoding. SODA 2007: 385-394
179EERichard M. Karp, Robert Kleinberg: Noisy binary search and its applications. SODA 2007: 881-890
178EERichard M. Karp: Computer Science as a Lens on the Sciences: . Web Intelligence 2007
177EEBonnie Kirkpatrick, Carlos Santos Armendariz, Richard M. Karp, Eran Halperin: HAPLOPOOL: improving haplotype frequency estimation through DNA pools and phylogenetic modeling. Bioinformatics 23(22): 3048-3055 (2007)
176EEConstantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, Elad Verbin: Sorting and Selection in Posets CoRR abs/0707.1532: (2007)
175EEConstantinos Daskalakis, Alexandros G. Dimakis, Richard M. Karp, Martin J. Wainwright: Probabilistic Analysis of Linear Programming Decoding CoRR abs/cs/0702014: (2007)
174EERichard M. Karp, Ming Li, Pavel A. Pevzner, Ron Shamir: Special issue on computational molecular biology. J. Comput. Syst. Sci. 73(7): 1023 (2007)
173EEManikandan Narayanan, Richard M. Karp: Comparing Protein Interaction Networks via a Graph Match-and-Split Algorithm. Journal of Computational Biology 14(7): 892-907 (2007)
2006
172EERichard M. Karp, Till Nierhoff, Till Tantau: Optimal Flow Distribution Among Multiple Channels with Unknown Capacities . Essays in Memory of Shimon Even 2006: 111-128
171EERichard M. Karp: Fair Bandwidth Allocation Without Per-Flow State. Essays in Memory of Shimon Even 2006: 88-110
170EEBrighten Godfrey, Richard M. Karp: On the price of heterogeneity in parallel systems. SPAA 2006: 84-92
169EEJacob Scott, Trey Ideker, Richard M. Karp, Roded Sharan: Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks. Journal of Computational Biology 13(2): 133-144 (2006)
168EESonesh Surana, Brighten Godfrey, Karthik Lakshminarayanan, Richard M. Karp, Ion Stoica: Load balancing in dynamic structured peer-to-peer systems. Perform. Eval. 63(3): 217-240 (2006)
167EEIrit Gat-Viks, Richard M. Karp, Ron Shamir, Roded Sharan: Reconstructing Chain Functions in Genetic Networks. SIAM J. Discrete Math. 20(3): 727-740 (2006)
2005
166EEJacob Scott, Trey Ideker, Richard M. Karp, Roded Sharan: Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks. RECOMB 2005: 1-13
165EERichard M. Karp, Till Nierhoff, Till Tantau: Optimal flow distribution among multiple channels with unknown capacities. Electronic Notes in Discrete Mathematics 19: 225-231 (2005)
164EERichard M. Karp, Ming Li, Pavel A. Pevzner, Ron Shamir: Guest Editors' foreword. J. Comput. Syst. Sci. 70(3): 283- (2005)
163EERoded Sharan, Trey Ideker, Brian P. Kelley, Ron Shamir, Richard M. Karp: Identification of Protein Complexes by Comparative Analysis of Yeast and Bacterial Protein Interaction Data. Journal of Computational Biology 12(6): 835-846 (2005)
162EEEran Halperin, Richard M. Karp: The minimum-entropy set cover problem. Theor. Comput. Sci. 348(2-3): 240-250 (2005)
2004
161EEEran Halperin, Richard M. Karp: The Minimum-Entropy Set Cover Problem. ICALP 2004: 733-744
160EEBrighten Godfrey, Karthik Lakshminarayanan, Sonesh Surana, Richard M. Karp, Ion Stoica: Load Balancing in Dynamic Structured P2P Systems. INFOCOM 2004
159EEJeremy Elson, Richard M. Karp, Christos H. Papadimitriou, Scott Shenker: Global Synchronization in Sensornets. LATIN 2004: 609-624
158EEIrit Gat-Viks, Ron Shamir, Richard M. Karp, Roded Sharan: Reconstructing Chain Functions in Genetic Networks. Pacific Symposium on Biocomputing 2004: 498-509
157EEEran Halperin, Richard M. Karp: Perfect phylogeny and haplotype assignment. RECOMB 2004: 10-19
156EERoded Sharan, Trey Ideker, Brian P. Kelley, Ron Shamir, Richard M. Karp: Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data. RECOMB 2004: 282-289
155EERichard M. Karp: Algorithms for inferring cis-regulatory structures and protein interaction networks. RECOMB 2004: 45
154EEManikandan Narayanan, Richard M. Karp: Gapped Local Similarity Search with Provable Guarantees. WABI 2004: 74-86
153EERichard M. Karp: The Role of Experimental Algorithms in Genomics. WEA 2004: 299-300
152EEEric P. Xing, Wei Wu, Michael I. Jordan, Richard M. Karp: Logos: a Modular Bayesian Model for de Novo Motif Detection. J. Bioinformatics and Computational Biology 2(1): 127-154 (2004)
151EEAmir Ben-Dor, Tzvika Hartman, Richard M. Karp, Benno Schwikowski, Roded Sharan, Zohar Yakhini: Towards Optimally Multiplexed Applications of Universal Arrays. Journal of Computational Biology 11(2/3): 476-492 (2004)
2003
150EERichard M. Karp: The Role of Algorithmic Research in Computational Genomics. CSB 2003: 10-12
149EEEric P. Xing, Wei Wu, Michael I. Jordan, Richard M. Karp: LOGOS: a modular Bayesian model for de novo motif detection. CSB 2003: 266-276
148EEAnanth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard M. Karp, Ion Stoica: Load Balancing in Structured P2P Systems. IPTPS 2003: 68-79
147EEEran Halperin, Jeremy Buhler, Richard M. Karp, Robert Krauthgamer, Ben Westover: Detecting protein sequence conservation via metric embeddings. ISMB (Supplement of Bioinformatics) 2003: 122-129
146EERoded Sharan, Ivan Ovcharenko, Asa Ben-Hur, Richard M. Karp: CREME: a framework for identifying cis-regulatory modules in human-mouse conserved segments. ISMB (Supplement of Bioinformatics) 2003: 283-291
145EERichard M. Karp, Claire Kenyon: A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding. RANDOM-APPROX 2003: 329-340
144EEEleazar Eskin, Eran Halperin, Richard M. Karp: Large scale reconstruction of haplotypes from genotype data. RECOMB 2003: 104-113
143EEMicah Adler, Eran Halperin, Richard M. Karp, Vijay V. Vazirani: A stochastic process on the hypercube with applications to peer-to-peer networks. STOC 2003: 575-584
142EERichard M. Karp, Scott Shenker, Christos H. Papadimitriou: A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst. 28: 51-55 (2003)
141EEAmir Ben-Dor, Benny Chor, Richard M. Karp, Zohar Yakhini: Discovering Local Structure in Gene Expression Data: The Order-Preserving Submatrix Problem. Journal of Computational Biology 10(3/4): 373-384 (2003)
140EEAmir Ben-Dor, Richard M. Karp, Benno Schwikowski, Ron Shamir: The Restriction Scaffold Problem. Journal of Computational Biology 10(3/4): 385-398 (2003)
139EEIlan Adler, Hyun-Soo Ahn, Richard M. Karp, Sheldon M. Ross: Coalescing times for IID random variables with applications to population biology. Random Struct. Algorithms 23(2): 155-166 (2003)
2002
138EESylvia Ratnasamy, Mark Handley, Richard M. Karp, Scott Shenker: Topologically-Aware Overlay Construction and Server Selection. INFOCOM 2002
137EEEric P. Xing, Michael I. Jordan, Richard M. Karp, Stuart J. Russell: A Hierarchical Bayesian Markovian Model for Motifs in Biopolymer Sequences. NIPS 2002: 1489-1496
136EEAmir Ben-Dor, Benny Chor, Richard M. Karp, Zohar Yakhini: Discovering local structure in gene expression data: the order-preserving submatrix problem. RECOMB 2002: 49-57
135EEAmir Ben-Dor, Richard M. Karp, Benno Schwikowski, Ron Shamir: The restriction scaffold problem. RECOMB 2002: 58-66
134EEAditya Akella, Srinivasan Seshan, Richard M. Karp, Scott Shenker, Christos H. Papadimitriou: Selfish behavior and stability of the internet: a game-theoretic analysis of TCP. SIGCOMM 2002: 117-130
133EEAmos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, Neal E. Young: Competitive Paging Algorithms CoRR cs.DS/0205038: (2002)
132EEPaul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks: The Efficiency of Resolution and Davis--Putnam Procedures. SIAM J. Comput. 31(4): 1048-1075 (2002)
2001
131EEJack Edmonds, Richard M. Karp: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Combinatorial Optimization 2001: 31-33
130 Eric P. Xing, Michael I. Jordan, Richard M. Karp: Feature selection for high-dimensional genomic microarray data. ICML 2001: 601-608
129 Eric P. Xing, Richard M. Karp: CLIFF: clustering of high-dimensional microarray data via iterative feature filtering using normalized cuts. ISMB (Supplement of Bioinformatics) 2001: 306-315
128EESylvia Ratnasamy, Mark Handley, Richard M. Karp, Scott Shenker: Application-Level Multicast Using Content-Addressable Networks. Networked Group Communication 2001: 14-29
127EESylvia Ratnasamy, Paul Francis, Mark Handley, Richard M. Karp, Scott Shenker: A scalable content-addressable network. SIGCOMM 2001: 161-172
126 Richard M. Karp: The Genomics Revolution and its Challenges for Algorithmic Research. Current Trends in Theoretical Computer Science 2001: 631-642
125EERan El-Yaniv, Amos Fiat, Richard M. Karp, G. Turpin: Optimal Search and One-Way Trading Online Algorithms. Algorithmica 30(1): 101-139 (2001)
124 Anne Condon, Richard M. Karp: Algorithms for graph partitioning on the planted partition model. Random Struct. Algorithms 18(2): 116-140 (2001)
2000
123 Richard M. Karp, Christian Schindelhauer, Scott Shenker, Berthold Vöcking: Randomized Rumor Spreading. FOCS 2000: 565-574
122 Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker: Optimization Problems in Congestion Control. FOCS 2000: 66-74
121EERichard M. Karp: The Genomics Revolution and Its Challenges for Algorithmic Research. ICALP 2000: 428
120EEAmir Ben-Dor, Richard M. Karp, Benno Schwikowski, Zohar Yakhini: Universal DNA tag systems: a combinatorial design scheme. RECOMB 2000: 65-75
119 Richard M. Karp, Ron Shamir: Algorithms for Optical Mapping. Journal of Computational Biology 7(1-2): 303-316 (2000)
118 Amir Ben-Dor, Richard M. Karp, Benno Schwikowski, Zohar Yakhini: Universal DNA Tag Systems: A Combinatorial Design Scheme. Journal of Computational Biology 7(3-4): 503-519 (2000)
117 Richard M. Karp, Itsik Pe'er, Ron Shamir: An Algorithm Combining Discrete and Continuous Methods for Optical Mapping. Journal of Computational Biology 7(5): 745-760 (2000)
116 Paul Dagum, Richard M. Karp, Michael Luby, Sheldon M. Ross: An Optimal Algorithm for Monte Carlo Estimation. SIAM J. Comput. 29(5): 1484-1496 (2000)
115 Micah Adler, John W. Byers, Richard M. Karp: Parallel Sorting with Limited Bandwidth. SIAM J. Comput. 29(6): 1997-2015 (2000)
1999
114 Richard M. Karp, Itsik Pe'er, Ron Shamir: An Algorithm Combining Discrete and Continuous Methods for Optical Mapping. ISMB 1999: 159-168
113 Anne Condon, Richard M. Karp: Algorithms for Graph Partitioning on the Planted Partition Model. RANDOM-APPROX 1999: 221-232
112EERichard M. Karp, Roland Stoughton, Ka Yee Yeung: Algorithms for choosing differential gene expression experiments. RECOMB 1999: 208-217
111 Daniel P. Fasulo, Tao Jiang, Richard M. Karp, Reuben Settergren, Edward C. Thayer: An Algorithmic Approach to Multiple Complete Digest Mapping. Journal of Computational Biology 6(2): 187-208 (1999)
110 Richard M. Karp, Claire Kenyon, Orli Waarts: Error-resilient DNA computation. Random Struct. Algorithms 15(3-4): 450-466 (1999)
1998
109EERichard M. Karp, Ron Shamir: Algorithms for optical mapping. RECOMB 1998: 117-124
108EEDaniel P. Fasulo, Tao Jiang, Richard M. Karp, Nitin Sharma: Constructing maps using the span and inclusion relations. RECOMB 1998: 64-73
107 Richard M. Karp: Random Graphs, Random Walks, Differential Equations and the Probabilistic Analysis of Algorithms. STACS 1998: 1-2
106EEPaul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks: On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas. STOC 1998: 561-571
105 Tao Jiang, Richard M. Karp: Mapping Clones with a Given Ordering or Interleaving. Algorithmica 21(3): 262-284 (1998)
104EEDan Gusfield, Richard M. Karp, Lusheng Wang, Paul Stelling: Graph Traversals, Genes and Matroids: An Efficient Case of the Travelling Salesman Problem. Discrete Applied Mathematics 88(1-3): 167-180 (1998)
103EERichard M. Karp, Yangun Zhang: On Parallel Evaluation of Game Trees. J. ACM 45(6): 1050-1075 (1998)
1997
102 Oren Zamir, Oren Etzioni, Omid Madani, Richard M. Karp: Fast and Intuitive Clustering of Web Documents. KDD 1997: 287-290
101EEDaniel P. Fasulo, Tao Jiang, Richard M. Karp, Reuben Settergren, Edward C. Thayer: An algorithmic approach to multiple complete digest mapping. RECOMB 1997: 118-127
100EETao Jiang, Richard M. Karp: Mapping clones with a given ordering or interleaving (abstract). RECOMB 1997: 162
99 Tao Jiang, Richard M. Karp: Mapping Clones with a Given Ordering or Interleaving (Extended Abstract). SODA 1997: 400-409
98 Johannes Blömer, Richard M. Karp, Emo Welzl: The rank of sparse random matrices over finite fields. Random Struct. Algorithms 10(4): 407-419 (1997)
1996
97 Dan Gusfield, Richard M. Karp, Lusheng Wang, Paul Stelling: Graph Traversals, Genes, and Matroids: An Efficient Case of the Travelling Salesman Problem. CPM 1996: 304-319
96 Oren Etzioni, Steve Hanks, Tao Jiang, Richard M. Karp, Omid Madani, Orli Waarts: Efficient Information Gathering on the Internet (extended abstract). FOCS 1996: 234-243
95 Richard M. Karp, Claire Kenyon, Orli Waarts: Error-Resilient DNA Computation. SODA 1996: 458-467
94 Richard M. Karp, Michael Luby, Friedhelm Meyer auf der Heide: Efficient PRAM Simulation on a Distributed Memory Machine. Algorithmica 16(4/5): 517-542 (1996)
93 Helmut Alt, Leonidas J. Guibas, Kurt Mehlhorn, Richard M. Karp, Avi Wigderson: A Method for Obtaining Randomized Algorithms with Small Tail Probabilities. Algorithmica 16(4/5): 543-547 (1996)
92 David E. Culler, Richard M. Karp, David A. Patterson, Abhijit Sahay, Eunice E. Santos, Klaus E. Schauser, Ramesh Subramonian, Thorsten von Eicken: LogP: A Practical Model of Parallel Computation. Commun. ACM 39(11): 78-85 (1996)
1995
91 Paul Dagum, Richard M. Karp, Michael Luby, Sheldon M. Ross: An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract). FOCS 1995: 142-149
90 Richard M. Karp, Orli Waarts, Geoffrey Zweig: The Bit Vector Intersection Problem (Preliminary Version). FOCS 1995: 621-630
89EERichard M. Karp: Modeling parallel communication. IPPS 1995: 2-
88 Micah Adler, John W. Byers, Richard M. Karp: Scheduling Parallel Communication: The h-relation Problem. MFCS 1995: 1-20
87EEMicah Adler, John W. Byers, Richard M. Karp: Parallel Sorting with Limited Bandwidth. SPAA 1995: 129-136
86 Farid Alizadeh, Richard M. Karp, Lee Aaron Newberg, Deborah K. Weisser: Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology. Algorithmica 13(1/2): 52-76 (1995)
85 Richard M. Karp, Lee Aaron Newberg: An algorithm for analysing probed partial digestion experiments. Computer Applications in the Biosciences 11(3): 229-235 (1995)
84 Farid Alizadeh, Richard M. Karp, Deborah K. Weisser, Geoffrey Zweig: Physical Mapping of Chromosomes Using Unique Probes. Journal of Computational Biology 2(2): 159-184 (1995)
83 Richard M. Karp, Yanjun Zhang: Bounded Branching Process AND/OR Tree Evaluation. Random Struct. Algorithms 7(2): 97-116 (1995)
82 Noga Alon, Richard M. Karp, David Peleg, Douglas B. West: A Graph-Theoretic Game and Its Application to the k-Server Problem. SIAM J. Comput. 24(1): 78-100 (1995)
81 Alan M. Frieze, Richard M. Karp, Bruce A. Reed: When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem? SIAM J. Comput. 24(3): 484-493 (1995)
1994
80 Farid Alizadeh, Richard M. Karp, Deborah K. Weisser, Geoffrey Zweig: Physical Mapping of Chromosomes Using Unique Probes. SODA 1994: 489-500
79 Micah Adler, Peter Gemmell, Mor Harchol-Balter, Richard M. Karp, Claire Kenyon: Selection in the Presence of Noise: The Design of Playoff Systems. SODA 1994: 564-572
78 Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson: On the Power of Randomization in On-Line Algorithms. Algorithmica 11(1): 2-14 (1994)
77 Lisa Hellerstein, Garth A. Gibson, Richard M. Karp, Randy H. Katz, David A. Patterson: Coding Techniques for Handling Failures in Large Disk Arrays. Algorithmica 12(2/3): 182-208 (1994)
76EERichard M. Karp: Probabilistic Recurrence Relations. J. ACM 41(6): 1136-1150 (1994)
1993
75 Ran El-Yaniv, Richard M. Karp: The Mortgage Problem. ISTCS 1993: 304-312
74 David E. Culler, Richard M. Karp, David A. Patterson, Abhijit Sahay, Klaus E. Schauser, Eunice E. Santos, Ramesh Subramonian, Thorsten von Eicken: LogP: Towards a Realistic Model of Parallel Computation. PPOPP 1993: 1-12
73 Farid Alizadeh, Richard M. Karp, Lee Aaron Newberg, Deborah K. Weisser: Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology. SODA 1993: 371-381
72EERichard M. Karp, Abhijit Sahay, Eunice E. Santos, Klaus E. Schauser: Optimal Broadcast and Summation in the LogP Model. SPAA 1993: 142-153
71EERichard M. Karp: Mapping the genome: some combinatorial problems arising in molecular biology. STOC 1993: 278-285
70 Richard M. Karp: A Generalization of Binary Search. WADS 1993: 27-34
69EERichard M. Karp, Yanjun Zhang: Randomized Parallel Algorithms for Backtrack Search and Branch-and-Bound Computation. J. ACM 40(3): 765-789 (1993)
68 Narendra Karmarkar, Richard M. Karp, Richard J. Lipton, László Lovász, Michael Luby: A Monte-Carlo Algorithm for Estimating the Permanent. SIAM J. Comput. 22(2): 284-293 (1993)
1992
67 Ran El-Yaniv, Amos Fiat, Richard M. Karp, G. Turpin: Competitive Analysis of Financial Games FOCS 1992: 327-333
66 Richard M. Karp: On-Line Algorithms Versus Off-Line Algorithms: How Much is it Worth to Know the Future? IFIP Congress (1) 1992: 416-429
65 Alan M. Frieze, Richard M. Karp, Bruce A. Reed: When is the Assignment Bound Tight for the Asymmetric Traveling Salesman Problem? IPCO 1992: 453-461
64 Richard M. Karp, Michael Luby, Friedhelm Meyer auf der Heide: Efficient PRAM Simulation on a Distributed Memory Machine STOC 1992: 318-326
63 Richard M. Karp: Three-Stage Generalized Connectors. SIAM J. Discrete Math. 5(2): 259-272 (1992)
1991
62 Richard M. Karp: Probabilistic Recurrence Relations STOC 1991: 190-197
61 Sally Floyd, Richard M. Karp: FFD Bin Packing for Item Sizes with Uniform Distributions on [0, 1/2]. Algorithmica 6(2): 222-240 (1991)
60EERichard M. Karp: An introduction to randomized algorithms. Discrete Applied Mathematics 34(1-3): 165-201 (1991)
59 Phillip B. Gibbons, Richard M. Karp, Vijaya Ramachandran, Danny Soroker, Robert Endre Tarjan: Transitive Compaction in Parallel via Branchings. J. Algorithms 12(1): 110-125 (1991)
58 Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, Neal E. Young: Competitive Paging Algorithms. J. Algorithms 12(4): 685-699 (1991)
1990
57 Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani: An Optimal Algorithm for On-line Bipartite Matching STOC 1990: 352-358
56 Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson: On the Power of Randomization in Online Algorithms (Extended Abstract) STOC 1990: 379-386
55 Richard M. Karp, Vijaya Ramachandran: Parallel Algorithms for Shared-Memory Machines. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 869-942
54EEPhillip B. Gibbons, Richard M. Karp, Gary L. Miller, Danny Soroker: Subtree isomorphism is in random NC. Discrete Applied Mathematics 29(1): 35-62 (1990)
53 Richard M. Karp: The Transitive Closure of a Random Digraph. Random Struct. Algorithms 1(1): 73-94 (1990)
1989
52 Garth A. Gibson, Lisa Hellerstein, Richard M. Karp, Randy H. Katz, David A. Patterson: Failure Correction Techniques for Large Disk Arrays. ASPLOS 1989: 123-132
51EERichard M. Karp, Yanjun Zhang: On Parallel Evaluation of Game Trees. SPAA 1989: 409-420
50 Richard M. Karp, Michael Luby, Neal Madras: Monte-Carlo Approximation Algorithms for Enumeration Problems. J. Algorithms 10(3): 429-448 (1989)
1988
49 Phillip B. Gibbons, Richard M. Karp, Gary L. Miller, Danny Soroker: Subtree Isomorphism is in Random NC. AWOC 1988: 43-52
48 Richard M. Karp, Yanjun Zhang: A Randomized Parallel Branch-and-Bound Procedure STOC 1988: 290-300
47 Richard M. Karp, Eli Upfal, Avi Wigderson: The Complexity of Parallel Search. J. Comput. Syst. Sci. 36(2): 225-253 (1988)
46 Richard M. Karp, Rajeev Motwani, Prabhakar Raghavan: Deferred Data Structuring. SIAM J. Comput. 17(5): 883-902 (1988)
1987
45 Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani: Global Wire Routing in Two-Dimensional Arrays. Algorithmica 2: 113-129 (1987)
44 Richard M. Karp, Michael O. Rabin: Efficient Randomized Pattern-Matching Algorithms. IBM Journal of Research and Development 31(2): 249-260 (1987)
43EEIlan Adler, Richard M. Karp, Ron Shamir: A simplex variant solving an m times d linear program in O(min(m2, d2) expected number of pivot steps. J. Complexity 3(4): 372-387 (1987)
1986
42 Richard M. Karp, Michael E. Saks, Avi Wigderson: On a Search Problem Related to Branch-and-Bound Procedures FOCS 1986: 19-28
41 Sally Floyd, Richard M. Karp: FFD Bin Packing for Item Sizes with Distributions on [0,1/2] FOCS 1986: 322-330
40 Richard M. Karp, Eli Upfal, Avi Wigderson: Constructing a perfect matching is in random NC. Combinatorica 6(1): 35-48 (1986)
39 Richard M. Karp: Combinatorics, Complexity, and Randomness. Commun. ACM 29(2): 97-109 (1986)
1985
38 Richard M. Karp, Eli Upfal, Avi Wigderson: The Complexity of Parallel Computation on Matroids FOCS 1985: 541-550
37 Richard M. Karp, Eli Upfal, Avi Wigderson: Constructing a Perfect Matching is in Random NC STOC 1985: 22-32
36 Richard M. Karp, Eli Upfal, Avi Wigderson: Are Search and Decision Problems Computationally Equivalent? STOC 1985: 464-475
35EERichard M. Karp, Avi Wigderson: A Fast Parallel Algorithm for the Maximal Independent Set Problem J. ACM 32(4): 762-773 (1985)
34EERichard M. Karp, Michael Luby: Monte-Carlo algorithms for the planar multiterminal network reliability problem. J. Complexity 1(1): 45-64 (1985)
1984
33 Richard M. Karp, Avi Wigderson: A Fast Parallel Algorithm for the Maximal Independent Set Problem STOC 1984: 266-272
32 Richard M. Karp, Michael Luby, Alberto Marchetti-Spaccamela: A Probabilistic Analysis of Multidimensional Bin Packing Problems STOC 1984: 289-298
1983
31 Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani: Global Wire Routing in Two-Dimensional Arrays (Extended Abstract) FOCS 1983: 453-459
30 Richard M. Karp, Michael Luby: Monte-Carlo Algorithms for Enumeration and Reliability Problems FOCS 1983: 56-64
29 Richard M. Karp, Judea Pearl: Searching for an Optimal Path in a Tree with Random Costs. Artif. Intell. 21(1-2): 99-116 (1983)
1982
28 Danny Dolev, Shimon Even, Richard M. Karp: On the Security of Ping-Pong Protocols. CRYPTO 1982: 177-186
27 Narendra Karmarkar, Richard M. Karp: An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem FOCS 1982: 312-320
26 Danny Dolev, Shimon Even, Richard M. Karp: On the Security of Ping-Pong Protocols Information and Control 55(1-3): 57-68 (1982)
25 Richard M. Karp, Christos H. Papadimitriou: On Linear Characterizations of Combinatorial Optimization Problems. SIAM J. Comput. 11(4): 620-632 (1982)
1981
24 Richard M. Karp, Michael Sipser: Maximum Matchings in Sparse Random Graphs FOCS 1981: 364-375
23 Manuel Blum, Richard M. Karp, Oliver Vornberger, Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Testing Whether a Graph is a Superconcentrator. Inf. Process. Lett. 13(4/5): 164-167 (1981)
1980
22 Richard M. Karp, Christos H. Papadimitriou: On Linear Characterizations of Combinatorial Optimization Problems FOCS 1980: 1-9
21 Richard M. Karp, Richard J. Lipton: Some Connections between Nonuniform and Uniform Complexity Classes STOC 1980: 302-309
20 Richard M. Karp, Robert Endre Tarjan: Linear Expected-Time Algorithms for Connectivity Problems (Extended Abstract) STOC 1980: 368-377
19 Richard M. Karp, Robert Endre Tarjan: Linear Expected-Time Algorithms for Connectivity Problems. J. Algorithms 1(4): 374-393 (1980)
1979
18 Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, Charles Rackoff: Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems FOCS 1979: 218-223
17 Richard M. Karp: Recent Advances in the Probabilistic Analysis of Graph-Theoretic Algorithms (Abstract). ICALP 1979: 338-339
16 Richard M. Karp: A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem. SIAM J. Comput. 8(4): 561-573 (1979)
1975
15 Richard M. Karp, A. C. McKellar, C. K. Wong: Near-Optimal Solutions to a 2-Dimensional Placement Problem. SIAM J. Comput. 4(3): 271-286 (1975)
1973
14 John E. Hopcroft, Richard M. Karp: An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2(4): 225-231 (1973)
1972
13 Richard M. Karp, Raymond E. Miller, Arnold L. Rosenberg: Rapid Identification of Repeated Patterns in Strings, Trees and Arrays STOC 1972: 125-136
12EEJack Edmonds, Richard M. Karp: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM 19(2): 248-264 (1972)
11 David Gale, Richard M. Karp: A Phenomenon in the Theory of Sorting. J. Comput. Syst. Sci. 6(2): 103-115 (1972)
1971
10 John E. Hopcroft, Richard M. Karp: A n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs FOCS 1971: 122-125
1970
9 David Gale, Richard M. Karp: A Phenomenon in the Theory of Sorting FOCS 1970: 51-59
1969
8 Richard M. Karp, Raymond E. Miller: Parallel Program Schemata. J. Comput. Syst. Sci. 3(2): 147-195 (1969)
1967
7 Richard M. Karp, Raymond E. Miller: Parallel Program Schemata: A Mathematical Model for Parallel Computation FOCS 1967: 55-61
6EERichard M. Karp: Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines. J. ACM 14(3): 478-489 (1967)
5EERichard M. Karp, Raymond E. Miller, Shmuel Winograd: The Organization of Computations for Uniform Recurrence Equations. J. ACM 14(3): 563-590 (1967)
1966
4EEL. P. Horwitz, Richard M. Karp, Raymond E. Miller, Shmuel Winograd: Index Register Allocation. J. ACM 13(1): 43-61 (1966)
1965
3 Michael Held, Richard M. Karp: The Construction of Discrete Dynamic Programming Algorithms. IBM Systems Journal 4(2): 136-147 (1965)
1961
2 Richard M. Karp, F. E. McFarlin, J. P. Roth, J. R. Wilts: A computer program for the synthesis of combinational switching circuits FOCS 1961: 182-194
1960
1 Richard M. Karp: A Note on the Applicaton of Graph Theory to Digital Computer Programming Information and Control 3(2): 179-190 (1960)

Coauthor Index

1Ilan Adler [43] [139]
2Micah Adler [79] [87] [88] [115] [143]
3Hyun-Soo Ahn [139]
4Aditya Akella [134]
5Romas Aleliunas [18]
6Farid Alizadeh [73] [80] [84] [86]
7Noga Alon [82]
8Helmut Alt [93]
9Christos Amanatidis [186]
10Carlos Santos Armendariz [177]
11Paul Beame [106] [132]
12Shai Ben-David [56] [78]
13Amir Ben-Dor [118] [120] [135] [136] [140] [141] [151]
14Asa Ben-Hur [146]
15Johannes Blömer [98]
16Manuel Blum [23]
17Allan Borodin [56] [78]
18Jeremy Buhler (Jeremy D. Buhler) [147]
19John W. Byers [87] [88] [115]
20Benny Chor [136] [141]
21Anne Condon [113] [124]
22David E. Culler [74] [92]
23Paul Dagum [91] [116]
24Constantinos Daskalakis (Konstantinos Daskalakis) [175] [176] [180] [184] [189]
25Alexandros G. Dimakis [175] [180] [184]
26Danny Dolev [26] [28]
27Jack Edmonds [12] [131]
28Thorsten von Eicken [74] [92]
29Ran El-Yaniv [67] [75] [125]
30Jeremy Elson [159]
31Eleazar Eskin [144]
32Oren Etzioni [96] [102]
33Shimon Even [26] [28]
34Daniel P. Fasulo [101] [108] [111]
35Amos Fiat [58] [67] [125] [133]
36Sally Floyd [41] [61]
37Paul Francis [127]
38Alan M. Frieze [65] [81]
39David Gale [9] [11]
40Irit Gat-Viks [158] [167]
41Peter Gemmell [79]
42Phillip B. Gibbons [49] [54] [59]
43Garth A. Gibson [52] [77]
44Brighten Godfrey [160] [168] [170]
45Leonidas J. Guibas [93]
46Dan Gusfield [97] [104]
47Eran Halperin [143] [144] [147] [157] [161] [162] [177]
48Mark Handley (Mark James Handley) [127] [128] [138]
49Steve Hanks [96]
50Mor Harchol-Balter [79]
51Tzvika Hartman [151]
52Friedhelm Meyer auf der Heide [64] [94]
53Michael Held [3]
54Lisa Hellerstein [52] [77]
55John E. Hopcroft [10] [14]
56L. P. Horwitz [4]
57Trey Ideker [156] [163] [166] [169]
58Tao Jiang [96] [99] [100] [101] [105] [108] [111]
59Michael I. Jordan [130] [137] [149] [152]
60Narendra Karmarkar [27] [68]
61Randy H. Katz [52] [77]
62Brian P. Kelley [156] [163]
63Bonnie Kirkpatrick [177]
64Robert D. Kleinberg (Robert Kleinberg) [179]
65Elias Koutsoupias [122]
66Robert Krauthgamer [147]
67Karthik Lakshminarayanan [148] [160] [168]
68Frank Thomson Leighton (Tom Leighton) [31] [45]
69Ming Li [164] [174]
70Henry Lin [186]
71Richard J. Lipton [18] [21] [68]
72László Lovász [18] [68]
73Michael Luby [30] [32] [34] [50] [58] [64] [68] [91] [94] [116] [133]
74Omid Madani [96] [102]
75Neal Madras [50]
76Alberto Marchetti-Spaccamela [32]
77Claire Mathieu (Claire Kenyon, Claire Kenyon-Mathieu) [79] [95] [110] [145]
78F. E. McFarlin [2]
79Lyle A. McGeoch [58] [133]
80A. C. McKellar [15]
81Kurt Mehlhorn [93]
82Gary L. Miller [49] [54]
83Raymond E. Miller [4] [5] [7] [8] [13]
84Elchanan Mossel [176] [189]
85Rajeev Motwani [46]
86Manikandan Narayanan [154] [173]
87Lee Aaron Newberg [73] [85] [86]
88Till Nierhoff [165] [172]
89Ivan Ovcharenko [146]
90Christos H. Papadimitriou [22] [23] [25] [122] [134] [142] [159] [181] [186]
91David A. Patterson [52] [74] [77] [92]
92Itsik Pe'er [114] [117]
93Judea Pearl [29]
94David Peleg [82]
95Pavel A. Pevzner [164] [174]
96Toniann Pitassi [106] [132]
97Lucian Popa [181]
98Michael O. Rabin [44]
99Charles Rackoff [18]
100Prabhakar Raghavan [46]
101Vijaya Ramachandran [55] [59]
102Ananth Rao [148]
103Sylvia Ratnasamy [127] [128] [138]
104Bruce A. Reed [65] [81]
105Samantha Riesenfeld [176] [189]
106Ronald L. Rivest [31] [45]
107Arnold L. Rosenberg [13]
108Sheldon M. Ross [91] [116] [139]
109Afshin Rostamizadeh [181]
110J. P. Roth [2]
111Stuart J. Russell [137]
112Abhijit Sahay [72] [74] [92]
113Michael E. Saks [42] [106] [132]
114Eunice E. Santos [72] [74] [92]
115Klaus E. Schauser [72] [74] [92]
116Christian Schindelhauer [123]
117Benno Schwikowski [118] [120] [135] [140] [151]
118Jacob Scott [166] [169]
119Srinivasan Seshan [134]
120Reuben Settergren [101] [111]
121Ron Shamir [43] [109] [114] [117] [119] [135] [140] [156] [158] [163] [164] [167] [174] [187]
122Roded Sharan [146] [151] [156] [158] [163] [166] [167] [169]
123Nitin Sharma [108]
124Scott Shenker [122] [123] [127] [128] [134] [138] [142] [159]
125Martha Sideri [186]
126Michael Sipser [24]
127Daniel Dominic Sleator [58] [133]
128Danny Soroker [49] [54] [59]
129Paul Stelling [97] [104]
130Ion Stoica [148] [160] [168] [181]
131Roland Stoughton [112]
132Ramesh Subramonian [74] [92]
133Sonesh Surana [148] [160] [168]
134Till Tantau [165] [172]
135Gábor Tardos [56] [78]
136Robert Endre Tarjan [19] [20] [59]
137Edward C. Thayer [101] [111]
138Clark D. Thomborson (Clark D. Thompson) [31] [45]
139G. Turpin [67] [125]
140Igor Ulitsky [187]
141Eli Upfal [36] [37] [38] [40] [47]
142Umesh V. Vazirani [31] [45] [57]
143Vijay V. Vazirani [31] [45] [57] [143]
144Elad Verbin [176] [189]
145Berthold Vöcking [123]
146Oliver Vornberger [23]
147Orli Waarts [90] [95] [96] [110]
148Martin J. Wainwright [175] [180] [184]
149Lusheng Wang [97] [104]
150Deborah K. Weisser [73] [80] [84] [86]
151Emo Welzl [98]
152Douglas B. West [82]
153Ben Westover [147]
154Avi Wigderson [33] [35] [36] [37] [38] [40] [42] [47] [56] [78] [93]
155J. R. Wilts [2]
156Shmuel Winograd [4] [5]
157Chak-Kuen Wong (C. K. Wong) [15]
158Wei Wu [149] [152]
159Eric P. Xing [129] [130] [137] [149] [152]
160Zohar Yakhini [118] [120] [136] [141] [151]
161Mihalis Yannakakis [23]
162Ka Yee Yeung [112]
163Neal E. Young [58] [133]
164Oren Zamir [102]
165Yangun Zhang [103]
166Yanjun Zhang [48] [51] [69] [83]
167Geoffrey Zweig [80] [84] [90]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)