### How proofs are prepared at Camelot

**2016-02-03**

1602.01295 | cs.DS

We study a design framework for robust, independently verifiable, and
workload-balanced distributed algorithms working on a common input. An
algorithm based on the framework is essentially a distributed encoding
procedure for a Reed--Solomon code, which enables (a) robustness against
byzantine failures with intrinsic error-correction and identification of failed
nodes, and (b) independent randomized verification to check the entire
computation for correctness, which takes essentially no more resources than
each node individually contributes to the computation. The framework builds on
recent Merlin--Arthur proofs of batch evaluation of Williams~[{\em Electron.\
Colloq.\ Comput.\ Complexity}, Report TR16-002, January 2016] with the
observation that {\em Merlin's magic is not needed} for batch evaluation---mere
Knights can prepare the proof, in parallel, and with intrinsic
error-correction.
The contribution of this paper is to show that in many cases the verifiable
batch evaluation framework admits algorithms that match in total resource
consumption the best known sequential algorithm for solving the problem. As our
main result, we show that the $k$-cliques in an $n$-vertex graph can be counted
{\em and} verified in per-node $O(n^{(\omega+\epsilon)k/6})$ time and space on
$O(n^{(\omega+\epsilon)k/6})$ compute nodes, for any constant $\epsilon>0$ and
positive integer $k$ divisible by $6$, where $2\leq\omega<2.3728639$ is the
exponent of matrix multiplication. This matches in total running time the best
known sequential algorithm, due to Ne{\v{s}}et{\v{r}}il and Poljak [{\em
Comment.~Math.~Univ.~Carolin.}~26 (1985) 415--419], and considerably improves
its space usage and parallelizability. Further results include novel algorithms
for counting triangles in sparse graphs, computing the chromatic polynomial of
a graph, and computing the Tutte polynomial of a graph.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2018-01-22**

1801.07301 | cs.DS

In machine learning, classifiers are used to predict a class of a given query
based on an existing (… show more

**2019-01-27**

1901.09355 | cs.SC

In the sparse multiplication problem, one is asked to multiply two sparse
polynomials $f$ and $g$ in… show more

**2019-03-08**

1903.03278 | cs.SC

It is well known that for any finite Galois extension field $K/F$, with
Galois group $G = \mathrm{Ga… show more

**2019-05-07**

1905.02424 | cs.DS

In the Equal-Subset-Sum problem, we are given a set $S$ of $n$ integers and
the problem is to decide… show more

**2018-11-19**

1811.07515 | cs.CC

The polynomial method from circuit complexity has been applied to several
fundamental problems and o… show more

**2018-07-12**

1807.04496 | cs.DS

In this paper we develop an efficient procedure for computing a (scaled)
Hadamard product for \emph{… show more

**2016-10-11**

1610.03383 | cs.DS

Many randomized algorithms can be derandomized efficiently using either the
method of conditional ex… show more

**2017-06-16**

1706.05423 | math.CO

Given complex numbers $w_1, \ldots, w_n$, we define the weight $w(X)$ of a
set $X$ of 0-1 vectors as… show more

**2019-03-28**

1903.12165 | cs.DS

Graph sketching has emerged as a powerful technique for processing massive
graphs that change over t… show more

**2019-03-14**

1903.05956 | cs.DC

We design fast deterministic algorithms for distance computation in the
congested clique model. Our … show more

**2018-08-31**

1808.10787 | cs.DS

Let $\mathbb{F}[X]$ be the polynomial ring over the variables $X=\{x_1,x_2,
\ldots, x_n\}$. An ideal… show more

**2018-12-28**

1812.10917 | cs.DC

We explore the power of interactive proofs with a distributed verifier. In
this setting, the verifie… show more

**2019-01-21**

1901.07118 | cs.DS

An NP-hard graph problem may be intractable for general graphs but it could
be efficiently solvable … show more

**2017-04-13**

1704.04163 | cs.DS

Understanding the singular value spectrum of a matrix $A \in \mathbb{R}^{n
\times n}$ is a fundament… show more

**2017-12-12**

1712.04177 | cs.SC

Consider a zero-dimensional ideal $I$ in $\mathbb{K}[X_1,\dots,X_n]$.
Inspired by Faug\`ere and Mou'… show more

**2017-04-24**

1704.07083 | cs.IT

We present quasi-linear time systematic encoding algorithms for multiplicity
codes. The algorithms h… show more