Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

How Proofs are Prepared at Camelot

Björklund, Andreas LU and Kaski, Petteri (2016) ACM Symposium on Principles of Distributed Computing (PODC '16) p.391-400
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 error-correction.
As our main technical result, we show that the k-cliques in an n-vertex graph can be counted and verified in per-node O(n(ω+ε)k/6) time and space on O(n(ω+ε)k/6) compute nodes, for any constant ε>0 and positive... (More)
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 error-correction.
As our main technical result, we show that the k-cliques in an n-vertex graph can be counted and verified in per-node O(n(ω+ε)k/6) time and space on O(n(ω+ε)k/6) compute nodes, for any constant ε>0 and positive integer k 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 Nešetř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. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
PODC '16 Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
pages
391 - 400
publisher
Association for Computing Machinery (ACM)
conference name
ACM Symposium on Principles of Distributed Computing (PODC '16)
conference location
Chicago, United States
conference dates
2016-07-25 - 2016-07-28
external identifiers
  • scopus:84984707539
  • wos:000383741300053
ISBN
978-1-4503-3964-3
DOI
10.1145/2933057.2933101
language
English
LU publication?
yes
id
a13b6ca5-43d2-48c7-9c46-6de75d91fe14
date added to LUP
2016-08-02 11:40:58
date last changed
2022-03-16 07:27:34
@inproceedings{a13b6ca5-43d2-48c7-9c46-6de75d91fe14,
  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 error-correction. <br/>As our main technical result, we show that the k-cliques in an n-vertex graph can be counted and verified in per-node O(n(ω+ε)k/6) time and space on O(n(ω+ε)k/6) compute nodes, for any constant ε&gt;0 and positive integer k divisible by 6, where 2 ≤ ω &lt; 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 Nešetř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.}},
  author       = {{Björklund, Andreas and Kaski, Petteri}},
  booktitle    = {{PODC '16 Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing}},
  isbn         = {{978-1-4503-3964-3}},
  language     = {{eng}},
  pages        = {{391--400}},
  publisher    = {{Association for Computing Machinery (ACM)}},
  title        = {{How Proofs are Prepared at Camelot}},
  url          = {{http://dx.doi.org/10.1145/2933057.2933101}},
  doi          = {{10.1145/2933057.2933101}},
  year         = {{2016}},
}