Richard Karp

Name: Richard Karp
Title: Professor of Computer Science
Company: University of Washington
(in the process of returning to the University of California at Berkeley and the International Computer Science Institute in Berkeley).

How I arrived at my present job (academic and other influences): I have spent my entire career working on the design and analysis of algorithms and the theory of computational complexity. I received my formal education at Harvard and much of my informal education during the nine years I spent at the IBM Watson Research Center. I then went on to teach at Berkeley for twenty-six years and at the University of Washington for the past four years.

How I organize my day: On teaching days I spend the morning preparing and presenting my lecture. Nearly every day I have two or three meetings with graduate students and postdoctoral researchers; these often turn into brainstorming sessions. The rest of the time is spent doing solitary research and writing, discharging various departmental and professional service obligations, attending seminars and handling mail. No matter how busy I am, I make it a point not to miss lunch.

Amount of time spent working daily (at home and office): About nine hours on campus and sometimes an additional hour at home after dinner going through e-mail. I try to keep weekends free to be with my family and friends, but, despite my good resolutions, I often end up working for a few hours on Saturday or Sunday.

What I do to get myself thinking creatively: I try to shake out of the usual routine by taking a walk or visiting a coffeehouse. Ideas may come when I'm in bed at night, taking a shower or just walking around.

My problem-solving strategy: I just keep playing with half-baked ideas until they take more coherent form. Writing down rough ideas or explaining them to a colleague or student often clarifies my thinking.

What I do to relieve stress: Walk the dog, read a novel or a biography, play a casual game of chess or cards, chauffeur my eleven-year-old son to one of his numerous activities.

My hero, mentor, or person I most admire and why: I admire many colleagues for their brilliance and a few for maintaining vibrant family lives in addition to productive professional lives.

What I do to mentor those who work for me: I take great pride in the achievements and careers of my graduate students. I try to treat each student with respect and to sense what he or she needs from me. Some need only a sounding board, while others need more active guidance. All of them need friendship, and I try to provide it.

How a negative event changed my life in a positive way: As an undergraduate at Harvard I took classes with a future Nobel Prize winner and a future Fields Medal winner. I concluded that I could not compete with them in pure mathematics, and pursued computer science instead (although that name for the subject had not been invented yet). Computer science has offered far more scope for my abilities than pure mathematics would have offered.

One event or decision in my life I wish I could go back and change: I have concentrated a bit too single-mindedly on my professional life. I would have done better to make room for a broader range of intellectual interests and for regular physical exercise. Through the luck of the genetic draw I have maintained my health despite the lack of exercise.

What values are the most important to me and what I value in others: Integrity, openness, a sense of humor, and the courage to attack really significant problems.

What inspires, motivates, or gets me excited about my job on a daily basis: Working with bright students is a great pleasure. Research continues to be tremendous fun. The opportunity for frequent travel is a great fringe benefit of a research career. For the last several years I have been working on algorithms in molecular biology, and it has been fun to learn the needed biology from scratch; fortunately, I had great mentors to show me the way.

Biography: Richard M. Karp was born in Boston, Massachusetts in 1935 and was educated at the Boston Latin School and Harvard University, where he received the Ph.D. in Applied Mathematics in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department at the IBM Thomas J. Watson Research Center. From 1968 to 1994 he was a Professor of Computer Science, Mathematics and Operations Research at the University of California, Berkeley. From 1988 to 1995 he was also associated with the International Computer Science Institute (ICSI)in Berkeley. In 1995 he became a Professor of Computer Science and Engineering and an Adjunct Professor of Molecular Biotechnology at the University of Washington. This summer he will return to Berkeley as a University Professor. His principal appointment will be in Computer Science, and he will also hold appointments in Mathematics and Bioengineering. In addition, he will again be a research scientist at ICSI.

The unifying theme in Karp's work has been the study of combinatorial algorithms. His most significant work is the 1972 paper ``Reducibility Among Combinatorial Problems,'' which shows that many of the most commonly studied combinatorial problems are disguised versions of a single underlying problem, and thus are all of essentially the same computational complexity. Much of his subsequent work has concerned the development of parallel algorithms, the probabilistic analysis of combinatorial optimization problems,and the construction of randomized algorithms for combinatorial problems. His current research is concerned with strategies for sequencing the human genome, the physical mapping of large DNA molecules, the analysis of gene expression data, and other combinatorial problems arising in molecular biology.

Karp has received the U.S. National Medal of Science, the Harvey Prize (Technion), the Turing Award (ACM), the Centennial Medal (Harvard University) the Fulkerson Prize(AMS and Math. Programming Society), the von Neumann Theory Prize(ORSA-TIMS), the Lanchester Prize (ORSA) the von Neumann Lectureship (SIAM) and the Distinguished Teaching Award (Berkeley). He is a member of the National Academy of Sciences, the National Academy of Engineering and the American Philosophical Society,as well as a Fellow of the American Academy of Arts and Sciences. He holds four honorary degrees.

Last Modified:
Location: www.acm.org/crossroads/dayinlife/bios/richard_karp.html