Richard M. Karp
Richard Manning Karp (born January 3, 1935 in Boston ) is an American computer scientist . He is responsible for important findings in complexity theory . In 1985 he received the Turing Award for his research work on the theory of algorithms , and in 2008 he received the Kyoto Prize .
Life
After the Boston Latin School , he attended Harvard University , where he received his bachelor's degree in literature in 1955 , his master's in mathematics in 1956 and his Ph.D. in 1959. in applied mathematics . He then worked at the IBM Thomas J. Watson Research Center until 1968 . In addition, he was a part-time research assistant at New York University in 1962, an associate visiting professor of electrical engineering at the University of Michigan from 1964 to 1965, an associate visiting professor and a full visiting professor of electrical engineering at the Polytechnic Institute of Brooklyn (part-time) from 1967 to 1968 and 1967 to 1968 Associate Professor of Industrial Engineering and Management Engineering at Columbia University (part-time). In 1968 he became Professor of Computer Science , Mathematics and Operations Research at the University of California, Berkeley . Apart from a four-year period as a professor at the University of Washington (1995 to 1999 as a professor of computer science and lecturer in molecular biotechnology), he has since remained in Berkeley, where, in addition to the university, he also worked at the International Computer Science Institute and at times also at the Mathematical Sciences Research Institute is or was active.
Karp has served on or served on the editorial boards of numerous journals, including the Journal of Computer and System Sciences and the Proceedings of the National Academy of Sciences . He was also on the Advisory Board of the Max Planck Institute for Computer Science and advised IBM Research , Hewlett-Packard , the Computer Professionals for Social Responsibility , the International Institute for Applied Systems Analysis and the Center for Discrete Mathematics and Theoretical Computer Science . He was on the supervisory board of the Weizmann Institute for Science and the Institute for Mathematics and its Applications as well as on the board of directors of the Miller Institute for Basic Research in Science . a. the Computer Science Planning Group of the National Research Council and the Computer and Information Sciences Section of the National Academy of Sciences .
In 1971, Karp and Jack Edmonds developed the Edmonds-Karp algorithm for solving the max flow problem in networks. In 1972 he published an article in which he demonstrated the NP-completeness of a number of graph-theoretic problems, including the Hamilton cycle problem , the clique problem, and the backpack problem . These became known as Karps 21 NP-Complete Problems . In 1973 he developed with John Hopcroft the Hopcroft-Karp algorithm for determining a greatest pairing in bipartite graphs . In 1987 he developed the Rabin-Karp algorithm for string searches together with Michael O. Rabin . His main research interests include combinatorial and parallel algorithms, bioinformatics and networks.
Karp’s 40 doctoral students include Narendra Karmarkar ( Fulkerson Prize 1988), Phillip Gibbons ( Paris Kanellakis Prize 2019) and Rajeev Motwani ( Gödel Prize 2001).
Awards (selection)
- 1977: Frederick W. Lanchester Prize (with Gérard Cornuéjols , Marshall Fisher and George Nemhauser ) Frederick W. Lanchester Prize
- 1979: Fulkerson Prize
- 1980: Member of the National Academy of Sciences and the New York Academy of Sciences
- 1983: Invited Speaker at the International Congress of Mathematicians in Warsaw ( The probabilistic analysis of combinatorial algorithms ).
- 1985: Turing Award and member of the American Academy of Arts and Sciences
- 1986: Honorary Doctorate from the University of Pennsylvania
- 1989: Honorary doctorate from Technion
- 1990: John von Neumann Theory Prize , Honorary Doctorate from the University of Massachusetts and Founding Fellow of the Institute of Combinatorics and its Applications
- 1991: Fellow of the American Association for the Advancement of Science
- 1992: Member of the National Academy of Engineering and Honorary Doctorate from Georgetown University
- 1994: Member of the American Philosophical Society and Fellow of the ACM
- 1996: National Medal of Science
- 1997: Harvard Centennial Medal
- 1998: Harvey Prize
- 2000: EATCS Award
- 2001: Honorary Doctorate from the University of Central Florida
- 2002: Foreign member of the Académie des sciences , honorary doctorate from Carleton University and Fellow of the Institute for Operations Research and the Management Sciences
- 2003: Honorary doctorate from ETH Zurich
- 2004: Benjamin Franklin Medal for Computer Science and Cognitive Science , as well as honorary doctorate from the Weizmann Institute for Sciences and member of the European Academy of Sciences
- 2008: Kyoto Prize
- 2008: Dickson Prize in Science
Fonts
- Reducibility Among Combinatorial Problems (PDF; 10.9 MB) . In: RE Miller, JW Thatcher (Ed.): Complexity of Computer Computations . Plenum Press, New York 1972, pp. 85-103.
Web links
- Literature by and about Richard M. Karp in the catalog of the German National Library
- Interview and biography ( memento from June 18, 2008 in the Internet Archive )
- Website (English)
Individual evidence
- ^ Frederick W. Lanchester Prize. (No longer available online.) Informs.org ( Institute for Operations Research and the Management Sciences ), archived from the original on October 2, 2015 ; accessed on February 16, 2016 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.
- ^ Honorary Degrees Awarded Since 1954 - Senate. carleton.ca, accessed March 12, 2015 .
personal data | |
---|---|
SURNAME | Karp, Richard M. |
ALTERNATIVE NAMES | Karp, Richard Manning (full name) |
BRIEF DESCRIPTION | American computer scientist |
DATE OF BIRTH | January 3, 1935 |
PLACE OF BIRTH | Boston |