Search Results

Documents authored by Giliberti, Jeff

Document
DOI: 10.4230/LIPIcs.DISC.2024.29
Massively Parallel Ruling Set Made Deterministic

Authors: Jeff Giliberti and Zahra Parsaeian

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
We study the deterministic complexity of the 2-Ruling Set problem in the model of Massively Parallel Computation (MPC) with linear and strongly sublinear local memory. - Linear MPC: We present a constant-round deterministic algorithm for the 2-Ruling Set problem that matches the randomized round complexity recently settled by Cambus, Kuhn, Pai, and Uitto [DISC'23], and improves upon the deterministic O(log log n)-round algorithm by Pai and Pemmaraju [PODC'22]. Our main ingredient is a simpler analysis of CKPU’s algorithm based solely on bounded independence, which makes its efficient derandomization possible. - Sublinear MPC: We present a deterministic algorithm that computes a 2-Ruling Set in Õ(√{log n}) rounds deterministically. Notably, this is the first deterministic ruling set algorithm with sublogarithmic round complexity, improving on the O(log Δ + log log^* n)-round complexity that stems from the deterministic MIS algorithm of Czumaj, Davies, and Parter [TALG'21]. Our result is based on a simple and fast randomness-efficient construction that achieves the same sparsification as that of the randomized Õ(√{log n})-round LOCAL algorithm by Kothapalli and Pemmaraju [FSTTCS'12].
Cite as

Jeff Giliberti and Zahra Parsaeian. Massively Parallel Ruling Set Made Deterministic. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{giliberti_et_al:LIPIcs.DISC.2024.29,
  author =	{Giliberti, Jeff and Parsaeian, Zahra},
  title =	{{Massively Parallel Ruling Set Made Deterministic}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{29:1--29:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.29},
  URN =		{urn:nbn:de:0030-drops-212551},
  doi =		{10.4230/LIPIcs.DISC.2024.29},
  annote =	{Keywords: deterministic algorithms, distributed computing, massively parallel computation, graph algorithms, derandomization}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.22
Improved Deterministic Connectivity in Massively Parallel Computation

Authors: Manuela Fischer, Jeff Giliberti, and Christoph Grunau

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
A long line of research about connectivity in the Massively Parallel Computation model has culminated in the seminal works of Andoni et al. [FOCS'18] and Behnezhad et al. [FOCS'19]. They provide a randomized algorithm for low-space MPC with conjectured to be optimal round complexity O(log D + log log_{m/n} n) and O(m) space, for graphs on n vertices with m edges and diameter D. Surprisingly, a recent result of Coy and Czumaj [STOC'22] shows how to achieve the same deterministically. Unfortunately, however, their algorithm suffers from large local computation time. We present a deterministic connectivity algorithm that matches all the parameters of the randomized algorithm and, in addition, significantly reduces the local computation time to nearly linear. Our derandomization method is based on reducing the amount of randomness needed to allow for a simpler efficient search. While similar randomness reduction approaches have been used before, our result is not only strikingly simpler, but it is the first to have efficient local computation. This is why we believe it to serve as a starting point for the systematic development of computation-efficient derandomization approaches in low-memory MPC.
Cite as

Manuela Fischer, Jeff Giliberti, and Christoph Grunau. Improved Deterministic Connectivity in Massively Parallel Computation. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.DISC.2022.22,
  author =	{Fischer, Manuela and Giliberti, Jeff and Grunau, Christoph},
  title =	{{Improved Deterministic Connectivity in Massively Parallel Computation}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.22},
  URN =		{urn:nbn:de:0030-drops-172138},
  doi =		{10.4230/LIPIcs.DISC.2022.22},
  annote =	{Keywords: Massively Parallel Computation, MPC, MapReduce, Deterministic Algorithms, Connectivity, Hitting Set, Maximum Matching, Derandomization}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact