Donald E. Knuth, who has made fundamental contributions in theoretical computer science and is the author of one of the most highly respected references in computer science, and Jon M. Kleinberg, a computer scientist whose work explores the interface between networks and information, have been chosen to receive the Katayanagi Prizes in Computer Science.
The prizes honor the best and the brightest in the field of computer science and are presented annually by Carnegie Mellon University in cooperation with the Tokyo University of Technology (TUT). The prizes are endowed with a gift from Japanese entrepreneur and education advocate Mr. Koh Katayanagi, who founded TUT and several other technical institutions in Japan over the last six decades.
Knuth, an emeritus professor at Stanford University, will receive the 2009 Katayanagi Prize for Research Excellence, which recognizes an established researcher with a record of outstanding, sustained achievement and includes a $10,000 honorarium. Kleinberg, the Tisch University Professor of Computer Science at Cornell University, will receive the 2009 Katayanagi Emerging Leadership Prize, which honors a researcher who demonstrates the promise of becoming a leader in the field and includes a $5,000 honorarium.
"Donald Knuth is a living legend," said Randal E. Bryant, dean of Carnegie Mellon's School of Computer Science. "His books have taught thousands of computer scientists how to apply mathematical techniques to determine the efficiency of their algorithms. His TeX typesetting system has become the gold standard for publishing technical articles and books.
"Jon Kleinberg has led a major wave in the analysis of society-scale networks, describing such phenomena as how Web pages link to one another, and who has befriended whom on social media sites," Bryant said. "His work has formed fundamentally new connections between computer science and social science."
Tohru Hoshi, dean of the TUT School of Computer Science, said, "Dr. Knuth is widely known as one of the greatest scientists in programming algorithms and also as the designer of TeX. Dr. Kleinberg is famous for developing the HITS algorithm for Web network analysis as well as analyzing the small-world phenomenon.
"I am convinced that their awards will enhance the value and authority of the Katayanagi Prize and will give a significant stimulus to academic and professional activities in computer science and technology," Hoshi said.
Knuth is the author of The Art of Computer Programming, widely considered the best comprehensive treatment of the subject. Originally conceived as a single volume, it has expanded to multiple volumes, with volumes 1-3 published in 1968, 1969 and 1973, and a fourth volume due later this year. Knuth now considers writing the volumes his main life's work. His one-of-a-kind academic title at Stanford is Professor Emeritus of The Art of Computer Programming. For more information, see Dr. Dobb's An Interview with Donald Knuth.
Knuth is also famous for his work on the rigorous analysis of algorithms, for creating the TeX typesetting system and the Metafont font design system. His dry wit is legendary. "Beware of bugs in the above code," he once warned users of his software. "I have only proved it correct, not tried it." He is a winner of the Association for Computing Machinery's (ACM) Turing Award, considered the computer science equivalent of the Nobel Prize, as well as the first ACM Grace Murray Hopper Award, the National Medal of Science, the John von Neumann Medal and the Kyoto Prize.
Kleinberg's research focuses on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other online media. His work on Web link analysis using hubs and authorities helped form the foundation of the current generation of Internet search engines. His research also has provided insights into the "six degrees of separation" phenomenon explored 40 years ago by social psychologist Stanley Milgram. Kleinberg has found that the geography of connections plays a role in the search process, even on computer networks. In a finding that has proven useful in the design of peer-to-peer file-sharing networks, he has characterized when short paths can be efficiently found in networks without a central index.
Kleinberg is a member of the National Academy of Engineering and the American Academy of Arts and Sciences, and the recipient of MacArthur, Packard and Sloan Foundation fellowships. He is a recipient of the Nevanlinna Prize, the ACM-Infosys Foundation Award and the National Academy of Sciences Award for Initiatives in Research.