Strong ETH Breaks With Merlin and Arthur: Short Non Interactive Proofs of Batch Evaluation
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.
Computational Complexity Conference