Omer Angel
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Omer Angel has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Itai Benjamini
Weizmann Institute of Science
2 shared publications - Eran O. Ofek
Weizmann Institute of Science
1 shared publication - Udi Wieder
Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot 76100 Israel
1 shared publication
Latest Publications
- 1 November 2007
- Published by Springer Nature in Combinatorica
- Vol. 27 (6) , 645-658
A phase transition for the metric distortion of percolation on the hypercube
- 1 November 2007
- Published by Springer Nature in Combinatorica
- Vol. 27 (6) , 645-658
A phase transition for the metric distortion of percolation on the hypercube
- 9 March 2007
- Published by Wiley in Random Structures & Algorithms
- Vol. 32 (1) , 71-87
Routing complexity of faulty networks
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This article investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability, which permits routing both for the hypercube and for thed‐dimensional mesh. We use tools from percolation theory to show that in thed‐dimensional mesh, once a giant component appears—efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location than that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graphGn,p. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008
- 9 March 2007
- Published by Wiley in Random Structures & Algorithms
- Vol. 32 (1) , 71-87
Routing complexity of faulty networks
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This article investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability, which permits routing both for the hypercube and for thed‐dimensional mesh. We use tools from percolation theory to show that in thed‐dimensional mesh, once a giant component appears—efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location than that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graphGn,p. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008