--- _id: '9541' abstract: - lang: eng text: The Massively Parallel Computation (MPC) model is an emerging model that 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 O(nɛ) space on each machine for any constant ɛ > 0. These algorithms also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel et al. [DISC’17]. acknowledgement: "Institute of Science and Technology Austria (IST Austria). Email: peter.davies@ist.ac.at. Work partially\r\ndone at the Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP),University of Warwick. Research partially supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 754411, the Centre for Discrete Mathematics and its Applications, a Weizmann-UK Making Connections Grant, and EPSRC award EP/N011163/1." article_number: '16' article_processing_charge: No article_type: original author: - first_name: Artur full_name: Czumaj, Artur last_name: Czumaj - first_name: Peter full_name: Davies, Peter id: 11396234-BB50-11E9-B24C-90FCE5697425 last_name: Davies orcid: 0000-0002-5646-9524 - first_name: Merav full_name: Parter, Merav last_name: Parter citation: ama: Czumaj A, Davies P, Parter M. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms. 2021;17(2). doi:10.1145/3451992 apa: Czumaj, A., Davies, P., & Parter, M. (2021). Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms. Association for Computing Machinery. https://doi.org/10.1145/3451992 chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” ACM Transactions on Algorithms. Association for Computing Machinery, 2021. https://doi.org/10.1145/3451992. ieee: A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing massively parallel computation with low space,” ACM Transactions on Algorithms, vol. 17, no. 2. Association for Computing Machinery, 2021. ista: Czumaj A, Davies P, Parter M. 2021. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms. 17(2), 16. mla: Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” ACM Transactions on Algorithms, vol. 17, no. 2, 16, Association for Computing Machinery, 2021, doi:10.1145/3451992. short: A. Czumaj, P. Davies, M. Parter, ACM Transactions on Algorithms 17 (2021). date_created: 2021-06-10T19:31:05Z date_published: 2021-06-01T00:00:00Z date_updated: 2024-02-28T12:53:09Z day: '01' ddc: - '000' department: - _id: DaAl doi: 10.1145/3451992 ec_funded: 1 external_id: arxiv: - '1912.05390' isi: - '000661311300006' file: - access_level: open_access checksum: a21c627683890c309a68f6389302c408 content_type: application/pdf creator: pdavies date_created: 2021-06-10T19:33:56Z date_updated: 2021-06-10T19:33:56Z file_id: '9542' file_name: MISMM-arxiv.pdf file_size: 587404 relation: main_file success: 1 file_date_updated: 2021-06-10T19:33:56Z has_accepted_license: '1' intvolume: ' 17' isi: 1 issue: '2' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1912.05390 month: '06' oa: 1 oa_version: Submitted Version project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: ACM Transactions on Algorithms publication_identifier: eissn: - 1549-6333 issn: - 1549-6325 publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' related_material: record: - id: '7802' relation: earlier_version status: public status: public title: Graph sparsification for derandomizing massively parallel computation with low space type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 17 year: '2021' ...