Tata Institute of Fundamental Research
Algebraic Methods in Distributed Graph Algorithms
STCS Seminar
Speaker:
Ami Paz (Technion Israel Institute of Technology
Department of Computer Science
Haifa 3200
Israel)
Organiser:
Kavitha Telikepalli
Date:
Tuesday, 15 Sep 2015, 16:00 to 17:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: We consider a computer network, represented by a communication graph: each node represents a processor and the communication is done synchronously along the edges. Can such a network compute its own graph's properties? E.g., how hard is it to list all the triangles in the graph, to find its shortest cycle, or to compute all-pairs shortest paths?
We will give an introduction to the relevant computation models. Then, we will discuss some recent results showing how to solve these problems faster using algebraic techniques (based on a joint work with Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen and Jukka Suomela).
| Speaker: | Ami Paz (Technion Israel Institute of Technology Department of Computer Science Haifa 3200 Israel) |
| Organiser: | Kavitha Telikepalli |
| Date: | Tuesday, 15 Sep 2015, 16:00 to 17:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: We consider a computer network, represented by a communication graph: each node represents a processor and the communication is done synchronously along the edges. Can such a network compute its own graph's properties? E.g., how hard is it to list all the triangles in the graph, to find its shortest cycle, or to compute all-pairs shortest paths?
We will give an introduction to the relevant computation models. Then, we will discuss some recent results showing how to solve these problems faster using algebraic techniques (based on a joint work with Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen and Jukka Suomela).
We will give an introduction to the relevant computation models. Then, we will discuss some recent results showing how to solve these problems faster using algebraic techniques (based on a joint work with Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen and Jukka Suomela).