pith. sign in

arxiv: 2606.03674 · v1 · pith:4TPUE4DBnew · submitted 2026-06-02 · 💻 cs.DS · cs.DC

Deterministic Distance Approximation in MPC via Improved Hitting Sets

Kyungjin Cho , Michal Dory , Yannic Maus , Tijn de Vos This is my paper

Pith reviewed 2026-06-28 07:54 UTC · model grok-4.3

classification 💻 cs.DS cs.DC
keywords deterministic algorithmsMPCspannersapproximate shortest pathshitting setsderandomizationCongested Clique
0
0 comments X

The pith

Deterministic hitting sets replace randomized sampling to match sublogarithmic round bounds for spanners and approximate shortest paths in MPC models.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper isolates the randomized sampling steps inside existing algorithms for spanners and approximate shortest paths, then replaces each step with a deterministic hitting-set construction that runs inside the same MPC model. This produces the first deterministic algorithms whose round complexity stays sublogarithmic and whose stretch and size guarantees stay identical to the best randomized algorithms. The approach works across linear MPC, sublinear MPC, near-linear MPC, and the Congested Clique. A reader would care because these primitives are building blocks for large-scale distance computation, and the deterministic versions remove dependence on randomness while keeping the same efficiency.

Core claim

By developing a versatile deterministic hitting-set algorithm that can be implemented inside the target MPC models, the randomized sampling routines used for spanner construction and distance approximation can be derandomized without incurring any extra rounds, yielding O(k)-stretch spanners of size O(n^{1+1/k}) in O(1) rounds in linear MPC and Congested Clique, O(k^{1+ε})-stretch spanners in O(log k) rounds in sublinear MPC, O(1)-approximate APSP in O(log log log n) rounds in Congested Clique, and (1+ε)-approximate SSSP together with O(1)-approximate APSP in polylog log n rounds in near-linear MPC.

What carries the argument

The versatile deterministic hitting-set algorithm that derandomizes the sampling routines of prior randomized spanner and shortest-path algorithms while preserving their exact round bounds inside each MPC model.

If this is right

  • O(k)-stretch spanners of size O(n^{1+1/k}) become available in O(1) rounds in both linear MPC and Congested Clique for any k.
  • O(k^{1+ε})-stretch spanners of the same size become available in O(log k) rounds in sublinear MPC.
  • O(1)-approximate all-pairs shortest paths become available in O(log log log n) rounds in the Congested Clique.
  • Near-linear MPC obtains (1+ε)-approximate single-source shortest paths and O(1)-approximate all-pairs shortest paths for unweighted graphs in polylog log n rounds using only one near-linear memory machine.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same hitting-set primitive may let other sampling-based randomized algorithms in MPC and Congested Clique be derandomized without round overhead.
  • If the hitting-set technique extends to weighted graphs or directed graphs, further distance problems could receive deterministic sublogarithmic-round solutions.
  • The single near-linear machine requirement in the near-linear MPC result suggests that memory heterogeneity can be exploited more broadly once deterministic primitives are available.

Load-bearing premise

The deterministic hitting-set construction can be carried out inside the target MPC models without using more rounds than the original randomized sampling routines.

What would settle it

An explicit lower-bound proof or concrete implementation showing that any deterministic hitting set of the required size and quality needs strictly more rounds than the randomized sampling step in linear MPC or the Congested Clique.

read the original abstract

In this paper, we provide the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various MPC models. Moreover, we significantly improve upon the state of the art in the deterministic Congested Clique. In particular, we obtain the following four results on undirected graphs: 1. In both linear MPC and Congested Clique, we obtain an $O(k)$ stretch-spanner of a weighted graph of size $O(n^{1+1/k})$ in $O(1)$ rounds, for some parameter $k\ge 0$. For $k=O(\log{n})$, this leads to an $O(\log n)$ approximation of APSP in constant rounds in both models. 2. In sublinear MPC, we obtain an $O(k^{1+\varepsilon})$-stretch spanner of a weighted graph of size $O(n^{1+1/k})$ in $O(\log k)$ rounds, for any fixed constant $\varepsilon>0$. 3. In Congested Clique, we obtain $O(1)$-approximate APSP for weighted graphs in $O(\log \log \log n)$ rounds. 4. In near-linear MPC, we obtain $(1+\varepsilon)$-approximate single-source shortest paths and $O(1)$-approximate all-pairs shortest paths for unweighted graphs in $\textsf{poly}\log \log n$ rounds. Our algorithm only requires a single near-linear memory machine, where the rest can have sublinear memory. Our deterministic algorithms obtain similar guarantees to the state of the art randomized algorithms without incurring additional factors in the round complexity. To obtain these results, we inspect the randomized algorithms and isolate a randomized sampling routine. Then we derandomize these sampling routines by using a deterministic hitting set. Hereto, we develop a versatile deterministic hitting set algorithm, which we hope will have further derandomization applications.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to deliver the first deterministic sublogarithmic-round algorithms for spanners and approximate shortest paths in linear MPC, sublinear MPC, Congested Clique, and near-linear MPC. It isolates randomized sampling steps from prior algorithms and replaces them with a new deterministic hitting-set primitive, yielding an O(k)-stretch spanner of size O(n^{1+1/k}) in O(1) rounds (linear MPC/CC), an O(k^{1+ε})-stretch spanner in O(log k) rounds (sublinear MPC), O(1)-approx APSP in O(log log log n) rounds (CC), and polyloglog n rounds for (1+ε)-SSSP / O(1)-APSP (near-linear MPC), all matching the round complexity of the best randomized algorithms.

Significance. If the central claims hold, the work supplies the first deterministic sublogarithmic-round distance-approximation results in these models and improves the deterministic Congested Clique state of the art. The versatile deterministic hitting-set construction is presented as a reusable primitive that may enable further derandomizations; explicit credit is due for the parameter-free matching of randomized round bounds and for the explicit four-model result list.

major comments (2)
  1. [Abstract (derandomization paragraph)] Abstract (derandomization paragraph) and the MPC implementation section: the claim that the deterministic hitting-set routine replaces randomized sampling while preserving exact round bounds (O(1) in linear MPC/CC, O(log k) in sublinear MPC) is load-bearing for all four results. The paper must exhibit the precise communication pattern, per-machine memory, and iteration count of the hitting-set construction to confirm that no hidden coordination or verification rounds are introduced.
  2. [Result 3] Result 3 (Congested Clique O(log log log n) APSP): the reduction from the hitting-set primitive to the final round bound must be spelled out with an explicit round-complexity calculation; any logarithmic overhead in the hitting-set phase would invalidate the stated O(log log log n) bound.
minor comments (2)
  1. Notation for the hitting-set size bound should be introduced once and used consistently across the four results.
  2. The abstract states four numbered results; the corresponding theorem statements in the body should carry matching numbering for easy cross-reference.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the careful review and constructive comments. We address the major comments point-by-point below. The requested clarifications on the hitting-set construction and round-complexity calculations can be incorporated directly into the manuscript.

read point-by-point responses

  1. Referee: [Abstract (derandomization paragraph)] Abstract (derandomization paragraph) and the MPC implementation section: the claim that the deterministic hitting-set routine replaces randomized sampling while preserving exact round bounds (O(1) in linear MPC/CC, O(log k) in sublinear MPC) is load-bearing for all four results. The paper must exhibit the precise communication pattern, per-machine memory, and iteration count of the hitting-set construction to confirm that no hidden coordination or verification rounds are introduced.

    Authors: We agree that the precise implementation details are essential to validate the round bounds. In the revised version we will insert a dedicated subsection (in the MPC implementation section) that explicitly lists: (i) the per-iteration communication pattern among machines, (ii) the memory footprint per machine, and (iii) the exact number of iterations of the deterministic hitting-set routine. This exposition will confirm that the construction integrates into the existing algorithms without introducing extra coordination or verification rounds, thereby preserving the stated O(1) and O(log k) bounds. revision: yes

  2. Referee: [Result 3] Result 3 (Congested Clique O(log log log n) APSP): the reduction from the hitting-set primitive to the final round bound must be spelled out with an explicit round-complexity calculation; any logarithmic overhead in the hitting-set phase would invalidate the stated O(log log log n) bound.

    Authors: We will add an explicit, step-by-step round-complexity calculation immediately following the description of Result 3. The calculation will enumerate each phase of the APSP algorithm, show precisely where and how many times the hitting-set primitive is invoked, and demonstrate that the total remains O(log log log n) with no hidden logarithmic factor from the derandomization. This will make the reduction fully transparent. revision: yes

Circularity Check

0 steps flagged

No circularity; new hitting-set construction supplies independent derandomization primitive

full rationale

The paper isolates randomized sampling steps from prior algorithms and replaces them with a newly developed deterministic hitting-set routine whose MPC implementation is presented as preserving the original round bounds. No equations, parameters, or central claims reduce by construction to fitted inputs, self-citations, or renamed known results. The derivation chain is therefore self-contained against external randomized baselines and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard graph-theoretic definitions of stretch and spanner size plus the assumption that the new deterministic hitting-set algorithm can be realized inside the MPC communication model without increasing round count. No free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math Undirected weighted graphs admit spanners of size O(n^{1+1/k}) with stretch O(k)
    Invoked as the target output of the spanner construction in all four results.
  • domain assumption Randomized sampling routines for hitting sets can be replaced by deterministic constructions while preserving round complexity in MPC
    Core premise of the derandomization approach stated in the abstract.

pith-pipeline@v0.9.1-grok · 5892 in / 1323 out tokens · 20463 ms · 2026-06-28T07:54:17.345620+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

96 extracted references · 24 canonical work pages

  1. [1]

    Optimal deterministic routing and sorting on the congested clique , booktitle =

    Christoph Lenzen , editor =. Optimal deterministic routing and sorting on the congested clique , booktitle =. 2013 , url =. doi:10.1145/2484239.2501983 , eprinttype =

    work page doi:10.1145/2484239.2501983 2013

  2. [2]

    1989 , publisher=

    The probabilistic method yields deterministic parallel algorithms , author=. 1989 , publisher=

    1989

  3. [3]

    Distributed Comput

    Orr Fischer and Adi Horowitz and Rotem Oshman , title =. Distributed Comput. , volume =. 2025 , url =. doi:10.1007/S00446-025-00479-7 , note =

    work page doi:10.1007/s00446-025-00479-7 2025

  4. [4]

    CoRR , volume =

    Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi , title =. CoRR , volume =. 2018 , url =

    2018

  5. [5]

    Improved All-Pairs Approximate Shortest Paths in Congested Clique , booktitle =

    Hong Duc Bui and Shashwat Chandra and Yi. Improved All-Pairs Approximate Shortest Paths in Congested Clique , booktitle =. 2024 , url =. doi:10.1145/3662158.3662804 , eprinttype =

    work page doi:10.1145/3662158.3662804 2024

  6. [6]

    Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Near-Optimal Spanners for General Graphs in (Nearly) Linear Time , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

    2022

  7. [7]

    ACM Transactions on Algorithms (TALG) , volume=

    Efficient algorithms for constructing very sparse spanners and emulators , author=. ACM Transactions on Algorithms (TALG) , volume=. 2018 , publisher=. 1607.08337 , note =

    Pith/arXiv arXiv 2018

  8. [8]

    Theoretical Computer Science , volume=

    Constructing light spanners deterministically in near-linear time , author=. Theoretical Computer Science , volume=. 2022 , publisher=. 1709.01960 , note =

    arXiv 2022

  9. [9]

    1975 , issn =

    On the ratio of optimal integral and fractional covers , journal =. 1975 , issn =. doi:https://doi.org/10.1016/0012-365X(75)90058-8 , url =

    work page doi:10.1016/0012-365x(75)90058-8 1975

  10. [10]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Improved distributed network decomposition, hitting sets, and spanners, via derandomization , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  11. [11]

    Proceedings of the tenth annual ACM symposium on Theory of computing , pages=

    Parallelism in random access machines , author=. Proceedings of the tenth annual ACM symposium on Theory of computing , pages=

  12. [12]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

    Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  13. [13]

    Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    A deterministic algorithm for the MST problem in constant rounds of congested clique , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=. 2021 , eprinttype =

    2021

  14. [14]

    Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing , pages=

    Communication-efficient parallel sorting (preliminary version) , author=. Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing , pages=

  15. [15]

    Journal of the ACM (JACM) , volume=

    Approximate distance oracles , author=. Journal of the ACM (JACM) , volume=. 2005 , publisher=

    2005

  16. [16]

    International Symposium on Algorithms and Computation , pages=

    Sorting, searching, and simulation in the mapreduce framework , author=. International Symposium on Algorithms and Computation , pages=. 2011 , organization=

    2011

  17. [17]

    Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures , pages=

    Massively parallel algorithms for approximate shortest paths , author=. Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures , pages=. 2024 , eprinttype =

    2024

  18. [18]

    34th International Symposium on Distributed Computing , year=

    Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs , author=. 34th International Symposium on Distributed Computing , year=

  19. [19]

    Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing , pages=

    Constant-round near-optimal spanners in congested clique , author=. Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing , pages=

    2022

  20. [20]

    2017 , publisher=

    Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis , author=. 2017 , publisher=

    2017

  21. [21]

    2022 , url =

    Dean Leitersdorf , title =. 2022 , url =

    2022

  22. [22]

    Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs , booktitle =

    Manuela Fischer and Jeff Giliberti and Christoph Grunau , editor =. Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs , booktitle =. 2023 , url =. doi:10.1145/3558481.3591081 , eprinttype =

    work page doi:10.1145/3558481.3591081 2023

  23. [23]

    2021 , url =

    Artur Czumaj and Peter Davies and Merav Parter , title =. 2021 , url =. doi:10.1145/3451992 , note =

    work page doi:10.1145/3451992 2021

  24. [24]

    Improved Deterministic Connectivity in Massively Parallel Computation , booktitle =

    Manuela Fischer and Jeff Giliberti and Christoph Grunau , editor =. Improved Deterministic Connectivity in Massively Parallel Computation , booktitle =. 2022 , url =. doi:10.4230/LIPICS.DISC.2022.22 , eprinttype =

    work page doi:10.4230/lipics.disc.2022.22 2022

  25. [25]

    and Sitchinava, Nodari and Zhang, Qin , title =

    Goodrich, Michael T. and Sitchinava, Nodari and Zhang, Qin , title =. Proceedings of the 22nd International Conference on Algorithms and Computation , pages =. 2011 , isbn =. doi:10.1007/978-3-642-25591-5_39 , abstract =

    work page doi:10.1007/978-3-642-25591-5_39 2011

  26. [26]

    Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures , pages=

    Massively parallel algorithms for distance approximation and spanners , author=. Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures , pages=. 2021 , eprinttype =

    2021

  27. [27]

    23rd International Conference on Principles of Distributed Systems (OPODIS 2019) , volume=

    Massively Parallel Approximate Distance Sketches , author=. 23rd International Conference on Principles of Distributed Systems (OPODIS 2019) , volume=. 2019 , organization=

    2019

  28. [28]

    Random Structures & Algorithms , volume=

    A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs , author=. Random Structures & Algorithms , volume=. 2007 , publisher=

    2007

  29. [29]

    2023 , url =

    Sam Coy and Artur Czumaj , title =. 2023 , url =. doi:10.1137/22M1520177 , note =

    work page doi:10.1137/22m1520177 2023

  30. [30]

    Pemmaraju , editor =

    Shreyas Pai and Sriram V. Pemmaraju , editor =. Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets , booktitle =. 2022 , url =

    2022

  31. [31]

    Massively Parallel Ruling Set Made Deterministic , booktitle =

    Jeff Giliberti and Zahra Parsaeian , editor =. Massively Parallel Ruling Set Made Deterministic , booktitle =. 2024 , url =. doi:10.4230/LIPICS.DISC.2024.29 , eprinttype =

    work page doi:10.4230/lipics.disc.2024.29 2024

  32. [32]

    Congested Clique Algorithms for Graph Spanners , booktitle =

    Merav Parter and Eylon Yogev , editor =. Congested Clique Algorithms for Graph Spanners , booktitle =. 2018 , url =. doi:10.4230/LIPICS.DISC.2018.40 , eprinttype =

    work page doi:10.4230/lipics.disc.2018.40 2018

  33. [33]

    Michael Luby , title =. J. Comput. Syst. Sci. , volume =. 1993 , url =. doi:10.1016/0022-0000(93)90033-S , note =

    work page doi:10.1016/0022-0000(93)90033-s 1993

  34. [34]

    Faster Deterministic All Pairs Shortest Paths in Congest Model , booktitle =

    Udit Agarwal and Vijaya Ramachandran , editor =. Faster Deterministic All Pairs Shortest Paths in Congest Model , booktitle =. 2020 , url =. doi:10.1145/3350755.3400256 , timestamp =

    work page doi:10.1145/3350755.3400256 2020

  35. [35]

    Ilan Newman , title =. Inf. Process. Lett. , volume =. 1991 , url =. doi:10.1016/0020-0190(91)90157-D , timestamp =

    work page doi:10.1016/0020-0190(91)90157-d 1991

  36. [36]

    Brief Announcement:

    Moses Charikar and Weiyun Ma and Li. Brief Announcement:. 2021 , url =. doi:10.1145/3465084.3467951 , timestamp =

    work page doi:10.1145/3465084.3467951 2021

  37. [37]

    Shor , title =

    Bonnie Berger and John Rompel and Peter W. Shor , title =. J. Comput. Syst. Sci. , volume =. 1994 , url =. doi:10.1016/S0022-0000(05)80068-6 , note =

    work page doi:10.1016/s0022-0000(05)80068-6 1994

  38. [38]

    Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Polylogarithmic-time deterministic network decomposition and distributed derandomization , author=. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

  39. [39]

    2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Conditional hardness results for massively parallel computation from distributed lower bounds , author=. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2019 , organization=

    2019

  40. [40]

    Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing , pages=

    Improved deterministic ( + 1) coloring in low-space MPC , author=. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing , pages=

    2021

  41. [41]

    34th International Symposium on Distributed Computing , year=

    Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond , author=. 34th International Symposium on Distributed Computing , year=

  42. [42]

    Distributed computing , volume=

    Equivalence classes and conditional hardness in massively parallel computations , author=. Distributed computing , volume=. 2022 , publisher=

    2022

  43. [43]

    2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    On derandomizing local distributed algorithms , author=. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2018 , organization=

    2018

  44. [44]

    Proceedings of the 26th International Conference on Distributed Computing and Networking , pages=

    Fast deterministic massively parallel ruling sets algorithms , author=. Proceedings of the 26th International Conference on Distributed Computing and Networking , pages=

  45. [45]

    40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science , volume=

    Sample-and-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model , author=. 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science , volume=. 2020 , organization=

    2020

  46. [46]

    37th International Symposium on Distributed Computing (DISC 2023) , pages=

    Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem , author=. 37th International Symposium on Distributed Computing (DISC 2023) , pages=. 2023 , organization=

    2023

  47. [47]

    Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization , booktitle =

    Mohsen Ghaffari and Christoph Grunau and Bernhard Haeupler and Saeed Ilchi and V. Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization , booktitle =. 2023 , url =. doi:10.1137/1.9781611977554.CH97 , eprinttype =

    work page doi:10.1137/1.9781611977554.ch97 2023

  48. [48]

    Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures , pages=

    Deterministic distributed sparse and ultra-sparse spanners and connectivity certificates , author=. Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures , pages=. 2022 , eprinttype =

    2022

  49. [49]

    35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, November 20-22, 1994 , pages =

    Mihir Bellare and John Rompel , title =. 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, November 20-22, 1994 , pages =. 1994 , url =

    1994

  50. [50]

    Vadhan , title =

    Salil P. Vadhan , title =. Found. Trends Theor. Comput. Sci. , volume =. 2012 , url =

    2012

  51. [51]

    Theory Comput

    Parikshit Gopalan and Amir Yehudayoff , title =. Theory Comput. , volume =. 2020 , url =

    2020

  52. [52]

    2021 , isbn =

    Dory, Michal and Fischer, Orr and Khoury, Seri and Leitersdorf, Dean , title =. 2021 , isbn =. doi:10.1145/3465084.3467928 , booktitle =

    work page doi:10.1145/3465084.3467928 2021

  53. [53]

    Discrete & Computational Geometry , volume=

    On sparse spanners of weighted graphs , author=. Discrete & Computational Geometry , volume=. 1993 , publisher=

    1993

  54. [54]

    SODA , pages=

    A model of computation for MapReduce , author=. SODA , pages=. 2010 , organization=

    2010

  55. [55]

    Journal of the ACM (JACM) , volume=

    Communication steps for parallel query processing , author=. Journal of the ACM (JACM) , volume=. 2017 , publisher=

    2017

  56. [56]

    Communications of the ACM , volume=

    MapReduce: simplified data processing on large clusters , author=. Communications of the ACM , volume=. 2008 , publisher=

    2008

  57. [57]

    2012 , publisher=

    Hadoop: The definitive guide , author=. 2012 , publisher=

    2012

  58. [58]

    , author=

    Spark: Cluster computing with working sets. , author=. HotCloud , volume=

  59. [59]

    ACM SIGOPS operating systems review , pages=

    Dryad: distributed data-parallel programs from sequential building blocks , author=. ACM SIGOPS operating systems review , pages=. 2007 , organization=

    2007

  60. [60]

    PODC , pages=

    Improved massively parallel computation algorithms for mis, matching, and vertex cover , author=. PODC , pages=

  61. [61]

    PODC , pages=

    Massively parallel computation of matching and MIS in sparse graphs , author=. PODC , pages=

  62. [62]

    FOCS , pages=

    Exponentially faster massively parallel maximal matching , author=. FOCS , pages=. 2019 , organization=

    2019

  63. [63]

    SODA , pages=

    Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation , author=. SODA , pages=

  64. [64]

    SPAA , pages=

    Filtering: a method for solving graph problems in mapreduce , author=. SPAA , pages=

  65. [65]

    PODC , pages=

    Massively parallel algorithms for minimum cut , author=. PODC , pages=

  66. [66]

    FOCS , pages=

    Parallel graph connectivity in log diameter rounds , author=. FOCS , pages=. 2018 , organization=

    2018

  67. [67]

    SODA , pages=

    Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs , author=. SODA , pages=. 2019 , organization=

    2019

  68. [68]

    STOC , pages=

    Round compression for parallel matching algorithms , author=. STOC , pages=

  69. [69]

    PODC , pages=

    Massively Parallel Computation in a Heterogeneous Regime , author=. PODC , pages=

  70. [70]

    SIAM Journal on Computing , volume=

    Near-optimal approximate shortest paths and transshipment in distributed and streaming models , author=. SIAM Journal on Computing , volume=. 2021 , publisher=

    2021

  71. [71]

    STOC , pages=

    Faster parallel algorithm for approximate shortest path , author=. STOC , pages=

  72. [72]

    STOC , pages=

    Parallel approximate undirected shortest paths via low hop emulators , author=. STOC , pages=

  73. [73]

    arXiv preprint arXiv:1905.01748 , year=

    MapReduce meets fine-grained complexity: MapReduce algorithms for APSP, matrix multiplication, 3-SUM, and beyond , author=. arXiv preprint arXiv:1905.01748 , year=

    Pith/arXiv arXiv 1905

  74. [74]

    OPODIS , year=

    Massively Parallel Approximate Distance Sketches , author=. OPODIS , year=

  75. [75]

    38th International Symposium on Distributed Computing , year=

    Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling , author=. 38th International Symposium on Distributed Computing , year=

  76. [76]

    PODC , pages=

    The complexity of ( + 1) coloring in congested clique, massively parallel computation, and centralized local computation , author=. PODC , pages=

  77. [77]

    Proceedings of the 26th International Conference on Distributed Computing and Networking , pages=

    Faster Set Cover in the MPC Model , author=. Proceedings of the 26th International Conference on Distributed Computing and Networking , pages=

  78. [78]

    SIAM journal on computing , volume=

    Simple, deterministic, constant-round coloring in congested clique and MPC , author=. SIAM journal on computing , volume=. 2021 , publisher=

    2021

  79. [79]

    Proceedings of the thirty-third annual ACM symposium on Theory of computing , pages=

    Non-approximability results for optimization problems on bounded degree instances , author=. Proceedings of the thirty-third annual ACM symposium on Theory of computing , pages=

  80. [80]

    David Peleg , title =

Showing first 80 references.