Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Seminar (11/2): Rotem Oshman

Ofir Geri ofirgeri at stanford.edu
Wed Oct 31 16:19:35 PDT 2018


Hi all,


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!

Ofir


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...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20181031/5c97299e/attachment.html>


More information about the theory-seminar mailing list