Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Standard

Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. / Ghaffari, Mohsen; Kuhn, Fabian; Uitto, Jara.

Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE, 2020. p. 1650-1663 8948686.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Harvard

Ghaffari, M, Kuhn, F & Uitto, J 2020, Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. in Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019., 8948686, IEEE, pp. 1650-1663, Annual Symposium on Foundations of Computer Science, Baltimore, United States, 09/11/2019. https://doi.org/10.1109/FOCS.2019.00097

APA

Ghaffari, M., Kuhn, F., & Uitto, J. (2020). Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. In Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019 (pp. 1650-1663). [8948686] IEEE. https://doi.org/10.1109/FOCS.2019.00097

Vancouver

Ghaffari M, Kuhn F, Uitto J. Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. In Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE. 2020. p. 1650-1663. 8948686 https://doi.org/10.1109/FOCS.2019.00097

Author

Ghaffari, Mohsen ; Kuhn, Fabian ; Uitto, Jara. / Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE, 2020. pp. 1650-1663

Bibtex - Download

@inproceedings{375a638b48eb4c538ccaa1e75cb5f4fe,
title = "Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds",
abstract = "We present the first conditional hardness results for massively parallel algorithms for some central graph problems including (approximating) maximum matching, vertex cover, maximal independent set, and coloring. In some cases, these hardness results match or get close to the state of the art algorithms. Our hardness results are conditioned on a widely believed conjecture in massively parallel computation about the complexity of the connectivity problem. We also note that it is known that an unconditional variant of such hardness results might be somewhat out of reach for now, as it would lead to considerably improved circuit complexity lower bounds and would concretely imply that NC_1 is a proper subset of P. We obtain our conditional hardness result via a general method that lifts unconditional lower bounds from the well-studied LOCAL model of distributed computing to the massively parallel computation setting.",
author = "Mohsen Ghaffari and Fabian Kuhn and Jara Uitto",
year = "2020",
month = "1",
day = "6",
doi = "10.1109/FOCS.2019.00097",
language = "English",
pages = "1650--1663",
booktitle = "Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019",
publisher = "IEEE",
address = "United States",

}

RIS - Download

TY - GEN

T1 - Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds

AU - Ghaffari, Mohsen

AU - Kuhn, Fabian

AU - Uitto, Jara

PY - 2020/1/6

Y1 - 2020/1/6

N2 - We present the first conditional hardness results for massively parallel algorithms for some central graph problems including (approximating) maximum matching, vertex cover, maximal independent set, and coloring. In some cases, these hardness results match or get close to the state of the art algorithms. Our hardness results are conditioned on a widely believed conjecture in massively parallel computation about the complexity of the connectivity problem. We also note that it is known that an unconditional variant of such hardness results might be somewhat out of reach for now, as it would lead to considerably improved circuit complexity lower bounds and would concretely imply that NC_1 is a proper subset of P. We obtain our conditional hardness result via a general method that lifts unconditional lower bounds from the well-studied LOCAL model of distributed computing to the massively parallel computation setting.

AB - We present the first conditional hardness results for massively parallel algorithms for some central graph problems including (approximating) maximum matching, vertex cover, maximal independent set, and coloring. In some cases, these hardness results match or get close to the state of the art algorithms. Our hardness results are conditioned on a widely believed conjecture in massively parallel computation about the complexity of the connectivity problem. We also note that it is known that an unconditional variant of such hardness results might be somewhat out of reach for now, as it would lead to considerably improved circuit complexity lower bounds and would concretely imply that NC_1 is a proper subset of P. We obtain our conditional hardness result via a general method that lifts unconditional lower bounds from the well-studied LOCAL model of distributed computing to the massively parallel computation setting.

U2 - 10.1109/FOCS.2019.00097

DO - 10.1109/FOCS.2019.00097

M3 - Conference contribution

SP - 1650

EP - 1663

BT - Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019

PB - IEEE

ER -

ID: 38157421