Communications of the ACM
ACM Group Honors Researchers Whose Zig-Zag Graph Aids Computer Network Designs
ACM's Special Interest Group on Algorithms and Computing Theory (SIGACT) and the European Association for Theoretical Computer Science have awarded the Godel Prize to Omer Reingold, Salil Vadhan, and Avi Wigderson for developing a new type of graph that enables the construction of large expander graphs, which are important in designing robust computer networks and constructing theories of error-correcting computer codes. The new zig-zag graph was able to help solve the problem of detecting a path from one node to another in very small storage for undirected graphs.
In their paper, "Entropy Waves, the Zig-Zag Graph Product and New Constant Degree Expanders," Reingold, Vadhan, and Wigderson discussed their research on a family of expander graphs, which are used for critical computer theory applications. The sparse but highly connected expander graphs were constructed using the zig-zag graph method, which enables the construction of large expanders from smaller expanders while preserving degree and connectivity.
In a second paper, "Undirected Connectivity in Log-Space," Reingold proved that connectivity in undirected graphs can be solved in logarithmic storage, and that any connected graph is a very weak expander, but applying the zig-zag method makes it possible to turn the graph into an expander of only moderately large size.
Omer Reingold is a professor of computer science at the Weizmann Institute of Science, Salil Vadhan is a professor of computer science and applied mathematics at Harvard University's School of Engineering and Applied Sciences, and Avi Wigderson is a professor at the School of Mathematics, Institute for Advanced Study. The Godel Prize, which includes an award of $5,000, is named after Kurt Godel in recognition of his major contributions to mathematical logic and the foundations of computer science.
From AScribe Newswire
View Full Article
Abstracts Copyright © 2009 Information Inc., Bethesda, Maryland, USA 
No entries found