GOVERNMENT

Carnegie Mellon University will award its 2008 Dickson Prize in Science to Richard M. Karp, a computer scientist best known for his work in developing algorithms to solve some of the world's most complex problems. Karp will receive the award, which includes a medal and a cash prize, before giving the annual Dickson Prize lecture at 4:30 p.m., Wednesday, March 25 in McConomy Auditorium in the University Center on Carnegie Mellon's campus. His lecture, titled "The Mysteries of Algorithms," is free and open to the public.

The prestigious Dickson Prize in Science, established in 1969 by the late Pittsburgh physician Joseph Z. Dickson and his wife, Agnes Fisher Dickson, is awarded annually to individuals in the United States who make outstanding contributions to science.

Karp has made many important discoveries in computer science and operations research in the area of combinatorial algorithms. His work on the theory of NP-completeness, a cornerstone of modern theoretical computer science, is considered seminal. NP-completeness refers to a class of problems that is extremely difficult to solve and may be impossible to solve efficiently, such as searching a vast set of patterns to find one that satisfies a stated set of conditions. Such problems span all of human activity, and the algorithms that solve them can be applied to complex tasks like scheduling jobs in a factory, arranging components on a computer chip, routing electricity in a power grid and sequencing the human genome.

Currently, Karp's research is focused on the field of bioinformatics and computational biology, in which he uses computers and algorithms to determine how genes and living cells work. By applying combinatorial and probabilistic methods, Karp is attempting to find hidden patterns in gene expression data and discover the structure of gene regulatory networks.

Karp is a University Professor and professor of electrical engineering and computer sciences at the University of California, Berkeley, where he holds joint appointments in the departments of Mathematics, Bioengineering, and Industrial Engineering and Operations Research. He is the recipient of numerous honors and awards including the A.M. Turing Award, the U.S. National Medal of Science, the Kyoto Prize, the Fulkerson Prize and 10 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 is a fellow 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.

For more information about the lecture, visit the Dickson Prize Web site at http://www.cmu.edu/dickson-prize.