Fetching the paper…
Reading the bibliography…
We introduce a method for sparsifying distributed algorithms and exhibit how it leads to improvements that go past known barriers in two algorithmic settings of large-scale graph processing: Massively Parallel Computation (MPC), and Local Computation Algorithms (LCA).
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.
A fast and simple randomized parallel algorithm for maximal matching
Amos Israeli and Alon Itai · 1986
Earlier work this paper cites.
A simple parallel algorithm for the maximal independent set problem
Michael Luby · 1986
Earlier work this paper cites.
Distributive graph algorithms-global solutions from local data
Nathan Linial · 1987
Earlier work this paper cites.
Equitable coloring extends chernoff-hoeffding bounds
Sriram V. Pemmaraju · 2001
Earlier work this paper cites.
MapReduce: Simplified data processing on large clusters
Jeffrey Dean and Sanjay Ghemawat · 2004
Earlier work this paper cites.
Finding graph matchings in data streams
Andrew McGregor · 2005
Earlier work this paper cites.
Dryad: Distributed data-parallel programs from sequential building blocks
Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly · 2007
Earlier work this paper cites.
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
Michal Parnas and Dana Ron · 2007
Earlier work this paper cites.
A model of computation for MapReduce
Howard J. 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.
Maintaining a large matching and a small vertex cover
Krzysztof Onak and Ronitt Rubinfeld · 2010
Earlier work this paper cites.
Spark: Cluster computing with working sets
Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica · 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.
Fast local computation algorithms
Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie · 2011
Cited alongside, same era.
Space-efficient local computation algorithms
Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie · 2012
Cited alongside, same era.
Hadoop: The Definitive Guide
Tom White · 2012
Cited alongside, same era.
Communication steps for parallel query processing
Paul Beame, Paraschos Koutris, and Dan Suciu · 2013
Cited alongside, same era.
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.
Coresets meet edcs: algorithms for matching and vertex cover on massive graphs
Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein · 2017
Later among the works it cites.
Simple round compression for parallel vertex cover
Sepehr Assadi · 2017
Later among the works it cites.
Distributed MIS via all-to-all communication
Mohsen Ghaffari · 2017
Later among the works it cites.
Efficient massively parallel methods for dynamic programming
Sungjin Im, Benjamin Moseley, and Xiaorui Sun · 2017
Later among the works it cites.
A (centralized) local guide
Reut Levi, Moti Medina, et al · 2017
Later among the works it cites.
Local computation algorithms for graphs of non-constant degrees
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Guy Even, Moti Medina, and Dana Ron · 2014
Cited alongside, same era.
Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints
Kook Jin Ahn and Sudipto Guha · 2015
Cited alongside, same era.
Lessons from the congested clique applied to mapreduce
James W Hegeman and Sriram V Pemmaraju · 2015
Cited alongside, same era.
Improved distributed approximate matching
Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie · 2015
Cited alongside, same era.
An improved distributed algorithm for maximal independent set
Mohsen Ghaffari · 2016
Cited alongside, same era.
Local computation: Lower and upper bounds
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer · 2016
Cited alongside, same era.
Reut Levi, Ronitt Rubinfeld, and Anak Yodpinyanee · 2017
Later among the works it cites.
Parallel graph connectivity in log diameter rounds
Alexandr Andoni, Clifford Stein, Zhao Song, Zhengyu Wang, and Peilin Zhong · 2018
Closest in time.
Massively parallel algorithms for finding well-connected components in sparse graphs
Sepehr Assadi, Xiaorui Sun, and Omri Weinstein · 2018
Closest in time.
Approximating edit distance in truly subquadratic time: quantum and mapreduce
Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi HajiAghayi, and Saeed Seddighin · 2018
Closest in time.
Sebastian Brandt, Manuela Fischer, and Jara Uitto · 2018
Closest in time.
Matching and mis for uniformly sparse graphs in MPC with low memory
Sebastian Brandt, Manuela Fischer, and Jara Uitto · 2018
Closest in time.
Round compression for parallel matching algorithms
Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski · 2018
Closest in time.
Improved massively parallel computation algorithms for mis, matching, and vertex cover
Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, and Ronitt Rubinfeld · 2018
Closest in time.
Greedy and local ratio algorithms in the mapreduce model
Nicholas JA Harvey, Christopher Liaw, and Paul Liu · 2018
Closest in time.