|
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 ]
|
Internet Telephony Magazine
Click here to read latest issue
CUSTOMER 
Cloud Computing Magazine
Click here to read latest issue
IoT EVOLUTION MAGAZINE
