Title: What Makes an Algorithm Great? 

Name: Richard Karp  
UC Berkeley  
Time: October 12 (Monday) 09:0010:00  
Location: LectureHall, FIT Building, Tsinghua University  
Host Unit: ITCS, Tsinghua University 
From time to time a new algorithm comes along that causes a sensation in theoretical computer science or in an area of application because of its resolution of a longstanding open question, its surprising efficiency, its practical usefulness, the novelty of its setting or approach, the elegance of its structure, the subtlety of its analysis or its range of applications. We will give examples of algorithms that qualify for greatness for one or more of these reasons, and discuss how to equip students to appreciate them and understand theor strengths and weaknesses. 
Richard M. Karp was born in Boston, Massachusetts on January 3, 1935. He attended Boston Latin School and Harvard University, receiving the Ph.D. in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department at IBM Research. From 1968 to 1994 and from 1999 to the present he has been a Professor at the University of California, Berkeley, where he held the Class of 1939 Chair and is currently a University Professor. From 1988 to 1995 and 1999 to the present he has been a Research Scientist at the International Computer Science Institute in Berkeley. From 1995 to 1999 he was a Professor at the University of Washington. During the 198586 academic year he was the coorganizer of a Computational Complexity Year at the Mathematical Sciences Research Institute in Berkeley. During the 19992000 academic year he was the HewlettPackard Visiting Professor at the Mathematical Sciences Research Institute.
The unifying theme in Karp's work has been the study of combinatorial algorithms. His 1972 paper ``Reducibility Among Combinatorial Problems'' showed that many of the most commonly studied combinatorial problems are NPcomplete, and hence likely to be intractable. Much of his work has concerned parallel algorithms, the probabilistic analysis of combinatorial optimization algorithms and the construction of randomized algorithms for combinatorial problems. His current activities center around algorithmic methods in genomics and computer networking. He has supervised thirtynine Ph.D. dissertations.
His honors and awards include: U.S. National Medal of Science, Turing Award, Kyoto Prize, Fulkerson Prize, Harvey Prize (Technion), Centennial Medal (Harvard), Dickson Prize (Carnegie Mellon), Lanchester Prize, Von Neumann Theory Prize, Von Neumann Lectureship, Distinguished Teaching Award (Berkeley), Faculty Research Lecturer (Berkeley), Miller Research Professor (Berkeley), Babbage Prize and ten honorary degrees. He is a member of the U.S. National Academies of Sciences and Engineering, the American Philosophical Society and the French Academy of Sciences, and a Fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science, the Association for Computing Machinery and the Institute for Operations Research and Management Science.
