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 (2020) Graph sparsification for derandomizing massively parallel computation with low space. In: 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020), Virtual, USA, 15-17 Jul 2020. Published in: SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures pp. 175-185. ISBN 9781450369350. doi:10.1145/3350755.3400282

[img]
Preview
PDF
WRAP-Graph-sparsification-derandomizing-massively-parallel-low-spaces-Czumaj-2020.pdf - Accepted Version - Requires a PDF viewer.

Download (1830Kb) | Preview
Official URL: https://doi.org/10.1145/3350755.3400282

Request Changes to record.

Abstract

Massively Parallel Computation (MPC) is an emerging model which distills core aspects of distributed and parallel computation. It was developed as a tool to solve (typically graph) problems in systems where input is distributed over many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. There are, however, no prior corresponding deterministic algorithms.

A major challenge in the sublinear space setting is that the local space of each machine may be too small to store all the edges incident to a single node. To overcome this barrier we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph with additional desired properties: degrees in the subgraph are sufficiently small that nodes’ neighborhoods can be stored on single machines, and solving the problem on the subgraph provides significant global progress towards solving the problem for the original input graph.

Using this framework to derandomize the well-known randomized algorithm of Luby [SICOMP’86], we obtain O(log(\Delta) + loglog(n))- round deterministic MPC algorithms for solving the fundamental problems of Maximal Matching and Maximal Independent Set with O(n epsilon) space on each machine for any constant epsilon > 0. Based on the recent work of Ghaffari et al. [FOCS’18], this additive O(loglog(n)) factor is conditionally essential. These algorithms can also be shown
to run in O(log(\Delta)) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log^2(\Delta)) rounds by Censor-Hillel et al. [DISC’17].

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH): Parallel computers, Distributed algorithms, Graph algorithms
Journal or Publication Title: SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures
Publisher: ACM
ISBN: 9781450369350
Official Date: July 2020
Dates:
DateEvent
July 2020Published
24 April 2020Accepted
Page Range: pp. 175-185
DOI: 10.1145/3350755.3400282
Status: Peer Reviewed
Publication Status: Published
Publisher Statement: Copyright © 2020 ACM.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 SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, July 2020 http://doi.acm.org/10.1145/3350755.3400282"
Access rights to Published version: Restricted or Subscription Access
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
EP/N011163/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
Making Connections GrantWeizmann UKhttp://dx.doi.org/10.13039/100014383
UNSPECIFIEDIBM Center for the Business of Governmenthttp://dx.doi.org/10.13039/100014026
UNSPECIFIEDCentre for Discrete Mathematics and its Applications, University of Warwick UNSPECIFIED
754411Horizon 2020 Framework Programmehttp://dx.doi.org/10.13039/100010661
Conference Paper Type: Paper
Title of Event: 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)
Type of Event: Conference
Location of Event: Virtual, USA
Date(s) of Event: 15-17 Jul 2020
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