GAMING

The Association for Computing Machinery (ACM) has recognized Dr. Omer Reingold of the Weizmann Institute in Israel with the Grace Murray Hopper Award for his proof that resolves a longstanding and central problem in computational complexity. This field of study examines the resources, or cost, of the computation required to solve a given problem. Reingold's work showed that connectivity of undirected graphs can be resolved deterministically using an algorithm he developed that involves the minimal amount of memory. Reingold will receive the Hopper Award for outstanding young computer professional of the year. The award carries a $15,000 prize. Reingold was cited for finding a solution to a more than 25-year quest by expert theoretical computer science researchers and others. He addressed the problem of finding paths to connect vertices in undirected graphs (i.e. finding paths in a three dimensional maze). The time complexity of this key graph problem has been well understood for decades. Reingold's theorem resolves the memory-complexity of the problem by showing that connectivity in undirected graphs admits an extremely memory-efficient algorithm. The memory used by Reingold's algorithm is comparable to the memory needed to store simply the name of a single vertex of the graph. One of the most important consequences of this theorem is demonstrating the equivalence of two complexity classes (i.e. sets of computational problems with the same bounds on time and space) known as SL and L (Symmetric Logspace and Deterministic Logspace). This fundamental result greatly advances the understanding of the power of nondeterminism and randomization over deterministic memory-bounded computation. Reingold was a member of AT&T Labs from 1999-2004, and a visiting member of the School of Mathematics at the Institute for Advanced Study in Princeton, NJ. He completed his Ph.D. and postdoctoral studies at the Weizmann Institute. ACM will present the Hopper Award to Reingold at the annual ACM Awards Banquet May 20, at the Westin St. Francis Hotel in San Francisco. The Grace Murray Hopper Award honors the outstanding young computer professional of the year, selected on the basis of a single recent major technical or service contribution. The candidate must have been 35 years of age or less at the time the qualifying contribution was made. Financial support of the Grace Murray Hopper Award is provided by Google.