Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds

Mohsen Ghaffari, Fabian Kuhn, Jara Uitto

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

Abstrakti

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.
AlkuperäiskieliEnglanti
OtsikkoProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
KustantajaIEEE
Sivut1650-1663
Sivumäärä14
ISBN (elektroninen)9781728149523
DOI - pysyväislinkit
TilaJulkaistu - 6 tammikuuta 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaAnnual Symposium on Foundations of Computer Science - Hotel Hyatt Regency Baltimore Inner Harbor, Baltimore, Yhdysvallat
Kesto: 9 marraskuuta 201912 marraskuuta 2019
http://focs2019.cs.jhu.edu/

Conference

ConferenceAnnual Symposium on Foundations of Computer Science
LyhennettäFOCS
MaaYhdysvallat
KaupunkiBaltimore
Ajanjakso09/11/201912/11/2019
www-osoite

Sormenjälki Sukella tutkimusaiheisiin 'Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • Siteeraa tätä

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