English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Motivated by recent progress on symmetry breaking problems such as maximalindependent set (MIS) and maximal matching in the low-memory Massively ParallelComputation (MPC) model (e.g., Behnezhad et al.~PODC 2019; Ghaffari-Uitto SODA2019), we investigate the complexity of ruling set problems in this model. TheMPC model has become very popular as a model for large-scale distributedcomputing and it comes with the constraint that the memory-per-machine isstrongly sublinear in the input size. For graph problems, extremely fast MPCalgorithms have been designed assuming $\tilde{\Omega}(n)$ memory-per-machine,where $n$ is the number of nodes in the graph (e.g., the $O(\log\log n)$ MISalgorithm of Ghaffari et al., PODC 2018). However, it has proven much moredifficult to design fast MPC algorithms for graph problems in the low-memoryMPC model, where the memory-per-machine is restricted to being stronglysublinear in the number of nodes, i.e., $O(n^\eps)$ for $0 < \eps < 1$.  In this paper, we present an algorithm for the 2-ruling set problem, runningin $\tilde{O}(\log^{1/6} \Delta)$ rounds whp, in the low-memory MPC model. Wethen extend this result to $\beta$-ruling sets for any integer $\beta > 1$.Specifically, we show that a $\beta$-ruling set can be computed in thelow-memory MPC model with $O(n^\eps)$ memory-per-machine in $\tilde{O}(\beta\cdot \log^{1/(2^{\beta+1}-2)} \Delta)$ rounds, whp. From this it immediatelyfollows that a $\beta$-ruling set for $\beta = \Omega(\log\log\log\Delta)$-ruling set can be computed in in just $O(\beta \log\log n)$ roundswhp. The above results assume a total memory of $\tilde{O}(m + n^{1+\eps})$. Wealso present algorithms for $\beta$-ruling sets in the low-memory MPC modelassuming that the total memory over all machines is restricted to$\tilde{O}(m)$.

Sample-and-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model