ACM SIGACT Honors Researchers' Contribution to Design of Robust Computer Networks

Awarded for Advances in Constructing and Applying Efficient Expander Graphs that Help Resolve Complex Computing Issues

acm
Association for Computing Machinery
Advancing Computing as a Science & Profession

Contacts:

Richard Ladner				Virginia Gold
ACM SIGACT Chair				ACM
206-543-9347				212-626-0505
[email protected]				[email protected]

NEW YORK, May 18, 2009 – 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 product, 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 Gödel 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 2009, http://www.umiacs.umd.edu/conferences/stoc2009/) May 31 to 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 Gödel Prize, which includes an award of $5,000, is named in honor of Kurt Gödel, who was born in Austria-Hungary (now the Czech Republic) in 1906. Gödel's work has had immense impact upon scientific and philosophical thinking in the 20^th century. The award recognizes his major contributions to mathematical logic and the foundations of computer science.

About ACM

ACM, the Association for Computing Machinery 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).