Search Mailing List Archives
[theory-seminar] Theory Seminar (11/2): Rotem Oshman
ofirgeri at stanford.edu
Wed Oct 31 16:19:35 PDT 2018
This Friday in theory seminar, Rotem Oshman (Tel-Aviv University) will give a talk on Two Open Problems in Distributed Graph Algorithms (see abstract below). The talk will be at 3pm in Gates 392 - please note the unusual location!
Hope to see you there!
Two Open Problems in Distributed Graph Algorithms
Speaker: Rotem Oshman (Tel-Aviv University)
In a distributed graph algorithm, we have a network of computing nodes, where each node initially knows only its own local neighborhood; the nodes communicate over the network edges in order to solve some problem on the network graph. We are interested in algorithms that are fast, but also do not require a lot of communication between the network nodes.
In this talk I will describe recent algorithms and lower bounds for two graph problems: exact maximum bipartite matching, and testing whether the network contains an even-length cycle of a specific length. Both problems do not have matching upper and lower bounds, so their complexity remains open. The talk will not assume any prior knowledge about distributed computing.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar