Engineering a delegatable and error-Tolerant algorithm for counting small subgraphs

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

1 Sitaatiot (Scopus)
43 Lataukset (Pure)

Abstrakti

We study the problem of counting the number of occurrences of a given six-vertex pattern graph S in an n-vertex host graph H. We engineer an open-source GPU implementation of a distributed algorithm design of Björklund and Kaski [PODC 2016] where (i) the execution of the algorithm can be delegated [Goldwasser, Kalai, and Rothblum, J. ACM 2015] to produce a noninteractive probabilistically checkable proof of correctness, and (ii) the execution of the algorithm when preparing the proof tolerates a controllable number of adversarial errors. Experiments with NVIDIA Tesla K80 and Tesla P100 Accelerators demonstrate that the framework is practical for inputs of up to 512 vertices, with proof checking being several orders of magnitude more efficient than preparing the proof; however, proof preparation still carries at least one order of magnitude overhead compared with just solving the problem.

AlkuperäiskieliEnglanti
Otsikko2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
Sivut184-198
Sivumäärä15
Vuosikerta2018-January
ISBN (elektroninen)9781611975055
DOI - pysyväislinkit
TilaJulkaistu - 2018
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaWorkshop on Algorithm Engineering and Experiments - New Orleans, Yhdysvallat
Kesto: 7 tammikuuta 20188 tammikuuta 2018
Konferenssinumero: 20

Workshop

WorkshopWorkshop on Algorithm Engineering and Experiments
LyhennettäALENEX
MaaYhdysvallat
KaupunkiNew Orleans
Ajanjakso07/01/201808/01/2018

Sormenjälki Sukella tutkimusaiheisiin 'Engineering a delegatable and error-Tolerant algorithm for counting small subgraphs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä