Richard M. Karp

Richard Manning Karp
Richard Manning Karp
	Richard Karp at the EPFL in 2009
Born	January 3, 1935 (age 89); Boston, Massachusetts, US
Nationality	American
Alma mater	Harvard University (BA, MA, PhD)
Known for	Aanderaa–Karp–Rosenberg conjecture; Edmonds–Karp algorithm; Held–Karp algorithm; Hopcroft–Karp algorithm; Karmarkar–Karp algorithm; Rabin–Karp string search algorithm; Karp–Lipton theorem; Karp's 21 NP-complete problems; Vector addition system
Awards	Fulkerson Prize (1979); Turing Award (1985); John von Neumann Theory Prize (1990); IEEE Computer Society Charles Babbage Award (1995); National Medal of Science (1996); Harvey Prize (1998); EATCS award (2000); Benjamin Franklin Medal (2004); Kyoto Prize (2008);
	Scientific career
Fields	Computer Science
Institutions	University of California, Berkeley; IBM
Thesis	Some Applications of Logical Syntax to Digital Computer Programming (1959)
Doctoral advisor	Anthony Oettinger
Doctoral students	Faith Ellen; Sally Floyd; Phillip Gibbons; Dan Gusfield; Narendra Karmarkar; Valerie King; Michael Luby; Rajeev Motwani; Noam Nisan; Raymond Reiter; Eunice Santos; Thomas J. Schaefer; Ron Shamir; Barbara Simons; Eric Xing; Norman Zadeh;

Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.^[2]

Karp was elected a member of the National Academy of Engineering (1992) for major contributions to the theory and application of NP-completeness, constructing efficient combinatorial algorithms, and applying probabilistic methods in computer science.

[mg-1] Richard M. Karp at the Mathematics Genealogy Project.

[2] Richard Manning Karp - THE 2008 KYOTO PRIZE - Advanced Technology

[1]

[2]

Richard Manning Karp
Richard Karp at the EPFL in 2009
Born	(1935-01-03) January 3, 1935 (age 89) Boston, Massachusetts, US
Nationality	American
Alma mater	Harvard University (BA, MA, PhD)
Known for	Aanderaa–Karp–Rosenberg conjecture Edmonds–Karp algorithm Held–Karp algorithm Hopcroft–Karp algorithm Karmarkar–Karp algorithm Rabin–Karp string search algorithm Karp–Lipton theorem Karp's 21 NP-complete problems Vector addition system
Awards	Fulkerson Prize (1979) Turing Award (1985) John von Neumann Theory Prize (1990) IEEE Computer Society Charles Babbage Award (1995) National Medal of Science (1996) Harvey Prize (1998) EATCS award (2000) Benjamin Franklin Medal (2004) Kyoto Prize (2008)
Scientific career
Fields	Computer Science
Institutions	University of California, Berkeley IBM
Thesis	Some Applications of Logical Syntax to Digital Computer Programming (1959)
Doctoral advisor	Anthony Oettinger^[1]
Doctoral students	Faith Ellen Sally Floyd Phillip Gibbons Dan Gusfield Narendra Karmarkar Valerie King Michael Luby Rajeev Motwani Noam Nisan Raymond Reiter Eunice Santos Thomas J. Schaefer Ron Shamir Barbara Simons Eric Xing Norman Zadeh^[1]