2016/01/18 by Williams, Ryan · 2 citations
#Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1601.04743
We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit C(x1,…,xn) of size s and degree d over a field \mathbb F, and any inputs a1,…,aK ∈ \mathbb Fn, \bullet the Prover sends the Verifier the values C(a1), …, C(aK) ∈ \mathbb F and a proof of O(K ⋅ d) length, and \bullet the Verifier tosses \textrmpoly(log(dK|\mathbb F|/ε)) coins and can check the proof in about O(K ⋅(n + d) + s) time, with probability of error less than ε. 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 cn 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 22n/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 nk/2+O(1)-time for counting k-cliques in graphs. We point to some potential future directions for refuting the Nondeterministic Strong ETH.