Theory Seminar, Wednesday Feb 21: Orr Fischer (Weizmann) - Massively Parallel Computation in a Heterogeneous Regime: One Strong Machine Makes a Big Difference

[Arnold Filtser]

Hi all,

Next week (Wed Feb 21, at 12:00) we will meet for our theory seminar.

Location: Building 503 room 226.

See you all there,

Arnold and Talya

https://theory.cs.biu.ac.il/

Speaker: Orr Fischer (Weizmann)
Title: Massively Parallel Computation in a Heterogeneous Regime: One Strong Machine Makes a Big Difference
Abstract: Massively-parallel graph algorithms have received extensive attention over the past decade, with research focusing on three memory regimes: the superlinear regime, the near-linear regime, and the sublinear regime. The sublinear regime is the most desirable in practice, but conditional hardness results point towards its limitations. In particular, the ``2-vs-1 cycle'' problem, where we are asked to distinguish between a graph that is a single large cycle and graphs that are comprised of two cycles, is conjectured to require Ω(log(n)) rounds. Based on this conjecture and a connection to local distributed algorithms, several conditional hardness results have been shown for sublinear MPC.

In this talk we discuss a heterogeneous setting created by adding a single near-linear space machine to the sublinear MPC regime, and show that this small alteration suffices to circumvent most of the conditional hardness results of the sublinear regime. The starting point of this work is the simple observation that the ``2-vs-1 cycle'' problem becomes trivial if we have even a single machine with near-linear memory. This motivates us to ask whether the problems whose conditional hardness rests on the hardness of the ``2-vs-1 cycle'' problem --- connectivity, minimum-weight spanning tree, maximal matching, and others --- also become easy given a single of large machine.

We will review the known results in this model, discuss which types of techniques work well in this model, and share some of the many open problems in the field.

[Arnold Filtser]

The seminar starts in one hour!