pith. sign in

arxiv: 2605.21248 · v1 · pith:MK4GK5RDnew · submitted 2026-05-20 · 💻 cs.DS · cs.DC

Distributed Stochastic Graph Algorithms

Keren Censor-Hillel , Aditi Dudeja , George Giakkoupis This is my paper

Pith reviewed 2026-05-21 04:02 UTC · model grok-4.3

classification 💻 cs.DS cs.DC
keywords distributed algorithmsstochastic graphsmaximum matchingvertex coverdominating setapproximation algorithmsrandom subgraphscommunication rounds
0
0 comments X

The pith

Stochastic distributed algorithms achieve faster approximations for matching and covering by using only realized random edges.

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

The paper examines graph optimization on a random subgraph in a distributed model where each vertex knows only its incident realized edges and communicates solely over them. It presents approximation algorithms for maximum matching, minimum vertex cover, and minimum dominating set that require far fewer synchronous rounds than deterministic distributed algorithms. These results surpass established lower bounds that hold in the non-stochastic setting. A reader would care because the work shows how local modeling of uncertainty can convert a source of difficulty into a source of efficiency for distributed computation.

Core claim

We establish that distributed stochastic algorithms can be drastically faster than their non-stochastic counterparts and overcome known lower bounds, by showing fast distributed approximation algorithms for maximum matching, minimum vertex cover, and minimum dominating set.

What carries the argument

The stochastic distributed model with local knowledge of realized edges in the random subgraph G*, which restricts communication to those edges and enables reduced round complexity.

If this is right

  • Maximum matching admits fast distributed approximations that beat non-stochastic lower bounds.
  • Minimum vertex cover can be approximated in significantly fewer rounds using the stochastic model.
  • Minimum dominating set similarly receives fast distributed approximations.
  • The approach demonstrates that randomness in edge realizations can be exploited directly for efficiency gains.

Where Pith is reading between the lines

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

  • The same local-realization technique could extend to other graph problems such as coloring or shortest paths.
  • Real-world networks with probabilistic link formation might adopt this model for more efficient distributed protocols.
  • Limited communication over non-realized edges could be added while retaining some of the observed speedups.

Load-bearing premise

Each vertex receives exact knowledge of its incident realized edges and communicates exclusively over those realized edges.

What would settle it

A proof establishing that the same approximation problems still require as many rounds in this model as in the non-stochastic case, even with local knowledge of realized edges.

Figures

Figures reproduced from arXiv: 2605.21248 by Aditi Dudeja, George Giakkoupis, Keren Censor-Hillel.

Figure 1
Figure 1. Figure 1: Plot of E[F ∗] P(Y ̸=0) as a function of λ, used in the proof of Lemma 7. is concave in each of the three intervals (the second derivative is negative), which implies the minimum lies in one of the points λi , for i ∈ {1, 2, 3, 4}. A plot of the function is shown in [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
read the original abstract

We study stochastic graph optimization problems in a novel distributed setting. As in the standard centralized setting, a random subgraph $G^*$ of a known base graph $G$ is realized by including each edge $e$ independently with a known probability $p_e$, and we must solve an optimization problem on $G^*$ despite uncertainty about its edges. In the standard setting, to cope with this uncertainty, the algorithm can query any edge of $G$ to learn if the edge exists in $G^*$, and its complexity is the number of queried edges. The distributed setting incorporates uncertainty in a natural manner, by having each vertex know only about its own edges in $G^*$ (and only communicate over them), and the complexity is measured by the number of synchronous communication rounds. We establish that distributed stochastic algorithms can be drastically faster than their non-stochastic counterparts and overcome known lower bounds, by showing fast distributed approximation algorithms for maximum matching, minimum vertex cover, and minimum dominating set.

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

0 major / 3 minor

Summary. The manuscript introduces a distributed model for stochastic graph optimization on a random subgraph G* realized from a known base graph G, where each edge is included independently with probability p_e. Vertices receive exact local knowledge of their incident realized edges in G* and communicate exclusively over those edges, with complexity measured in synchronous rounds. The central claim is that this model enables drastically faster distributed approximation algorithms for maximum matching, minimum vertex cover, and minimum dominating set compared to non-stochastic counterparts, overcoming known lower bounds.

Significance. If the algorithms and their analyses hold, the work is significant for demonstrating how a natural incorporation of stochastic uncertainty—via local knowledge of realized edges and restricted communication—can bypass standard lower bounds in distributed graph algorithms. The concrete results on three classic problems provide falsifiable predictions and a clear model definition that distinguishes this setting from centralized stochastic optimization or standard distributed models. This opens avenues for efficient distributed computation under uncertainty.

minor comments (3)
  1. The abstract would be strengthened by explicitly stating the approximation ratios achieved and the round complexities for each of the three problems.
  2. A comparison table or section contrasting the new stochastic distributed model with the LOCAL/CONGEST models and with centralized stochastic query models would improve clarity for readers.
  3. Notation for the base graph G, realized subgraph G*, and edge probabilities p_e is introduced clearly but could be reinforced with a formal definition early in the model section.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, recognition of the model's novelty in incorporating stochastic uncertainty via local realized-edge knowledge, and recommendation for minor revision. The assessment accurately reflects the central claim that the distributed stochastic setting enables approximation algorithms for matching, vertex cover, and dominating set that bypass non-stochastic lower bounds.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents new distributed algorithms for stochastic graph problems (maximum matching, minimum vertex cover, minimum dominating set) in a model where each vertex knows its realized incident edges in G* and communicates only over them. The central claims consist of algorithmic constructions and round-complexity bounds that are derived from the algorithm descriptions and their analysis; these do not reduce to fitted parameters, self-definitions, or load-bearing self-citations. The modeling assumptions are stated explicitly and the speed-up results are scoped to that model, making the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are visible in the abstract; the model appears to rest on standard assumptions of the LOCAL distributed model plus independent edge realizations.

pith-pipeline@v0.9.0 · 5698 in / 1100 out tokens · 28388 ms · 2026-05-21T04:02:00.023692+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

135 extracted references · 135 canonical work pages

  1. [1]

    2026 , month = may, url =

    Censor-Hillel, Keren and Dudeja, Aditi and Giakkoupis, George , title =. 2026 , month = may, url =

    work page 2026

  2. [2]

    An Optimal Algorithm for Stochastic Vertex Cover , journal =

    Jan van den Brand and Inge Li G. An Optimal Algorithm for Stochastic Vertex Cover , journal =. 2026 , xurl =. doi:10.48550/arXiv.2603.27795 , xeprinttype =

    work page doi:10.48550/arxiv.2603.27795 2026

  3. [3]

    Distributed Computation with Local Advice , booktitle =

    Alkida Balliu and Sebastian Brandt and Fabian Kuhn and Krzysztof Nowicki and Dennis Olivetti and Eva Rotenberg and Jukka Suomela , xeditor =. Distributed Computation with Local Advice , booktitle =. 2025 , xurl =. doi:10.4230/LIPICS.DISC.2025.12 , timestamp =

    work page doi:10.4230/lipics.disc.2025.12 2025

  4. [4]

    Theory Comput

    Pierre Fraigniaud and Amos Korman and Emmanuelle Lebhar , title =. Theory Comput. Syst. , volume =. 2010 , xurl =. doi:10.1007/S00224-010-9280-9 , timestamp =

    work page doi:10.1007/s00224-010-9280-9 2010

  5. [5]

    Distributed Comput

    Pierre Fraigniaud and Cyril Gavoille and David Ilcinkas and Andrzej Pelc , title =. Distributed Comput. , volume =. 2009 , xurl =. doi:10.1007/S00446-008-0076-Y , timestamp =

    work page doi:10.1007/s00446-008-0076-y 2009

  6. [6]

    Larsen , title =

    Joan Boyar and Faith Ellen and Kim S. Larsen , title =. CoRR , volume =. 2025 , xurl =. doi:10.48550/ARXIV.2501.05267 , eprinttype =. 2501.05267 , timestamp =

    work page doi:10.48550/arxiv.2501.05267 2025

  7. [7]

    Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond , booktitle =

    Salwa Faour and Mohsen Ghaffari and Christoph Grunau and Fabian Kuhn and V. Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond , booktitle =. 2023 , xurl =. doi:10.1137/1.9781611977554.CH168 , timestamp =

    work page doi:10.1137/1.9781611977554.ch168 2023

  8. [8]

    Distributed Comput

    Michal Dory and Mohsen Ghaffari and Saeed Ilchi , title =. Distributed Comput. , volume =. 2024 , xurl =. doi:10.1007/S00446-023-00447-Z , timestamp =

    work page doi:10.1007/s00446-023-00447-z 2024

  9. [9]

    Deterministic Distributed Dominating Set Approximation in the

    Janosch Deurer and Fabian Kuhn and Yannic Maus , xeditor =. Deterministic Distributed Dominating Set Approximation in the. 2019. 2019 , xurl =. doi:10.1145/3293611.3331626 , timestamp =

    work page doi:10.1145/3293611.3331626 2019

  10. [10]

    Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set , booktitle =

    Mohsen Ghaffari and Fabian Kuhn , xeditor =. Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set , booktitle =. 2018 , xurl =. doi:10.4230/LIPICS.DISC.2018.29 , timestamp =

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

  11. [11]

    Fabian Kuhn and Thomas Moscibroda and Roger Wattenhofer , title =. J. 2016 , xurl =. doi:10.1145/2742012 , timestamp =

    work page doi:10.1145/2742012 2016

  12. [12]

    Constant-time distributed dominating set approximation , booktitle =

    Fabian Kuhn and Roger Wattenhofer , xeditor =. Constant-time distributed dominating set approximation , booktitle =. 2003 , xurl =. doi:10.1145/872035.872040 , timestamp =

    work page doi:10.1145/872035.872040 2003

  13. [13]

    Improved Deterministic Network Decomposition , booktitle =

    Mohsen Ghaffari and Christoph Grunau and V. Improved Deterministic Network Decomposition , booktitle =. 2021 , xurl =. doi:10.1137/1.9781611976465.173 , timestamp =

    work page doi:10.1137/1.9781611976465.173 2021

  14. [14]

    Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial , booktitle =

    Adir Morgan and Shay Solomon and Nicole Wein , xeditor =. Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial , booktitle =. 2021 , xurl =. doi:10.4230/LIPICS.DISC.2021.33 , timestamp =

    work page doi:10.4230/lipics.disc.2021.33 2021

  15. [15]

    Distributed Spanner Approximation , journal =

    Keren Censor. Distributed Spanner Approximation , journal =. 2021 , xurl =. doi:10.1137/20M1312630 , timestamp =

    work page doi:10.1137/20m1312630 2021

  16. [16]

    Stochastic Matching on Uniformly Sparse Graphs , booktitle =

    Soheil Behnezhad and Mahsa Derakhshan and Alireza Farhadi and MohammadTaghi Hajiaghayi and Nima Reyhani , xeditor =. Stochastic Matching on Uniformly Sparse Graphs , booktitle =. 2019 , xurl =. doi:10.1007/978-3-030-30473-7\_24 , timestamp =

    work page doi:10.1007/978-3-030-30473-7 2019

  17. [17]

    Stochastic Matching via In-n-Out Local Computation Algorithms , booktitle =

    Amir Azarmehr and Soheil Behnezhad and Alma Ghafari and Ronitt Rubinfeld , xeditor =. Stochastic Matching via In-n-Out Local Computation Algorithms , booktitle =. 2025 , xurl =. doi:10.1145/3717823.3718279 , timestamp =

    work page doi:10.1145/3717823.3718279 2025

  18. [18]

    Dickerson and Nika Haghtalab and Ariel D

    Avrim Blum and John P. Dickerson and Nika Haghtalab and Ariel D. Procaccia and Tuomas Sandholm and Ankit Sharma , xeditor =. Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries , booktitle =. 2015 , xurl =. doi:10.1145/2764468.2764479 , timestamp =

    work page doi:10.1145/2764468.2764479 2015

  19. [19]

    Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching , booktitle =

    Manuela Fischer and Mohsen Ghaffari and Fabian Kuhn , xeditor =. Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching , booktitle =. 2017 , xurl =. doi:10.1109/FOCS.2017.25 , timestamp =

    work page doi:10.1109/focs.2017.25 2017

  20. [20]

    Local, distributed weighted matching on general and wireless topologies , booktitle =

    Tim Nieberg , xeditor =. Local, distributed weighted matching on general and wireless topologies , booktitle =. 2008 , xurl =. doi:10.1145/1400863.1400880 , timestamp =

    work page doi:10.1145/1400863.1400880 2008

  21. [21]

    Larsen , xeditor =

    Joan Boyar and Faith Ellen and Kim S. Larsen , xeditor =. Brief Announcement: Distributed Graph Algorithms with Predictions , booktitle =. 2025 , xurl =. doi:10.1145/3732772.3733530 , timestamp =

    work page doi:10.1145/3732772.3733530 2025

  22. [22]

    Query Complexity of Stochastic Minimum Vertex Cover , booktitle =

    Mahsa Derakhshan and Mohammad Saneian and Zhiyang Xun , xeditor =. Query Complexity of Stochastic Minimum Vertex Cover , booktitle =. 2025 , xurl =. doi:10.4230/LIPICS.ITCS.2025.41 , timestamp =

    work page doi:10.4230/lipics.itcs.2025.41 2025

  23. [23]

    Fifteenth

    Zvi Lotker and Elan Pavlov and Boaz Patt. Fifteenth. 2003 , xurl =. doi:10.1145/777412.777428 , timestamp =

    work page doi:10.1145/777412.777428 2003

  24. [24]

    Korhonen and Ami Paz and Joel Rybicki and Stefan Schmid and Jukka Suomela , xeditor =

    Janne H. Korhonen and Ami Paz and Joel Rybicki and Stefan Schmid and Jukka Suomela , xeditor =. Brief Announcement: Sinkless Orientation Is Hard Also in the Supported. 35th International Symposium on Distributed Computing,. 2021 , xurl =. doi:10.4230/LIPICS.DISC.2021.58 , timestamp =

    work page doi:10.4230/lipics.disc.2021.58 2021

  25. [25]

    Korhonen and Fabian Kuhn and Henrik Lievonen and Dennis Olivetti and Shreyas Pai and Ami Paz and Joel Rybicki and Stefan Schmid and Jan Studen

    Alkida Balliu and Janne H. Korhonen and Fabian Kuhn and Henrik Lievonen and Dennis Olivetti and Shreyas Pai and Ami Paz and Joel Rybicki and Stefan Schmid and Jan Studen. Sinkless Orientation Made Simple , booktitle =. 2023 , xurl =. doi:10.1137/1.9781611977585.CH17 , timestamp =

    work page doi:10.1137/1.9781611977585.ch17 2023

  26. [26]

    Input-Dynamic Distributed Algorithms for Communication Networks , journal =

    Klaus. Input-Dynamic Distributed Algorithms for Communication Networks , journal =. 2021 , xurl =. doi:10.1145/3447384 , timestamp =

    work page doi:10.1145/3447384 2021

  27. [27]

    Local Recurrent Problems in the

    Akanksha Agrawal and John Augustine and David Peleg and Srikkanth Ramachandran , xeditor =. Local Recurrent Problems in the. 27th International Conference on Principles of Distributed Systems,. 2023 , xurl =. doi:10.4230/LIPICS.OPODIS.2023.22 , timestamp =

    work page doi:10.4230/lipics.opodis.2023.22 2023

  28. [28]

    Universally-optimal distributed algorithms for known topologies , booktitle =

    Bernhard Haeupler and David Wajc and Goran Zuzic , xeditor =. Universally-optimal distributed algorithms for known topologies , booktitle =. 2021 , xurl =. doi:10.1145/3406325.3451081 , timestamp =

    work page doi:10.1145/3406325.3451081 2021

  29. [29]

    Distributed Comput

    Ioannis Anagnostides and Christoph Lenzen and Bernhard Haeupler and Goran Zuzic and Themis Gouleakis , title =. Distributed Comput. , volume =. 2023 , xurl =. doi:10.1007/S00446-023-00454-0 , timestamp =

    work page doi:10.1007/s00446-023-00454-0 2023

  30. [30]

    Does Preprocessing Help under Congestion? , booktitle =

    Klaus. Does Preprocessing Help under Congestion? , booktitle =. 2019 , xurl =. doi:10.1145/3293611.3331581 , timestamp =

    work page doi:10.1145/3293611.3331581 2019

  31. [31]

    On the Power of Preprocessing in Decentralized Network Optimization , booktitle =

    Klaus. On the Power of Preprocessing in Decentralized Network Optimization , booktitle =. 2019 , xurl =. doi:10.1109/INFOCOM.2019.8737382 , timestamp =

    work page doi:10.1109/infocom.2019.8737382 2019

  32. [32]

    Tight Lower Bounds in the Supported

    Alkida Balliu and Thomas Boudier and Sebastian Brandt and Dennis Olivetti , xeditor =. Tight Lower Bounds in the Supported. 43rd. 2024 , xurl =. doi:10.1145/3662158.3662798 , timestamp =

    work page doi:10.1145/3662158.3662798 2024

  33. [33]

    Korhonen and Joel Rybicki , xeditor =

    Janne H. Korhonen and Joel Rybicki , xeditor =. Deterministic Subgraph Detection in Broadcast. 21st International Conference on Principles of Distributed Systems,. 2017 , xurl =. doi:10.4230/LIPICS.OPODIS.2017.4 , timestamp =

    work page doi:10.4230/lipics.opodis.2017.4 2017

  34. [34]

    Exploiting locality in distributed

    Stefan Schmid and Jukka Suomela , xeditor =. Exploiting locality in distributed. Second. 2013 , xurl =. doi:10.1145/2491185.2491198 , timestamp =

    work page doi:10.1145/2491185.2491198 2013

  35. [35]

    Distributed Weighted Matching , booktitle =

    Mirjam Wattenhofer and Roger Wattenhofer , xeditor =. Distributed Weighted Matching , booktitle =. 2004 , xurl =. doi:10.1007/978-3-540-30186-8\_24 , timestamp =

    work page doi:10.1007/978-3-540-30186-8 2004

  36. [36]

    Distributed Approximate Matching , journal =

    Zvi Lotker and Boaz Patt. Distributed Approximate Matching , journal =. 2009 , xurl =. doi:10.1137/080714403 , timestamp =

    work page doi:10.1137/080714403 2009

  37. [37]

    Narrowing the

    Yi. Narrowing the. 2022. 2022 , xurl =. doi:10.1145/3519270.3538423 , timestamp =

    work page doi:10.1145/3519270.3538423 2022

  38. [38]

    Improved Distributed Approximate Matching , journal =

    Zvi Lotker and Boaz Patt. Improved Distributed Approximate Matching , journal =. 2015 , xurl =. doi:10.1145/2786753 , timestamp =

    work page doi:10.1145/2786753 2015

  39. [39]

    (1- )-Approximate Maximum Weighted Matching in poly(1/ , log

    Shang. (1- )-Approximate Maximum Weighted Matching in poly(1/ , log. 2023. 2023 , xurl =. doi:10.1145/3583668.3594570 , timestamp =

    work page doi:10.1145/3583668.3594570 2023

  40. [40]

    A framework for boosting matching approximation: parallel, distributed, and dynamic , journal =

    Slobodan Mitrovic and Wen. A framework for boosting matching approximation: parallel, distributed, and dynamic , journal =. 2025 , xurl =. doi:10.48550/ARXIV.2503.01147 , eprinttype =

    work page doi:10.48550/arxiv.2503.01147 2025

  41. [41]

    Distributed Comput

    Manuela Fischer , title =. Distributed Comput. , volume =. 2020 , xurl =. doi:10.1007/S00446-018-0344-4 , timestamp =

    work page doi:10.1007/s00446-018-0344-4 2020

  42. [42]

    Deterministic (1+

    Manuela Fischer and Slobodan Mitrovic and Jara Uitto , xeditor =. Deterministic (1+. 54th. 2022 , xurl =. doi:10.1145/3519935.3520039 , timestamp =

    work page doi:10.1145/3519935.3520039 2022

  43. [43]

    2022 , xurl =

    Naoki Kitamura and Taisuke Izumi , title =. 2022 , xurl =. doi:10.1587/TRANSINF.2021EDP7083 , timestamp =

    work page doi:10.1587/transinf.2021edp7083 2022

  44. [44]

    Distributed Approximate Maximum Matching in the

    Mohamad Ahmadi and Fabian Kuhn and Rotem Oshman , xeditor =. Distributed Approximate Maximum Matching in the. 32nd International Symposium on Distributed Computing,. 2018 , xurl =. doi:10.4230/LIPICS.DISC.2018.6 , timestamp =

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

  45. [45]

    A Nearly Linear-Time Distributed Algorithm for Exact Maximum Matching , booktitle =

    Taisuke Izumi and Naoki Kitamura and Yutaro Yamaguchi , xeditor =. A Nearly Linear-Time Distributed Algorithm for Exact Maximum Matching , booktitle =. 2024 , xurl =. doi:10.1137/1.9781611977912.141 , timestamp =

    work page doi:10.1137/1.9781611977912.141 2024

  46. [46]

    The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs , booktitle =

    Yi. The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs , booktitle =. 2023 , xurl =. doi:10.1145/3583668.3594562 , timestamp =

    work page doi:10.1145/3583668.3594562 2023

  47. [47]

    Improved Deterministic Distributed Matching via Rounding , booktitle =

    Manuela Fischer , xeditor =. Improved Deterministic Distributed Matching via Rounding , booktitle =. 2017 , xurl =. doi:10.4230/LIPICS.DISC.2017.17 , timestamp =

    work page doi:10.4230/lipics.disc.2017.17 2017

  48. [48]

    Leonid Barenboim and Michael Elkin and Seth Pettie and Johannes Schneider , title =. 53rd. 2012 , xurl =. doi:10.1109/FOCS.2012.60 , timestamp =

    work page doi:10.1109/focs.2012.60 2012

  49. [49]

    2001 , xurl =

    Michal Hanckowiak and Michal Karonski and Alessandro Panconesi , title =. 2001 , xurl =. doi:10.1137/S0895480100373121 , timestamp =

    work page doi:10.1137/s0895480100373121 2001

  50. [50]

    Distributed Comput

    Alessandro Panconesi and Romeo Rizzi , title =. Distributed Comput. , volume =. 2001 , xurl =. doi:10.1007/PL00008932 , timestamp =

    work page doi:10.1007/pl00008932 2001

  51. [51]

    Valentin Polishchuk and Jukka Suomela , title =. Inf. Process. Lett. , volume =. 2009 , xurl =. doi:10.1016/J.IPL.2009.02.017 , timestamp =

    work page doi:10.1016/j.ipl.2009.02.017 2009

  52. [52]

    Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks , booktitle =

    Matti. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks , booktitle =. 2010 , xurl =. doi:10.1145/1810479.1810533 , timestamp =

    work page doi:10.1145/1810479.1810533 2010

  53. [53]

    A Local 2-Approximation Algorithm for the Vertex Cover Problem , booktitle =

    Matti. A Local 2-Approximation Algorithm for the Vertex Cover Problem , booktitle =. 2009 , xurl =. doi:10.1007/978-3-642-04355-0\_21 , timestamp =

    work page doi:10.1007/978-3-642-04355-0 2009

  54. [54]

    Parameterized Distributed Algorithms , booktitle =

    Ran Ben. Parameterized Distributed Algorithms , booktitle =. 2019 , xurl =. doi:10.4230/LIPICS.DISC.2019.6 , timestamp =

    work page doi:10.4230/lipics.disc.2019.6 2019

  55. [55]

    Optimal distributed covering algorithms , journal =

    Ran Ben. Optimal distributed covering algorithms , journal =. 2023 , xurl =. doi:10.1007/S00446-021-00391-W , timestamp =

    work page doi:10.1007/s00446-021-00391-w 2023

  56. [56]

    A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in

    Ran Ben. A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in. 25th International Colloquium on Structural Information and Communication Complexity,. 2018 , xurl =. doi:10.1007/978-3-030-01325-7\_21 , timestamp =

    work page doi:10.1007/978-3-030-01325-7 2018

  57. [57]

    Young , xeditor =

    Christos Koufogiannakis and Neal E. Young , xeditor =. Distributed and parallel algorithms for weighted vertex cover and other covering problems , booktitle =. 2009 , xurl =. doi:10.1145/1582716.1582746 , timestamp =

    work page doi:10.1145/1582716.1582746 2009

  58. [58]

    Polylogarithmic-time deterministic network decomposition and distributed derandomization , booktitle =

    V. Polylogarithmic-time deterministic network decomposition and distributed derandomization , booktitle =. 2020 , xurl =. doi:10.1145/3357713.3384298 , timestamp =

    work page doi:10.1145/3357713.3384298 2020

  59. [59]

    Young , title =

    Samir Khuller and Uzi Vishkin and Neal E. Young , title =. J. Algorithms , volume =. 1994 , xurl =. doi:10.1006/JAGM.1994.1036 , timestamp =

    work page doi:10.1006/jagm.1994.1036 1994

  60. [60]

    Reiter, Guy Golan-Gueta, and Ittai Abraham

    Nir Bachrach and Keren Censor. Hardness of Distributed Optimization , booktitle =. 2019 , xurl =. doi:10.1145/3293611.3331597 , timestamp =

    work page doi:10.1145/3293611.3331597 2019

  61. [61]

    No sublogarithmic-time approximation scheme for bipartite vertex cover , journal =

    Mika G. No sublogarithmic-time approximation scheme for bipartite vertex cover , journal =. 2014 , xurl =. doi:10.1007/S00446-013-0194-Z , timestamp =

    work page doi:10.1007/s00446-013-0194-z 2014

  62. [62]

    Smaller Cuts, Higher Lower Bounds , journal =

    Amir Abboud and Keren Censor. Smaller Cuts, Higher Lower Bounds , journal =. 2021 , xurl =. doi:10.1145/3469834 , timestamp =

    work page doi:10.1145/3469834 2021

  63. [63]

    On the complexity of local distributed graph problems , booktitle =

    Mohsen Ghaffari and Fabian Kuhn and Yannic Maus , xeditor =. On the complexity of local distributed graph problems , booktitle =. 2017 , xurl =. doi:10.1145/3055399.3055471 , timestamp =

    work page doi:10.1145/3055399.3055471 2017

  64. [64]

    What cannot be computed locally! , booktitle =

    Fabian Kuhn and Thomas Moscibroda and Roger Wattenhofer , xeditor =. What cannot be computed locally! , booktitle =. 2004 , xurl =. doi:10.1145/1011767.1011811 , timestamp =

    work page doi:10.1145/1011767.1011811 2004

  65. [65]

    Distributed

    Salwa Faour and Marc Fuchs and Fabian Kuhn , xeditor =. Distributed. 25th International Conference on Principles of Distributed Systems,. 2021 , xurl =. doi:10.4230/LIPICS.OPODIS.2021.17 , timestamp =

    work page doi:10.4230/lipics.opodis.2021.17 2021

  66. [66]

    Approximating Bipartite Minimum Vertex Cover in the

    Salwa Faour and Fabian Kuhn , xeditor =. Approximating Bipartite Minimum Vertex Cover in the. 24th International Conference on Principles of Distributed Systems,. 2020 , xurl =. doi:10.4230/LIPICS.OPODIS.2020.29 , timestamp =

    work page doi:10.4230/lipics.opodis.2020.29 2020

  67. [67]

    Distributed Vertex Cover Reconfiguration , booktitle =

    Keren Censor. Distributed Vertex Cover Reconfiguration , booktitle =. 2022 , xurl =. doi:10.4230/LIPICS.ITCS.2022.36 , timestamp =

    work page doi:10.4230/lipics.itcs.2022.36 2022

  68. [68]

    Reuven Bar. J. 2017 , xurl =. doi:10.1145/3060294 , timestamp =

    work page doi:10.1145/3060294 2017

  69. [69]

    Finding Graph Matchings in Data Streams , booktitle =

    Andrew McGregor , xeditor =. Finding Graph Matchings in Data Streams , booktitle =. 2005 , xurl =. doi:10.1007/11538462\_15 , timestamp =

    work page doi:10.1007/11538462 2005

  70. [70]

    Cliff Liu and Robert E

    Sepehr Assadi and S. Cliff Liu and Robert E. Tarjan , xeditor =. An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models , booktitle =. 2021 , xurl =. doi:10.1137/1.9781611976496.18 , timestamp =

    work page doi:10.1137/1.9781611976496.18 2021

  71. [71]

    Adapting Local Sequential Algorithms to the Distributed Setting , booktitle =

    Ken. Adapting Local Sequential Algorithms to the Distributed Setting , booktitle =. 2018 , xurl =. doi:10.4230/LIPICS.DISC.2018.35 , timestamp =

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

  72. [72]

    Choi , journal =

    Kwok P. Choi , journal =. On the Medians of Gamma Distributions and an Equation of. 1994 , doi =

    work page 1994

  73. [73]

    The Annals of Mathematical Statistics , number =

    Wassily Hoeffding , title =. The Annals of Mathematical Statistics , number =. 1956 , doi =

    work page 1956

  74. [74]

    Statistical Science , number =

    Wenpin Tang and Fengmin Tang , title =. Statistical Science , number =. 2023 , doi =

    work page 2023

  75. [75]

    Stochastic Vertex Cover with Few Queries , booktitle =

    Soheil Behnezhad and Avrim Blum and Mahsa Derakhshan , xeditorx =. Stochastic Vertex Cover with Few Queries , booktitle =. 2022 , xurl =. doi:10.1137/1.9781611977073.73 , timestamp =

    work page doi:10.1137/1.9781611977073.73 2022

  76. [76]

    Stochastic Minimum Vertex Cover in General Graphs:

    Mahsa Derakhshan and Naveen Durvasula and Nika Haghtalab , xeditorx =. Stochastic Minimum Vertex Cover in General Graphs:. 55th. 2023 , xurl =. doi:10.1145/3564246.3585230 , timestamp =

    work page doi:10.1145/3564246.3585230 2023

  77. [77]

    Data structures meet cryptography: 3SUM with preprocessing

    Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi , xeditorx =. Stochastic matching with few queries: (1-. 52nd. 2020 , xurl =. doi:10.1145/3357713.3384340 , timestamp =

    work page doi:10.1145/3357713.3384340 2020

  78. [78]

    A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size , booktitle =

    Krzysztof Onak and Dana Ron and Michal Rosen and Ronitt Rubinfeld , xeditorx =. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size , booktitle =. 2012 , xurl =. doi:10.1137/1.9781611973099.88 , timestamp =

    work page doi:10.1137/1.9781611973099.88 2012

  79. [79]

    Michal Parnas and Dana Ron , title =. Theor. Comput. Sci. , volume =. 2007 , xurl =. doi:10.1016/J.TCS.2007.04.040 , timestamp =

    work page doi:10.1016/j.tcs.2007.04.040 2007

  80. [80]

    In: Proceed- ings of the Forty-First Annual ACM Symposium on Theory of Computing

    Yuichi Yoshida and Masaki Yamamoto and Hiro Ito , xeditor =. An improved constant-time approximation algorithm for maximum matchings , booktitle =. 2009 , xurl =. doi:10.1145/1536414.1536447 , timestamp =

    work page doi:10.1145/1536414.1536447 2009

Showing first 80 references.