Carnegie Mellon Announces Knuth and Kleinberg Will Receive Katayanagi Prizes In Computer Science
January 7, 2010

PITTSBURGH—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.

Both Katayanagi recipients will receive their awards and present a lecture in the Rashid Auditorium of Carnegie Mellon’s Gates and Hillman centers. Kleinberg will present his lecture, “Meme-tracking, Scheduling, and the Flow of On-Line Information,” at 4 p.m., Thursday, Jan. 21. Knuth will present his award lecture on May 5.

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.

He also is 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.

For more information, visit the Katayanagi Prize Web site,

About Tokyo University of Technology: The Tokyo University of Technology was founded in 1986 as a college consisting solely of the School of Engineering in the Hachioji district of Tokyo. Since then, as a forward-looking university always prepared to meet current society’s needs, it has cultivated new horizons in higher education, as exemplified by the opening of Japan's first School of Media Science as well as the School of Bionics, which is among the first in the world. In 2010, it will take a major step toward a more comprehensive university by constructing a 20-story building in Ota Ward, Tokyo, to house the School of Health Science and the School of Design. As of 2009, it has about 6,000 students. The 36-hectare (90-acre) campus in Hachioji is blessed with rich greenery; together with the new Kamata campus close to the Haneda International Airport, it embodies founder Koh Katayanagi's spirit of “an ideal environment for an ideal education.

Byron Spice