How Proofs are Prepared at Camelot
(2016) ACM Symposium on Principles of Distributed Computing (PODC '16) In PODC '16 Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing p.391400 Abstract
 We study a design framework for robust, independently verifiable, and workloadbalanced distributed algorithms working on a common input. The framework builds on recent noninteractive MerlinArthur proofs of batch evaluation of Williams~[31st IEEE Colloquium on Computational Complexity (CCC'16, May 29June 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 kcliques in an nvertex graph can be counted and verified in pernode 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 workloadbalanced distributed algorithms working on a common input. The framework builds on recent noninteractive MerlinArthur proofs of batch evaluation of Williams~[31st IEEE Colloquium on Computational Complexity (CCC'16, May 29June 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 kcliques in an nvertex graph can be counted and verified in pernode 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) 415419], 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:
http://lup.lub.lu.se/record/a13b6ca543d248c79c466de75d91fe14
 author
 Björklund, Andreas ^{LU} and Kaski, Petteri
 organization
 publishing date
 2016
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 PODC '16 Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
 pages
 391  400
 publisher
 ACM
 conference name
 ACM Symposium on Principles of Distributed Computing (PODC '16)
 external identifiers

 scopus:84984707539
 ISBN
 9781450339643
 DOI
 10.1145/2933057.2933101
 language
 English
 LU publication?
 yes
 id
 a13b6ca543d248c79c466de75d91fe14
 date added to LUP
 20160802 11:40:58
 date last changed
 20170730 05:13:33
@inproceedings{a13b6ca543d248c79c466de75d91fe14, abstract = {We study a design framework for robust, independently verifiable, and workloadbalanced distributed algorithms working on a common input. The framework builds on recent noninteractive MerlinArthur proofs of batch evaluation of Williams~[31st IEEE Colloquium on Computational Complexity (CCC'16, May 29June 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. <br/>As our main technical result, we show that the kcliques in an nvertex graph can be counted and verified in pernode 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) 415419], 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 = {9781450339643 }, language = {eng}, pages = {391400}, publisher = {ACM}, title = {How Proofs are Prepared at Camelot}, url = {http://dx.doi.org/10.1145/2933057.2933101}, year = {2016}, }