License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2019.33
URN: urn:nbn:de:0030-drops-118194
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11819/
Nanongkai, Danupon ;
Scquizzato, Michele
Equivalence Classes and Conditional Hardness in Massively Parallel Computations
Abstract
The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attention over the past few years, especially in the context of classical graph problems. So far, the only way to argue lower bounds for this model is to condition on conjectures about the hardness of some specific problems, such as graph connectivity on promise graphs that are either one cycle or two cycles, usually called the one cycle vs. two cycles problem. This is unlike the traditional arguments based on conjectures about complexity classes (e.g., P ≠ NP), which are often more robust in the sense that refuting them would lead to groundbreaking algorithms for a whole bunch of problems.
In this paper we present connections between problems and classes of problems that allow the latter type of arguments. These connections concern the class of problems solvable in a sublogarithmic amount of rounds in the MPC model, denoted by MPC(o(log N)), and some standard classes concerning space complexity, namely L and NL, and suggest conjectures that are robust in the sense that refuting them would lead to many surprisingly fast new algorithms in the MPC model. We also obtain new conditional lower bounds, and prove new reductions and equivalences between problems in the MPC model.
BibTeX - Entry
@InProceedings{nanongkai_et_al:LIPIcs:2020:11819,
author = {Danupon Nanongkai and Michele Scquizzato},
title = {{Equivalence Classes and Conditional Hardness in Massively Parallel Computations}},
booktitle = {23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
pages = {33:1--33:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-133-7},
ISSN = {1868-8969},
year = {2020},
volume = {153},
editor = {Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11819},
URN = {urn:nbn:de:0030-drops-118194},
doi = {10.4230/LIPIcs.OPODIS.2019.33},
annote = {Keywords: Massively parallel computation, conditional hardness, fine-grained complexity}
}
|
Keywords: |
|
Massively parallel computation, conditional hardness, fine-grained complexity |
|
Collection: |
|
23rd International Conference on Principles of Distributed Systems (OPODIS 2019) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.02.2020 |
