Ph.D. recipient receives top award in the field of computer science

Chicago computer science Ph.D. recipient Dieter van Melkebeek has received the Association for Computing Machinery’s 1999 Doctoral Dissertation Award, which is the top such award in computer science.

Van Melkebeek received the award Saturday, May 6, in San Francisco. His dissertation, “Randomness and Completeness in Computational Complexity,” will be published in the ACM Distinguished Dissertation Series by Springer-Verlag.

“This is the only major award given for the best doctoral dissertation in computer science overall,” said Lance Fortnow, Associate Professor in Computer Science, who directed van Melkebeek’s dissertation. “I’m a little biased, but I think Dieter wrote a wonderful thesis. I’m very happy he got the award. This is the same organization that gives the Turing Award, which is the equivalent of a Nobel Prize in computer science.”

Founded in 1947, the Association for Computing Machinery has 80,000 members and bills itself as the world’s first educational and scientific computing society.

“I feel deeply honored to receive the award,” van Melkebeek said. “The list of previous recipients is very impressive. I even feel a bit uncomfortable to become part of it.

“I am also very happy as a scholar. ACM, once again, awarded the prize to theoretical work with long-term goals. It is great that a community that is largely driven by immediate practical applications recognizes the value of fundamental research and stimulates it.”

With this award, the University has joined an elite group in computer science departments, said Stuart Kurtz, Professor and Chairman of Computer Science. “The top five computer science programs––MIT, Stanford, Berkeley, Carnegie Mellon and Cornell––have dominated, accounting for 19 of the 23 awards,” Kurtz said.

Van Melkebeek’s dissertation addresses problems that have a variety of practical implications, including the creation of more reliable stock market simulations, solutions to cryptographic problems and the development of more efficient airline schedules.

Computational complexity theory deals with how many resources, especially time and memory, it would take to solve certain computational problems. From a practical standpoint, many of these problems are so similar that once an efficient solution is found for one, it also can be applied to others.

“Complexity theory is essentially about seeing whether or not we can come up with more efficient solutions for this whole class of problems,” van Melkebeek said.

Some of these problems have solutions that tend to be easily verified once found, but coming up with a good solution to begin with can be quite difficult, van Melkebeek said.

An example is the traveling salesman problem, in which the salesman must develop an itinerary that will allow him to visit a number of cities via the shortest possible route.

“It’s generally very easy to check how long a given tour takes, but it’s very hard to find the fastest tour because you might have to look through all the possibilities,” Fortnow said. “The question is, do you really need to look through all the possibilities, or can you do it more quickly?”

Many theoreticians rely on randomness, or spot-checking possibilities, in order to rapidly arrive at solutions for various problems. But true randomness is difficult to achieve, even with the help of a computer, Fortnow said. Analysts who run complex simulations that depend on randomness want to be able to trust the answers they get. Van Melkebeek’s work is partly aimed at developing trustworthy randomness-generation techniques.

In his dissertation, van Melkebeek found that randomness is of little help in solving problems of the traveling-salesman type, although it can effectively be applied to others. Knowing that randomness does not help solve certain types of problems is of potential interest to cryptographers, van Melkebeek said, because their goal is to devise impenetrable codes.

After completing his Ph.D. last year, van Melkebeek began serving a two-year joint postdoctoral research appointment with the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers University and at the Institute for Advanced Study. Previous recipients of the ACM dissertation award include Ketan Mulmuley, Professor in Computer Science. Mulmuley received the award in 1986 for the Ph.D. dissertation he wrote as a student at Carnegie Mellon University. The runner-up for the 1991 award was Chicago Ph.D. recipient Carsten Lund, whose dissertation Fortnow also directed. Lund now works for AT&T Labs-Research.