Fetching the paper…
Reading the bibliography…
This paper proves strong lower bounds for distributed computing in the CONGEST model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts.
Some complexity questions related to distributive computing (preliminary report)
Andrew Chi-Chih Yao · 1979
Earlier work this paper cites.
Deterministic coin tossing with applications to optimal parallel list ranking
Richard Cole and Uzi Vishkin · 1986
Earlier work this paper cites.
Locality in distributed graph algorithms
Nathan Linial · 1992
Earlier work this paper cites.
On the distributional complexity of disjointness
Alexander A. Razborov · 1992
Earlier work this paper cites.
A primal-dual parallel approximation technique applied to weighted set and vertex covers
Samir Khuller, Uzi Vishkin, and Neal E. Young · 1994
Earlier work this paper cites.
Communication Complexity
Eyal Kushilevitz and Noam Nisan · 1997
Earlier work this paper cites.
Computing on data streams
Monika Rauch Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan · 1998
Earlier work this paper cites.
Distributed Computing: A Locality-Sensitive Approach
David Peleg · 2000
Earlier work this paper cites.
A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
David Peleg and Vitaly Rubinovich · 2000
Earlier work this paper cites.
On the distributed complexity of computing maximal matchings
Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi · 2001
Earlier work this paper cites.
Some simple distributed algorithms for sparse networks
Alessandro Panconesi and Romeo Rizzi · 2001
Earlier work this paper cites.
Reductions in streaming algorithms, with an application to counting triangles in graphs
Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar · 2002
Earlier work this paper cites.
Distributed approximation: a survey
Michael Elkin · 2004
Earlier work this paper cites.
On graph problems in a semi-streaming model
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang · 2005
Earlier work this paper cites.
Data streams: Algorithms and applications
S. Muthukrishnan · 2005
Earlier work this paper cites.
An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem
Michael Elkin · 2006
Earlier work this paper cites.
The price of being near-sighted
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer · 2006
Earlier work this paper cites.
Estimating clustering indexes in data streams
Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, and Christian Sohler · 2007
Earlier work this paper cites.
Streaming algorithm for graph spanners - single pass and constant processing time per edge
Surender Baswana · 2008
Earlier work this paper cites.
Mining large networks with subgraph counting
Ilaria Bordino, Debora Donato, Aristides Gionis, and Stefano Leonardi · 2008
Earlier work this paper cites.
Fast distributed approximations in planar graphs
Andrzej Czygrinow, Michal Hanckowiak, and Wojciech Wawrzyniak · 2008
Earlier work this paper cites.
Distributed weighted vertex cover via maximal matchings
Fabrizio Grandoni, Jochen Könemann, and Alessandro Panconesi · 2008
Earlier work this paper cites.
A primal-dual bicriteria distributed algorithm for capacitated vertex cover
Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, and Mauro Sozio · 2008
Earlier work this paper cites.
Leveraging linial’s locality limit
Christoph Lenzen and Roger Wattenhofer · 2008
Earlier work this paper cites.
Coloring unstructured radio networks
Thomas Moscibroda and Roger Wattenhofer · 2008
Earlier work this paper cites.
Graph sparsification in the semi-streaming model
Kook Jin Ahn and Sudipto Guha · 2009
Earlier work this paper cites.
A local 2-approximation algorithm for the vertex cover problem
Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto · 2009
Earlier work this paper cites.
Distributed computing with advice: information sensitivity of graph coloring
Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc · 2009
Earlier work this paper cites.
Distributed and parallel algorithms for weighted vertex cover and other covering problems
Christos Koufogiannakis and Neal E. Young · 2009
Earlier work this paper cites.
A simple local 3-approximation algorithm for vertex cover
Valentin Polishchuk and Jukka Suomela · 2009
Cited alongside, same era.
Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
Matti Åstrand and Jukka Suomela · 2010
Cited alongside, same era.
Deterministic distributed vertex coloring in polylogarithmic time
Leonid Barenboim and Michael Elkin · 2011
Cited alongside, same era.
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
Michael Elkin · 2011
Cited alongside, same era.
Approximate counting of cycles in streams
Madhusudan Manjunath, Kurt Mehlhorn, Konstantinos Panagiotou, and He Sun · 2011
Cited alongside, same era.
A tight unconditional lower bound on distributed randomwalk computation
Danupon Nanongkai, Atish Das Sarma, and Gopal Pandurangan · 2011
Streaming lower bounds for approximating MAX-CUT
Michael Kapralov, Sanjeev Khanna, and Madhu Sudan · 2015
Later among the works it cites.
Fast partial distance estimation and applications
Christoph Lenzen and Boaz Patt-Shamir · 2015
Later among the works it cites.
The graph structure in the web - analyzed on different aggregation levels
Robert Meusel, Sebastiano Vigna, Oliver Lehmberg, and Christian Bizer · 2015
Later among the works it cites.
Distributed coloring algorithms for triangle-free graphs
Seth Pettie and Hsin-Hao Su · 2015
Later among the works it cites.
Near-linear lower bounds for distributed distance computations, even in sparse networks
Amir Abboud, Keren Censor-Hillel, and Seri Khoury · 2016
Later among the works it cites.
Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs
Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang · 2016
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Distributed coloring depending on the chromatic number or the neighborhood growth
Johannes Schneider and Roger Wattenhofer · 2011
Cited alongside, same era.
On the locality of some NP-complete problems
Leonid Barenboim · 2012
Cited alongside, same era.
Networks cannot compute their diameter in sublinear time
Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer · 2012
Cited alongside, same era.
Streaming and communication complexity of clique approximation
Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy, and Chengu Wang · 2012
Cited alongside, same era.
Optimal distributed all pairs shortest paths and applications
Stephan Holzer and Roger Wattenhofer · 2012
Cited alongside, same era.
Distributed algorithms for network diameter and girth
David Peleg, Liam Roditty, and Elad Tal · 2012
Cited alongside, same era.
Later among the works it cites.
Deterministic (
Leonid Barenboim · 2016
Later among the works it cites.
The locality of distributed symmetry breaking
Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider · 2016
Later among the works it cites.
Brief announcement: Local independent set approximation
Marijke H. L. Bodlaender, Magnús M. Halldórsson, Christian Konrad, and Fabian Kuhn · 2016
Later among the works it cites.
New bounds for approximating extremal distances in undirected graphs
Massimo Cairo, Roberto Grossi, and Romeo Rizzi · 2016
Later among the works it cites.
An exponential separation between randomized and deterministic complexity in the LOCAL model
Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie · 2016
Later among the works it cites.
Local conflict coloring
Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski · 2016
Later among the works it cites.
Streaming algorithms for independent sets in sparse hypergraphs
Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, and Mario Szegedy · 2016
Later among the works it cites.
Distributed (
David G. Harris, Johannes Schneider, and Hsin-Hao Su · 2016
Later among the works it cites.
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai · 2016
Later among the works it cites.
Brief announcement: A tight distributed algorithm for all pairs shortest paths and applications
Qiang-Sheng Hua, Haoqiang Fan, Lixiang Qian, Ming Ai, Yangyang Li, Xuanhua Shi, and Hai Jin · 2016
Later among the works it cites.
Local computation: Lower and upper bounds
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer · 2016
Later among the works it cites.
Distributed approximation of maximum independent set and maximum matching
Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman · 2017
Later among the works it cites.
Quadratic and near-quadratic lower bounds for the CONGEST model
Keren Censor-Hillel, Seri Khoury, and Ami Paz · 2017
Later among the works it cites.
A time hierarchy theorem for the LOCAL model
Yi-Jun Chang and Seth Pettie · 2017
Later among the works it cites.
Distributed exact shortest paths in sublinear time
Michael Elkin · 2017
Later among the works it cites.
Distributed coloring in sparse graphs with fewer colors
Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, and Louis Esperet · 2018
Later among the works it cites.
A faster deterministic distributed algorithm for weighted apsp through pipelining
Udit Agarwal and Vijaya Ramachandran · 2018
Later among the works it cites.
Suman Kalyan Bera and Prantar Ghosh · 2018
Later among the works it cites.
Distributed exact weighted all-pairs shortest paths in near-linear time
Aaron Bernstein and Danupon Nanongkai · 2018
Later among the works it cites.
New bounds for the CLIQUE-GAP problem using graph decomposition theory
Vladimir Braverman, Zaoxing Liu, Tejasvam Singh, N. V. Vinodchandran, and Lin F. Yang · 2018
Later among the works it cites.
Distributed construction of purely additive spanners
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, and Amir Yehudayoff · 2018
Later among the works it cites.
Optimal distributed coloring algorithms for planar graphs in the LOCAL model
Shiri Chechik and Doron Mukhtar · 2018
Later among the works it cites.
Approximating the caro-wei bound for independent sets in graph streams
Graham Cormode, Jacques Dark, and Christian Konrad · 2018
Later among the works it cites.