ML p(r)ior | How proofs are prepared at Camelot

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.
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-03-08

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

Highlights - Most important sentences from the article

2019-05-07

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

Highlights - Most important sentences from the article

2018-11-19
1811.07515 | cs.CC

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

Highlights - Most important sentences from the article

2018-07-12

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

Highlights - Most important sentences from the article

2016-10-11
1610.03383 | cs.DS

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-03-28

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

Highlights - Most important sentences from the article

2019-03-14

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

Highlights - Most important sentences from the article

2018-08-31

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2017-04-13

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

Highlights - Most important sentences from the article

2017-12-12

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

Highlights - Most important sentences from the article

2017-04-24
1704.07083 | cs.IT

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

Highlights - Most important sentences from the article