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
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!


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: <>

More information about the theory-seminar mailing list