Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation

By Richard Ryan Williams. 2016

65 citations recorded by the source corpus.

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ and degree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in {\mathbb F}^n$, $\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K) \in {\mathbb F}$ and a proof of $\tilde{O}(K \cdot d)$ length, and $\bullet$ the Verifier tosses $\textrm{poly}(\log(dK|{\mathbb F}|/\varepsilon))$ coins and can check the proof in about $\tilde{O}(K \cdot(n + d) + s)$ time, with probability of error less than $\varepsilon$. For small degree $d$, this "Merlin-Arthur" proof system (a.k.a. MA-proof system) runs in nearly-linear time, and has many applications. For example, we obtain MA-proof systems that run in $c^{n}$ time (for various $c < 2$) for the Permanent, $\#$Circuit-SAT for all sublinear-depth circuits, counting Hamiltonian cycles, and infeasibility of $0$-$1$ linear programs. In general, the value of any polynomial in Valiant's class ${\sf VP}$ can be certified faster than "exhaustive summation" over all possible assignments. These results strongly refute a Merlin-Arthur Strong ETH and Arthur-Merlin Strong ETH posed by Russell Impagliazzo and others. We also give a three-round (AMA) proof system for quantified Boolean formulas running in $2^{2n/3+o(n)}$ time, nearly-linear time MA-proof systems for counting orthogonal vectors in a collection and finding Closest Pairs in the Hamming metric, and a MA-proof system running in $n^{k/2+O(1)}$-time for counting $k$-cliques in graphs. We point to some potential future directions for refuting the Nondeterministic Strong ETH.

Subfields: Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

Citations in the corpus

Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “The core idea behind Prio is reminiscent of techniques used in verifiable computation [16, 37, 62, 69, 97, 115, 116, 119], but in reverse—the client proves to a set of servers that it computed a function correctly.”
Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (2019, methodology): “3 is a generalization of the linear PCP implicit in the construction used in the Prio system [43] and is closely related to a Merlin-Arthur proof system of Williams for batch verification of circuit evaluation [122].”