Weizmann Institute Professor Wins ACM Award

[bemildred]

This is actually a very big deal. How to manage the complexity of highly parallel systems is central to really "intelligent" computing systems, and this fellow seems to done something important in that direction.

NEW YORK, March 16 (AScribe Newswire) -- 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.

Ascribe.org