ACM Group Honors Researchers Who Discovered Zig-Zag Graph That Improves Design of Robust Computer Networks

[May 19, 2009]

ACM Group Honors Researchers Who Discovered Zig-Zag Graph That Improves Design of Robust Computer Networks

NEW YORK, May 19, 2009 (ASCRIBE NEWS via COMTEX) -- ACM's Special Interest Group on Algorithms and Computing Theory (SIGACT) has recognized the contributions of three computer scientists who developed a new type of graph that enables the construction of large expander graphs, which play an important role in designing robust computer networks and constructing theories of error-correcting computer codes. Using the new zig-zag graph, this technique was able to solve one of the most intriguing open problems in computational complexity theory, that of detecting a path from one node to another in very small storage for undirected graphs (in which the nodes are connected by lines with no direction). Omer Reingold, Salil Vadhan, and Avi Wigderson will receive the 2009 Godel Prize, presented by SIGACT and the European Association for Theoretical Computer Science (EATCS), for outstanding papers in theoretical computer science at the ACM Symposium on the Theory of Computing (STOC) May 31 - June 2, in Bethesda, MD.

In a paper titled "Entropy Waves, the Zig-Zag Graph Product and New Constant Degree Expanders," Reingold, Vadhan, and Wigderson presented their research on a rich family of expander graphs, which are used for critical computer theory applications. These sparse but highly connected graphs were constructed using the zig-zag graph product. This new tool makes it possible to construct large expanders from smaller expanders while preserving degree and connectivity.

In a second paper titled "Undirected Connectivity in Log-Space," Reingold proved that connectivity in undirected graphs can be solved in logarithmic storage (i.e. enough storage to hold a constant number of pointers or counters stored elsewhere in the computer). The paper's key observation is that any connected graph is a very weak expander, but applying the zig-zag product makes it possible to turn the graph into an expander of only moderately large size. This solution had been possible using randomness but had not been accomplished with a deterministic algorithm, as Reingold demonstrated.

The findings of Reingold, Vadhan, and Wigderson were published in the Annals of Mathematics in 2002. The subsequent findings of Reingold on undirected connective in log-space where published in the Journal of ACM in 2007.

Omer Reingold is professor of computer science at the Weizmann Institute of Science. From 1999-2004, he was a member of AT&T Labs, and a visiting member of the School of Mathematics, Institute for Advanced Study in Princeton, NJ.

In 2005, he was the recipient of the ACM Grace Murray Hopper Award for "the outstanding young computer professional of the year." He completed a Ph.D. and pursued a short period of postdoctoral studies at the Weizmann Institute. He is a graduate of Tel-Aviv University with a B.Sc. in mathematics.

Salil Vadhan is Gordon McKay Professor of Computer Science and Applied Mathematics, and Director of the Center for Research on Computation and Society at Harvard University's School of Engineering and Applied Sciences. He was a visiting professor at the University of California Berkeley and a visiting member of the School of Mathematics, Institute for Advanced Study. He received a Ph.D. in applied mathematics from the Massachusetts Institute of Technology (MIT) and won the 2000 ACM Doctoral Dissertation award for his Ph.D. thesis. The recipient of a Certificate of Advanced Study in Mathematics from Churchill College, Cambridge University, he earned an A.B. in mathematics and computer science from Harvard University.

A professor at the School of Mathematics, Institute for Advanced Study since 1999, Avi Wigderson also taught at the Computer Science Institute, Hebrew University in Jerusalem from 1986 to 2003. He held visiting professor positions at the Institute for Advanced Study, Princeton University, and the Mathematical Sciences Research Institute, Berkeley, CA.

He is a recipient of the 1994 Nevanlinna Prize from the International Congress of Mathematicians in Zurich.

The Godel Prize, which includes an award of $5,000, is named in honor of Kurt Godel, who was born in Austria-Hungary (now the Czech Republic) in 1906. Godel's work has had immense impact upon scientific and philosophical thinking in the 20th century. The award recognizes his major contributions to mathematical logic and the foundations of computer science.

About ACM ACM, the Association for Computing Machinery (http://www.acm.org/), is the world's largest educational and scientific computing society, uniting computing educators, researchers and professionals to inspire dialogue, share resources and address the field's challenges. ACM strengthens the computing profession's collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.

About SIGACT The ACM Special Interest Group on Algorithms and Computation Theory (http://sigact.acm.org) fosters and promotes the discovery and dissemination of high quality research in the domain of theoretical computer science. The field includes algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.

About EATCS The European Association for Theoretical Computer Science (http://eatcs.org) is an international organization aimed at promoting research in the wide field of the foundations of computer science (ranging from formal languages, abstract computation models, algorithm design and complexity analysis, to applications of logic and semantics in programming). It facilitates the exchange of ideas and results among computer scientists, in particular through the organization of the annual International Conference on Automata, Languages and Programming (ICALP).

- - - - CONTACTS: Richard Ladner, ACM SIGACT, 206-543-9347, ladner@cs.washington.edu Virginia Gold, ACM, 212-626-0505, vgold@acm.org ((AScribe - The Public Interest Newswire / http://www.ascribe.org))

[ Back To TMCnet.com's Homepage ]