Fetching the paper…
Reading the bibliography…
Recently, studying fundamental graph problems in the \emph{Massively Parallel Computation (MPC) framework, inspired by the MapReduce paradigm, has gained a lot of attention.
A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem
Noga Alon, László Babai, and Alon Itai · 1986
Earlier work this paper cites.
Deterministic Coin Tossing and Accelerating Cascades: Micro and Macro Techniques for Designing Parallel Algorithms
Richard Cole and Uzi Vishkin · 1986
Earlier work this paper cites.
A Simple Parallel Algorithm for the Maximal Independent Set Problem
Michael Luby · 1986
Earlier work this paper cites.
An algorithmic approach to the Lovász local lemma
József Beck · 1991
Earlier work this paper cites.
Improved distributed algorithms for coloring and network decomposition problems
Alessandro Panconesi and Aravind Srinivasan · 1992
Earlier work this paper cites.
Mapreduce: simplified data processing on large clusters
Jeffrey Dean and Sanjay Ghemawat · 2008
Earlier work this paper cites.
A Model of Computation for MapReduce
Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii · 2010
Earlier work this paper cites.
Brief Announcement: Exponential Speed-Up of Local Algorithms Using Non-Local Communication
Christoph Lenzen and Roger Wattenhofer · 2010
Earlier work this paper cites.
Sorting, searching, and simulation in the mapreduce framework
Michael T Goodrich, Nodari Sitchinava, and Qin Zhang · 2011
Earlier work this paper cites.
Filtering: a method for solving graph problems in mapreduce
Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii · 2011
Earlier work this paper cites.
MIS on Trees
Christoph Lenzen and Roger Wattenhofer · 2011
Earlier work this paper cites.
Space-round tradeoffs for mapreduce computations
Andrea Pietracaprina, Geppino Pucci, Matteo Riondato, Francesco Silvestri, and Eli Upfal · 2012
Earlier work this paper cites.
Finding connected components in map-reduce in logarithmic rounds
Laukik Chitnis, Anish Das Sarma, Ashwin Machanavajjhala, and Vibhor Rastogi · 2013
Earlier work this paper cites.
Parallel algorithms for geometric graph problems
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev · 2014
Cited alongside, same era.
Skew in parallel query processing
Paul Beame, Paraschos Koutris, and Dan Suciu · 2014
Cited alongside, same era.
Space and time efficient parallel graph decomposition, clustering, and diameter approximation
Matteo Ceccarello, Andrea Pietracaprina, Geppino Pucci, and Eli Upfal · 2015
Cited alongside, same era.
Fast greedy algorithms in mapreduce and streaming
Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii, and Andrea Vattani · 2015
Cited alongside, same era.
The Locality of Distributed Symmetry Breaking
Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider · 2016
Cited alongside, same era.
An improved distributed algorithm for maximal independent set
Mohsen Ghaffari · 2016
Cited alongside, same era.
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
S. Assadi, X. Sun, and O. Weinstein · 2018
Closest in time.
Brief announcement: Semi-mapreduce meets congested clique
Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi · 2018
Closest in time.
Breaking the linear-memory barrier in mpc: Fast mis on trees with strongly sublinear memory
Sebastian Brandt, Manuela Fischer, and Jara Uitto · 2018
Closest in time.
Matching and MIS for uniformly sparse graphs in the low-memory MPC model
Sebastian Brandt, Manuela Fischer, and Jara Uitto · 2018
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Fast distributed algorithms for connectivity and mst in large graphs
Gopal Pandurangan, Peter Robinson, and Michele Scquizzato · 2016
Cited alongside, same era.
Shuffles and circuits:(on lower bounds for modern parallel computation)
Tim Roughgarden, Sergei Vassilvitskii, and Joshua R Wang · 2016
Cited alongside, same era.
Randomized composable coresets for matching and vertex cover
Sepehr Assadi and Sanjeev Khanna · 2017
Cited alongside, same era.
Simple round compression for parallel vertex cover
Sepehr Assadi · 2017
Cited alongside, same era.
Communication steps for parallel query processing
Paul Beame, Paraschos Koutris, and Dan Suciu · 2017
Cited alongside, same era.
Round compression for parallel matching algorithms
Artur Czumaj, Jakub Łacki, Aleksander Madry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski · 2017
Cited alongside, same era.
Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Zufan Zheng · 2018
Closest in time.
Improved massively parallel computation algorithms for mis, matching, and vertex cover
Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, and Ronitt Rubinfeld · 2018
Closest in time.
Round compression for parallel graph algorithms in strongly sublinear space
Krzysztof Onak · 2018
Closest in time.
Massively parallel algorithms and hardness for single-linkage clustering under l p l_{p} distances
Grigory Yaroslavtsev and Adithya Vadapalli · 2018
Closest in time.
Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein · 2019
Closest in time.
Massively parallel computation of matching and mis in sparse graphs
Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto · 2019
Closest in time.
personal communication, 2019
Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto · 2019
Closest in time.
Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
Mohsen Ghaffari and Jara Uitto · 2019
Closest in time.