Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Graph sparsification for derandomizing massively parallel computation with low space

Tools
- Tools
+ Tools

Czumaj, Artur, Davies, Peter and Parter, Merav (2021) Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms, 17 (2). 16. doi:10.1145/3451992 ISSN 1549-6325.

[img]
Preview
PDF
WRAP-graph-sparsification-derandomizing-massively-parallel-computation-low space-Czumaj-2021.pdf - Accepted Version - Requires a PDF viewer.

Download (1348Kb) | Preview
Official URL: https://doi.org/10.1145/3451992

Request Changes to record.

Abstract

The Massively Parallel Computation (MPC) model is an emerging model which distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space.

Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms.

A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph.

Using this framework to derandomize the well-known algorithm of Luby [SICOMP’86], we obtain O(log Δ+ log log n)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with

Item Type: Journal Article
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Distributed algorithms, Parallel algorithms , Graph algorithms , Numbers, Random, Computational complexity, Parallel processing (Electronic computers)
Journal or Publication Title: ACM Transactions on Algorithms
Publisher: ACM
ISSN: 1549-6325
Official Date: 29 May 2021
Dates:
DateEvent
29 May 2021Published
1 May 2021Completion
20 February 2021Accepted
Volume: 17
Number: 2
Article Number: 16
DOI: 10.1145/3451992
Status: Peer Reviewed
Publication Status: Published
Reuse Statement (publisher, data, author rights): © ACM, 2021. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Algorithms, 17 (2). 16. http://doi.acm.org/10.1145/10.1145/3451992
Access rights to Published version: Restricted or Subscription Access
Copyright Holders: Association for Computing Machinery (ACM)
Date of first compliant deposit: 8 June 2021
Date of first compliant Open Access: 9 June 2021
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
DIMAPUniversity of Warwickhttp://dx.doi.org/10.13039/501100000741
Making Connections Grant,Weizmann UKhttp://dx.doi.org/10.13039/100014383
EP/N011163/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
UNSPECIFIEDIBM Center for the Business of Governmenthttp://dx.doi.org/10.13039/100014026
754411[ERC] Horizon 2020 Framework Programmehttp://dx.doi.org/10.13039/100010661
713238Minerva Foundationhttp://dx.doi.org/10.13039/501100001658
Is Part Of: 1
Open Access Version:
  • ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us