Richard Karp

Home * People * Richard Karp

[ Richard Karp [1] Richard M. Karp,

an American mathematician, computer scientist and pioneer in theoretical computer science and computational complexity for which he received a Turing Award in 1985, the Harvey Prize in 1998, the Benjamin Franklin Medal in 2004, and the Kyoto Prize in 2008 [2] and several honorary degrees. Richard Karp is professor emeritus at Department of Electrical Engineering and Computer Sciences with additional appointments in mathematics, bioengineering and operations research, University of California, Berkeley. His research interests further include combinatorial algorithms, discrete probability, computational biology, and internet algorithms. Karp introduced the now standard methodology for proving problems to be NP-complete. He is known for Karp’s 21 NP-complete problems, the Edmonds–Karp algorithm, the Hopcroft–Karp algorithm, the Karp–Lipton theorem, and the Rabin–Karp algorithm.

Selected Publications#

[4]

1959#

• Richard Karp (1959). Some Applications of Logical Syntax to Digital Computer Programming. Ph.D. thesis, Harvard University

1960 …#

• Richard Karp (1960). A Note on the Applicaton of Graph Theory to Digital Computer Programming. Information and Control, Vol. 3, No. 2, pdf
• Richard Karp (1964). Some Techniques of State Assignment for Synchronous Sequential Machines. IEEE Transactions on Electronic Computers, Vol. 13, No. 5
• Richard Karp (1967). Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines. Journal of the ACM, Vol. 14, No. 3
• Richard Karp, Raymond E. Miller (1969). Parallel Program Schemata. Journal of Computer and System Sciences, Vol. 3, No. 2, pdf

1970 …#

• Michael Held, Richard Karp (1970). The Traveling-Salesman Problem and Minimum Spanning Trees. Operations Research, Vol. 18, No. 6, pdf [5]
• Michael Held, Richard Karp (1971). The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming, Vol. 1, No. 1
• Richard Karp, Raymond E. Miller, Arnold L. Rosenberg (1972). Rapid Identification of Repeated Patterns in Strings, Trees and Arrays. STOC 1972
• Richard Karp (1972). Reducibility Among Combinatorial Problems. Complexity of Computer Computations 1972, pdf
• Richard Karp (1977). Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane. Mathematics of Operations Research, Vol. 2, No. 3

1980 …#

• Manuel Blum, Richard Karp, Oliver Vornberger, Christos H. Papadimitriou, Mihalis Yannakakis (1981). The Complexity of Testing Whether a Graph is a Superconcentrator. Information Processing Letters, Vol. 13, Nos. 4/5
• Richard Karp (1986). Combinatorics, complexity, and randomness. Communications of the ACM, Vol. 29, No. 2
• Richard Karp, Yanjun Zhang (1988). A randomized parallel branch-and-bound procedure. STOC ‘88
• Richard Karp, Yanjun Zhang (1989). On parallel evaluation of game trees. SPAA ‘89

1990 …#

• Richard Karp, Yanjun Zhang (1993). Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM, Vol. 40, No. 3
• Richard Karp, Yanjun Zhang (1995). Bounded branching process and and/or tree evaluation. Random Structures & Algorithms, Vol. 7, No. 2
• Richard Karp, Yanjun Zhang (1998). On Parallel Evaluation of Game Trees. Journal of the ACM, Vol. 45, No. 6

2000 …#

• Richard Karp (2000). The Genomics Revolution and Its Challenges for Algorithmic Research. ICALP 2000
• Aditya Akella, Srinivasan Seshan, Richard Karp, Scott Shenker, Christos H. Papadimitriou (2002). Selfish behavior and stability of the internet: a game-theoretic analysis of TCP. SIGCOMM 2002
• Richard Karp, Claire Kenyon (2003). A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding. RANDOM-APPROX 2003
• Richard Karp (2008). Computer Science as a Lens on the Sciences. ICDCS 2008
• Richard Karp (2008). George Dantzig’s impact on the theory of computation. Discrete Optimization, Vol 5, No. 2
• P. Brighten Godfrey, Richard Karp (2009). On the Price of Heterogeneity in Parallel Systems. Theory of Computing Systems, Vol. 45, No. 2

2010 …#

• Richard Karp (2010). Reducibility Among Combinatorial Problems. 50 Years of Integer Programming
• Karthekeyan Chandrasekaran, Richard Karp (2012). Finding a most biased coin with fewest flips. arXiv:1202.3639
• Christos H. Papadimitriou, Leonard Adleman, Richard Karp, Donald Knuth, Robert E. Tarjan, Leslie Valiant (2012). An Algorithmic View of the Universe. ACM-Turing 2012
• Ilan Adler, Yang Cao, Richard Karp, Erol A. Peköz, Sheldon M. Ross (2017). Random Knockout Tournaments. Operations Research, Vol. 65, No. 6, arXiv:1612.04448

External Links#

• Richard M. Karp’s Home Page
• Richard M. Karp from Wikipedia
• Richard M. Karp | EECS at UC Berkeley
• The Mathematics Genealogy Project - Richard Karp
• Details for Richard Karp - Oberwolfach Photo Collection
• Message from Richard Manning Karp - The 2008 Kyoto Prize, YouTube Video

References#

1. ↑ Richard Karp giving a talk at the EPFL on 13th of July 2009, Category:Richard Karp - Wikimedia Commons
2. ↑ Richard M. Karp from Wikipedia
3. ↑ Bradley C. Kuszmaul (1994). Synchronized MIMD Computing. Ph. D. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, pdf, pp. 146, Acknowledgments
4. ↑ dblp: Richard M. Karp
5. ↑ Travelling salesman problem from Wikipedia

Up one level