# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

__Mittagsseminar Talk Information__ | |

**Date and Time**: Thursday, May 24, 2018, 12:15 pm

**Duration**: 30 minutes

**Location**: OAT S15/S16/S17

**Speaker**: Manuela Fischer

## Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Sublinear Memory per Machine

Recently, studying fundamental graph problems in the Massively Parallel Computation (MPC) framework, inspired by the MapReduce paradigm, has gained a lot of attention. A standard assumption, common to most traditional approaches, is to allow memory which is linear in the number n of nodes in the graph. However, as pointed out by Karloff et al. [SODA'10] and Czumaj et al. [arXiv:1707.03478], this might be unrealistic for real-world graphs.

We propose the study of a more practical variant of the MPC model which only requires substantially sublinear or even subpolynomial memory per machine. In contrast to the standard MPC model and also to the streaming model, in this low-memory MPC setting a single machine will never see all the nodes in the graph. We introduce a new technique to cope with this imposed locality.

In particular, we show that the Maximal Independent Set (MIS) problem can be solved efficiently, that is, in O(log^{3} log n) rounds, when the input graph is a tree. This substantially reduces the local memory from almost linear required by the recent O(log log n)-round MIS algorithm of Ghaffari et al. [PODC'18] to n^{ε}, and exponentially improves on the O(sqrt(log n) log log n)-algorithm by Lenzen and Wattenhofer [PODC'11] which can cope with sublinear memory.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login