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

Research paper by **Ryan Williams**

Indexed on: **18 Jan '16**Published on: **18 Jan '16**Published in: **Computer Science - Computational Complexity**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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.