How proofs are prepared at camelot: [Extended Abstract]

Andreas Björklund, Petteri Kaski

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

9 Citations (Scopus)

Abstract

We study a design framework for robust, independently verifiable, and workload-balanced distributed algorithms working on a common input. The framework builds on recent noninteractive Merlin-Arthur proofs of batch evaluation of Williams [31st IEEE Colloquium on Computational Complexity (CCC'16, May 29-June 1, 2016, Tokyo), to appear] with the basic observation that Merlin's magic is not needed for batch evaluation: mere Knights can prepare the independently verifiable proof, in parallel, and with intrinsic errorcorrection. As our main technical result, we show that the κ-cliques in an n-vertex graph can be counted and verified in pernode O(n(ω+ϵ)κ/6) time and space on O(n(ω+ϵ)κ/6) compute nodes, for any constant ϵ > 0 and positive integer κ divisible by 6, where 2 ≤ ω <2:3728639 is the exponent of square matrix multiplication over the integers. This matches in total running time the best known sequential algorithm, due to Nesetr-il and Poljak [Comment. Math. Univ. Carolin. 26 (1985) 415-419], and considerably improves its space usage and parallelizability. Further results (only partly presented in this extended abstract) include novel algorithms for counting triangles in sparse graphs, computing the chromatic polynomial of a graph, and computing the Tutte polynomial of a graph.

Original languageEnglish
Title of host publicationPODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
PublisherACM
Pages391-400
Number of pages10
Volume25-28-July-2016
ISBN (Electronic)9781450339643
DOIs
Publication statusPublished - 25 Jul 2016
MoE publication typeA4 Article in a conference publication
EventACM Symposium on Principles of Distributed Computing - Chicago, United States
Duration: 25 Jul 201628 Jul 2016
Conference number: 35

Conference

ConferenceACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC
CountryUnited States
CityChicago
Period25/07/201628/07/2016

Keywords

  • Batch evaluation
  • Noninteractive proof
  • Parameterized clique
  • Reed-Solomon
  • Vector parallel
  • Verification

Fingerprint Dive into the research topics of 'How proofs are prepared at camelot: [Extended Abstract]'. Together they form a unique fingerprint.

  • Cite this

    Björklund, A., & Kaski, P. (2016). How proofs are prepared at camelot: [Extended Abstract]. In PODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Vol. 25-28-July-2016, pp. 391-400). ACM. https://doi.org/10.1145/2933057.2933101