Misplaced Pages

#913086

15-633: The major activities of the EATCS are: Each year, the EATCS Award is awarded in recognition of a distinguished career in theoretical computer science. The first award was assigned to Richard Karp in 2000; the complete list of the winners is given below: Starting in 2010, the European Association of Theoretical Computer Science (EATCS) confers each year at the conference ICALP the Presburger Award to

30-794: A Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004 , and the Kyoto Prize in 2008. 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. Born to parents Abraham and Rose Karp in Boston, Massachusetts , Karp has three younger siblings: Robert, David , and Carolyn. His family

45-411: A young scientist (in exceptional cases to several young scientists) for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers. The award is named after Mojzesz Presburger who accomplished his path-breaking work on decidability of the theory of addition (which today is called Presburger arithmetic) as a student in 1929. The complete list of

60-540: The Held–Karp algorithm , an exact exponential-time algorithm for the travelling salesman problem . In 1971 he co-developed with Jack Edmonds the Edmonds–Karp algorithm for solving the maximum 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 1973 he and John Hopcroft published

75-531: The Hopcroft–Karp algorithm , the fastest known method for finding maximum cardinality matchings in bipartite graphs . 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). In 1987 he co-developed with Michael O. Rabin

90-1037: The Institute for Operations Research and the Management Sciences . He is the recipient of several honorary degrees and a member of the U.S. National Academy of Sciences , the American Academy of Arts and Sciences , and the American Philosophical Society . In 2012, Karp became the founding director of the Simons Institute for the Theory of Computing at the University of California, Berkeley . Karp has made many important discoveries in computer science, combinatorial algorithms , and operations research . His major current research interests include bioinformatics . In 1962 he co-developed with Michael Held

105-475: The Rabin–Karp string search algorithm . His citation for the (1985) 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

120-719: The Technion in Haifa . The prize has become a " Nobel predictor" over the years, as around 30% of its recipients have become Nobel prize winners. It is the most prestigious award bestowed upon by the Technion. The prize is named for industrialist and inventor Leo Harvey. Two prizes of $ 75,000 each are awarded each year. Candidates are submitted by past recipients, Technion Senate members and presidents of recognized institutions of higher learning and research in Israel and abroad. Generally, recipients of

135-708: The University of California, Berkeley . Karp was the first associate chair of the Computer Science Division within the Department of Electrical Engineering and Computer Science. Apart from a 4-year period as a professor at the University of Washington , he has remained at Berkeley. From 1988 to 1995 and 1999 to the present he has also been a research scientist at the International Computer Science Institute in Berkeley, where he currently leads

150-622: The Algorithms Group. 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 was elected to the 2002 class of Fellows of

165-445: The European Association for Theoretical Computer Science (EATCS) established a series of Young Researcher Schools on TCS topics. A brief history of the schools follows below. Richard Karp 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

SECTION 10

#1733084650914

180-507: The TCS community, helping to develop the standing of TCS beyond the frontiers of the community. The EATCS Bulletin is a newsletter of the EATCS, published online three times annually in February, June, and October respectively. The Bulletin is a medium for rapid publication and wide distribution of material such as: Since 2021 its editor-in-chief has been Stefan Schmid (TU Berlin). Beginning in 2014,

195-464: 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. Harvey Prize Harvey Prize is an annual Israeli award for breakthroughs in science and technology, as well as contributions to peace in the Middle East granted by

210-578: The winners is given below: The EATCS Fellows Program has been established by the Association to recognize outstanding EATCS Members for their scientific achievements in the field of Theoretical Computer Science. The Fellow status is conferred by the EATCS Fellows-Selection Committee upon a person having a track record of intellectual and organizational leadership within the EATCS community. Fellows are expected to be “model citizens” of

225-775: Was Jewish , and he grew up in a small apartment, in a then mostly Jewish neighborhood of Dorchester in Boston. Both his parents were Harvard graduates (his mother eventually obtaining her Harvard degree at age 57 after taking evening courses), while his father had had ambitions to go to medical school after Harvard, but became a mathematics teacher as he could not afford the medical school fees. 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 started working at IBM 's Thomas J. Watson Research Center . In 1968, he became professor of computer science, mathematics, and operations research at

#913086