Jewish Biography
 

Related Links

Biographies
Jewish Memoirs
List of Jews
List of Rabbis
Actors & Actresses
American authors
Jewish Chefs
Chess Players
Computer Scientists
Economists
Film Directors
Jewish Americans
Jewish Comedians
Jewish CEOs
Jewish Comics
Jewish Dancers
Jewish Head States
Jewish Magicians
Jewish Models
Jewish Producers
Jewish Poker Players
Jewish Philosopher
Jewish Theater
Jewish TV
Jewish Radio
Mathematicians
Motion Pictures
Music businessmen
Jewish Poets
Jewish Cartoonist
Jewish Women
Playwrights
Representatives
Senators
Singers
Songwriters
Wrestlers
Featured Jews
Harry Houdini
Hogan's Heroes
Marx Brothers
Seinfeld
The Three Stooges

-- Jewish Links --

Jewish Books
Jewish Links
Jewish Catalogs
Jewish Posters
Jewish Stories
Jewish Videos
Judaica
Judaism
Kosher Wines
Jewish Biography --> Biographies --> List of Jews --> Famous Jewish American Computer Scientists
Sponsored listings for Jewish Recipes and Kosher Cooking
Richard Manning Karp (born 1935) is a computer scientist and computational theorist, notable for research in the theory of algorithms, for which he received a Turing Award in 1985 and the Kyoto Prize in 2008.[1]

Born to Abraham and Rose Karp in Boston, Massachusetts, Karp has three younger siblings: Robert, David, and Carolyn. He attended Harvard University, where he received his Bachelor's degree in 1955, his Master's degree in 1956, and his Ph.D. in applied mathematics in 1959. He then worked at IBM's Thomas J. Watson Research Center. In 1968, he became Professor of Computer Science, Mathematics, and Operations Research at the University of California, Berkeley. Apart from a 4-year period as a professor at the University of Washington, he has remained at Berkeley. Richard Karp was awarded the National Medal of Science, and was the recipient of the Harvey Prize of the Technion and the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for his insights into computational complexity. In 1994 he was inducted as a Fellow of the Association for Computing Machinery. He is the recipient of several honorary degrees.

His citation for the Turing Award was as follows:

For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness. Karp introduced the now standard methodology for proving problems to be NP-complete which has led to the identification of many theoretical and practical problems as being computationally difficult.
In 1971 he co-developed with Jack Edmonds the Edmonds-Karp algorithm for solving the max-flow problem on networks, and in 1972 he published a landmark paper in complexity theory, "Reducibility Among Combinatorial Problems", in which he proved 21 Problems to be NP-complete. In 1987 he co-developed with Michael O. Rabin the Rabin-Karp string search algorithm. In 1980, along with Richard J. Lipton, Karp proved the Karp-Lipton theorem (which proves that, if SAT can be solved by Boolean circuits with a polynomial number of logic gates, then the polynomial hierarchy collapses to its second level).

He has made many other important discoveries in computer science and operations research in the area of combinatorial algorithms. His major current research interests include bioinformatics.

Preceded by
John McCarthy Benjamin Franklin Medal in Computer and Cognitive Science
2004 Succeeded by
Aravind Joshi

Aharon's Jewish Books and Judaica
600 South Holly Street Suite 103
Denver, Colorado 80246
303-322-7345
800-830-8660

Map to Aharon's Jewish Books and Judaica

Store Hours

Monday through Thursday 9 AM to 6 PM
Friday 9 AM to 2 PM
Sunday 9 AM to 4 PM

 

Jewish Biography | About Jewish Biography | Search

This article is licensed under the GNU Free Documentation License. It uses material from the