By Janie Chang
September 8, 2009 1:00 PM PT
The Gödel Prize is awarded each year for outstanding research papers in theoretical computer science. In May 2009, it was given to two papers, and Omer Reingold, one of the newest additions to Microsoft Research Silicon Valley, wrote or co-wrote both of them.
The first winning paper, Entropy Waves, the Zig-Zag Graph Product and New Constant Degree Expanders, by Reingold, Salil Vadhan, and Avi Wigderson, presents a new type of graph product—named the zig-zag graph product by the researchers—that enables the construction of large expander graphs, which can be thought of as networks with a sparse number of highly connected links. This paper provides a completely new set of techniques for their construction.
The second paper, Reingold’s Undirected Connectivity in Log-Space, proved that connectivity in undirected graphs can be solved within the bounds of logarithmic space, the minimal amount of memory one can desire. This is a central problem in computational complexity theory that has been open for decades.
While receiving this honor has raised Reingold’s profile in the world of theoretical computing, researchers at Microsoft were already familiar with his work. In 1998, while still in graduate school and later, while at AT&T Labs, he collaborated with Cynthia Dwork, a principal researcher with the Silicon Valley lab, co-authoring papers on zero-knowledge arguments and on encryption schemes. He also collaborated more recently with both Dwork and researcher Ilya Mironov on privacy, spending time at the Silicon Valley lab during each of these collaborations. When Reingold went from AT&T to a professorship at the Weizmann Institute of Science in Israel, Dwork stayed in touch.
“Cynthia was always enthusiastic about getting him to come to Microsoft Research,” says Roy Levin, managing director of Microsoft Research Silicon Valley. “And it’s easy to see why. He is a very smart, creative researcher who wants his work to have an impact on the world. He is highly regarded in the field, so having him at Microsoft Research will attract other top talent. And he wants to work in the kind of collaborative environment we can offer, so he will be well-positioned to do excellent work.”
Reingold’s two major areas of interest are cryptography and computational complexity theory. To the layman, encryption, the protection of information and communications, might appear a more practical topic than complexity theory, but Reingold notes that understanding the limits of computation is relevant to almost every area of computer science.
“To solve a problem efficiently,” Reingold says, “you must understand the minimum amount of time or computing resources that would be required. My focus is randomization, understanding the role of randomness in computation. It turns out that sometimes it makes sense to use algorithms that use randomness. It sounds counterintuitive, because we are used to thinking of algorithms as exact recipes, but randomization plays an important role in computations. Still, there are many reasons to avoid the use of randomness, and I study the extent to which this is possible.”
In fact, Reingold’s paper Undirected Connectivity in Log-Space is based on a classic computing problem that involves randomness: finding a way through a maze. The maze question is a fundamental problem that is at the core of computer science because there are mazes in disguise in numerous types of complex calculations, and they provide a useful analogy for applications such as airline-flight routes, road networks, and computer networks. The problem can be solved simplistically by random means: At each intersection of the maze, one flips a coin to select the next turn.
But how much memory and how much time does it take to calculate the steps required to travel from point A to point B in a maze? Solving the problem in a deterministic way, not based on randomness, is a longstanding problem in computational complexity theory. While the solution for calculating time complexity was solved more than two decades ago, there were only partial solutions to memory complexity. Algorithms based on random selection are known to use small amounts of memory. In contrast, deterministic algorithms for maze-type problems are memory hogs—or were, until Reingold devised an approach that was deterministic and almost as frugal with memory as algorithms based on random turnings.
“Getting through a maze can be a simple random process,” he says. “My work was to find a way to de-randomize this algorithm and use less memory. Now, we know that randomness is not the only way to save on computer memory for this representative problem.”
Reingold has spent the past two months settling into Microsoft Research, and part of this process has included exploring potential projects with his new colleagues. Naturally, there are opportunities for collaboration with researchers in the Algorithms and Theory and Security and Privacy groups, but he also has been in discussions with other teams, most notably in the areas of game theory and data structures. This is exactly what he hoped to do when he joined Microsoft Research.
“I was attracted at first because the expertise in this lab is very impressive,” Reingold says. “There are highly respected researchers here that I wanted to work with. At the same time, the atmosphere is one of openness. There is willingness to collaborate with scientists outside one’s direct research area. I liked the feeling that I would have opportunities to stretch out and extend my interests to other disciplines.”
Levin harbors the same hopes.
“Often,” he says, “the most interesting research results from unexpected collaborations, which, in turn, arise from having a wide variety of expertise and interests in a small organization. I would be delighted, but not entirely surprised, to discover a collaboration between Omer and someone with expertise in a very different area.”
The question everyone asks Reingold these days is “What did it feel like to win the Gödel Prize?”
“It was a good feeling to get the award,” he says. “But the real reward was people’s reaction. It felt really great for me and my fellow researchers to receive all those e-mails and phone calls of congratulations, to get that support and recognition from the research community.”
But exciting though it has been to receive the honor, Reingold says that nothing can beat the excitement he felt when he found a solution to a problem about which he had been thinking for years: a deterministic algorithm to solve memory complexity.
“I kept turning things over in my mind,” he says, “wondering if I had made an error somewhere, whether there was something I had overlooked in my argument. But at the same time, I knew I had it.”
At Microsoft Research, there is an abundance of research opportunities to keep Reingold occupied productively—and no lack of people who want to collaborate with him.
“He brings to the lab a powerful collection of expertise,” Levin says, “some of which overlaps with that of other lab members to form the basis for communication and collaboration, and other of which is new to us and will enable him to lead us into new territory. Every researcher we hire brings new expertise to the lab, and that extends the scope of problems we can attack and solve.”
Reingold agrees, adding that he feels success in research comes from being open to the unexpected, so he prefers to avoid predicting results.
“Microsoft Research takes an academic approach to research, which I really believe is the best way to conduct research,” he says. “You can't predict where the research will lead you, so you have to be open to different possibilities. You can’t predict results, but you should always be open and, most importantly, you should always be true to yourself. It pays off in the end.”