Omer Reingold
Encyclopedia
Omer Reingold is a faculty member of the Foundations of Computer Science
Group at the Weizmann Institute of Science
, Israel
. He received the 2005 Grace Murray Hopper Award
for his work in finding a deterministic logarithmic-space
algorithm for ST-connectivity
in undirected graphs
. He, along with Avi Wigderson
and Salil Vadhan
, won the Gödel Prize
(2009) for their work on the zig-zag product
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
Group at the Weizmann Institute of Science
Weizmann Institute of Science
The Weizmann Institute of Science , known as Machon Weizmann, is a university and research institute in Rehovot, Israel. It differs from other Israeli universities in that it offers only graduate and post-graduate studies in the sciences....
, Israel
Israel
The State of Israel is a parliamentary republic located in the Middle East, along the eastern shore of the Mediterranean Sea...
. He received the 2005 Grace Murray Hopper Award
Grace Murray Hopper Award
The original Grace Murray Hopper Awards have been awarded by the Association for Computing Machinery since 1971. The award goes to a young computer professional who makes a single, significant technical or service contribution.-Recipients:* 1971 Donald E. Knuth* 1972 Paul H. Dirksen* 1972 Paul H...
for his work in finding a deterministic logarithmic-space
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
algorithm for ST-connectivity
ST-connectivity
In computer science and computational complexity theory, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s.Formally, the decision problem is given by- Complexity :...
in undirected graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
. He, along with Avi Wigderson
Avi Wigderson
Avi Wigderson is an Israeli mathematician and computer scientist, a professor of mathematics at the Institute for Advanced Study in Princeton. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural...
and Salil Vadhan
Salil Vadhan
Salil Vadhan is Vicky Joseph Professor of Computer Science and Applied Mathematics at Harvard University. He obtained his PhD in Applied Mathematics from Massachusetts Institute of Technology in 1999, where his advisor was Shafi Goldwasser. His research centers around the interface between...
, won the Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
(2009) for their work on the zig-zag product
Zig-zag product
In graph theory, the zig-zag product of regular graphs G,H, denoted by G \circ H, takes a large graph and a small graph , and produces a graph that approximately inherits the size of the large one but the degree of the small one...
.