Williams, Richard Ryan
Strong ETH Breaks With Merlin and Arthur: Short NonInteractive Proofs of Batch Evaluation
Abstract
We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit C(x_1,...,x_n) of size s and degree d over a field F, and any inputs a_1,...,a_K in F}^n,
 the Prover sends the Verifier the values C(a_1), ..., C(a_K) in F and a proof of ~O(K * d) length, and
 the Verifier tosses poly(log(dKFepsilon)) coins and can check the proof in about ~O}(K * (n + d) + s) time, with probability of error less than epsilon.
For small degree d, this "MerlinArthur" proof system (a.k.a. MAproof system) runs in nearlylinear time, and has many applications. For example, we obtain MAproof systems that run in c^{n} time (for various c < 2) for the Permanent, #CircuitSAT for all sublineardepth circuits, counting Hamiltonian cycles, and infeasibility of 01 linear programs. In general, the value of any polynomial in Valiant's class VP can be certified faster than "exhaustive summation" over all possible assignments. These results strongly refute a MerlinArthur Strong ETH and ArthurMerlin Strong ETH posed by Russell Impagliazzo and others.
We also give a threeround (AMA) proof system for quantified Boolean formulas running in 2^{2n/3+o(n)} time, nearlylinear time MAproof systems for counting orthogonal vectors in a collection and finding Closest Pairs in the Hamming metric, and a MAproof system running in n^{k/2+O(1)}time for counting kcliques in graphs.
We point to some potential future directions for refuting the Nondeterministic Strong ETH.
BibTeX  Entry
@InProceedings{williams:LIPIcs:2016:5830,
author = {Richard Ryan Williams},
title = {{Strong ETH Breaks With Merlin and Arthur: Short NonInteractive Proofs of Batch Evaluation}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {2:12:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5830},
URN = {urn:nbn:de:0030drops58307},
doi = {10.4230/LIPIcs.CCC.2016.2},
annote = {Keywords: counting complexity, exponentialtime hypothesis, interactive proofs, MerlinArthur games}
}
2016
Keywords: 

counting complexity, exponentialtime hypothesis, interactive proofs, MerlinArthur games 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 