Richard Karp
Richard Karp is an American theoretical computer scientist and UC BerkeleyUniversity of California, BerkeleyThe University of California, Berkeley (UC Berkeley) is a campus of the University of California system; the University of California was founded in 1868 through a merger of two institutions and moved to Berkeley, California, in 1873.Open the full entry professor emeritus known for showing 21 combinatorial problems to be NP-complete in 1972 and for algorithms such as Edmonds–Karp; he won the 1985 ACMAustralian Community MediaAustralian Community Media (ACM) is an Australian regional and rural news publishing group with more than 100 brands, including The Canberra Times; in 2019 Nine sold it to a company controlled by interests associated with Antony Catalano and Thorney Investment Group.Open the full entry Turing Award and was founding director of the Simons Institute for the Theory of Computing.
Contents25 sections
Key facts
January 3, 1935Born in Boston
Richard Manning Karp was born in Boston, Massachusetts, on January 3, 1935.[1]
He was the oldest of four children; his father was a junior high school teacher.[2]
1940sChildhood and Boston Latin School
As a child he loved mathematics, multiplying four-digit numbers in his head, and in tenth grade faked illness to stay home and solve geometry problems.[3]
He received a classical education at Boston Latin School, studying Latin for six years.[4]
1955–1959Harvard Degrees and the Computation Lab
He received an AB in mathematics from HarvardHarvard UniversityHarvard University is a private research university in Massachusetts, established by the Massachusetts Bay Colony legislature in 1636 and named in 1639 for early benefactor John Harvard. Its principal campuses are in Cambridge and the Allston and Longwood neighborhoods of Boston. It includes Harvard College, graduate and professional schools, and the Radcliffe Institute for Advanced Study. Two governing boards share oversight. Alan M. Garber was president as of October 2026, and the endowment stood at $56.9 billion at the end of fiscal 2025.Open the full entry in 1955, an SM in applied mathematics in 1956 and a PhD in applied mathematics in 1959.[5]
His dissertation, supervised by Anthony G. Oettinger, applied graph algorithms to analyzing programs.[2]
1959–1968IBM Research
From 1959 to 1968 he worked at IBM’s Thomas J. Watson Research Center, studying parallel computation models and combinatorial problems such as the traveling salesman problem with Ray Miller, Michael Held and others.[3]
During this period he also worked at New York University, the University of MichiganUniversity of MichiganThe University of Michigan is a university founded in Detroit in 1817 that moved to Ann Arbor, Michigan, in 1837; it is governed by a statewide-elected Board of Regents and also has campuses in Dearborn and Flint.Open the full entry and the Polytechnic Institute of Brooklyn.[6]
1968Joins UC Berkeley
He joined UC Berkeley in 1968, where he built a hub for theoretical computer science and mentored many young researchers, playing a leading role in establishing the theories of parallel and probabilistic algorithms.[7]
1971–1972The Theory of NP-Completeness
In 1971 he read Steve Cook’s paper on the satisfiability problem, which inspired him to develop the notion of NP-completeness; in 1972 he and Jack Edmonds devised the Edmonds–Karp algorithm for computing maximum flow in a network.[2]
In April 1972 he presented his NP-completeness results to a large audience at a symposium at IBM; his first talk on the subject had been at a seminar at Don KnuthDonald KnuthDonald Knuth is an American computer scientist and mathematician, professor emeritus at Stanford University, author of the multi-volume The Art of Computer Programming and creator of the TeX typesetting system, often called the father of the analysis of algorithms.Open the full entry’s home.[4]
1972“Reducibility Among Combinatorial Problems”
His 1972 paper “Reducibility Among Combinatorial Problems” showed 21 problems to be NP-complete, everyday computational problems central to many applications.[3]
1972–1974First Head of the Computer Science Division
In 1972 Berkeley merged its two computer science faculty groups into a Computer Science Division within EECS; as the compromise candidate he reluctantly headed it for two years.[4]
1977Lanchester Prize
He received the INFORMS Frederick W. Lanchester Prize in 1977.[5]
1985Turing Award
He received the 1985 ACM Turing Award for continuing contributions to the theory of algorithms, including efficient algorithms for network flow and other combinatorial optimization problems, identifying polynomial-time computability with algorithmic efficiency, and the theory of NP-completeness.[8]
1985–1986Organizes MSRI’s Complexity Year
In the 1985–86 academic year he co-organized a Computational Complexity Year at the Mathematical Sciences Research Institute in Berkeley.[1]
1988Joins ICSI
From 1988 to 1995 he was a research scientist at the International Computer Science Institute in Berkeley, returning to the institute in 1999.[9]
1990John von Neumann Theory Prize
He received the INFORMS John von Neumann Theory Prize in 1990.[5]
1995Moves to the University of Washington
He joined the University of Washington faculty in 1995 and worked with Leroy Hood, chair of molecular biotechnology, on deciphering the human genetic code.[10]
July 26, 1996National Medal of Science
He received the 1996 National Medal of Science from President Bill Clinton, calling it “the most significant award that I have received.”[10]
1999Returns to Berkeley
From 1999 he again taught at UC Berkeley, where he held the Class of 1939 Chair and became a University Professor.[11]
2004Benjamin Franklin Medal
The Franklin Institute awarded him the Benjamin Franklin Medal for his contributions to the understanding of computational complexity.[6]
June 20, 2008Kyoto Prize
The Inamori Foundation named him a 2008 Kyoto Prize laureate in Advanced Technology, with a cash gift of 50 million yen; he was then a University Professor at Berkeley with joint appointments in mathematics, bioengineering, and industrial engineering and operations research.[12]
May 1, 2012Founding Director of the Simons Institute
The Simons Foundation announced a $60 million award to Berkeley to create the Simons Institute for the Theory of Computing, with him as founding director, Alistair Sinclair as associate director and Christos Papadimitriou as chief scientist.[13]
2013The Simons Institute Begins Operations
In his director’s letter he announced that the institute held its first scientific meeting in February 2013 and would begin its first full semester in August that year in the renovated Calvin Lab.[14]
December 31, 2017Steps Down as Director
After a five-year term he stepped down as director of the Simons Institute on December 31, 2017, succeeded by Shafi Goldwasser.[15]
2019The Richard M. Karp Fund and Lectures
On his third (and possibly final) retirement from Berkeley, the Simons Institute launched a fundraising campaign in his honor and established the Richard M. Karp Distinguished Lectures; the series and a permanent installation in Calvin Lab honoring his contributions launched in fall 2019.[16]
July 26, 2020Appears on the Lex Fridman Podcast
He appeared on episode 111 of the Lex FridmanLex FridmanLex Fridman is a Soviet-born, US-raised computer scientist and podcast host who works as an MIT research scientist on human-AI interaction and autonomous driving. His Lex Fridman Podcast is known for hours-long conversations with guests including heads of state and technology leaders.Open the full entry Podcast, discussing geometry, visualizing algorithms, Don Knuth, the Edmonds–Karp algorithm, P versus NP, the stable marriage problem, randomized algorithms, machine learning and bioinformatics.[17]
Related Organizations, Websites, and Public Accounts
UC Berkeley: Official website: https://www.berkeley.edu/ (opens in a new window)[18]
International Computer Science Institute: Official website: https://www.icsi.berkeley.edu/ (opens in a new window)[19]
Simons Institute for the Theory of Computing: Official website: https://simons.berkeley.edu/ (opens in a new window)[20]
Sources
- Title: What Makes an Algorithm Great? (opens in a new window)
- Karp, Richard M. - INFORMS (opens in a new window)
- Science Lives: Computer Scientist Richard Karp – Simons Foundation (opens in a new window)
- The Mysteries of Algorithms (opens in a new window)
- Richard M. Karp | EECS at UC Berkeley (opens in a new window)
- Richard M. Karp | The Franklin Institute (opens in a new window)
- Richard Manning Karp | Kyoto Prize (opens in a new window)
- Richard M. Karp | Berkeley in the 80s (opens in a new window)
- Richard Karp | Center for Computational Biology (opens in a new window)
- UW computer scientist awarded National Medal of Science (opens in a new window)
- Richard Karp (opens in a new window)
- Richard Karp, renowned computer theorist, wins 2008 Kyoto Prize (opens in a new window)
- Simons Foundation awards UC Berkeley $60 million for theory of computing institute | Research UC Berkeley (opens in a new window)
- Letter from the Director (opens in a new window)
- Oral History: Russell Impagliazzo in Conversation with Dick Karp (opens in a new window)
- Richard M. Karp Fund (opens in a new window)
- #111 - Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast (opens in a new window)
- University of California, Berkeley: Home (opens in a new window)
- ICSI (opens in a new window)
- Simons Institute for the Theory of Computing (opens in a new window)