License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2016.2
URN: urn:nbn:de:0030-drops-58307
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5830/
Go to the corresponding LIPIcs Volume Portal

Williams, Richard Ryan

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

pdf-format:
9.pdf (0.5 MB)

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(dK|F|epsilon)) 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 "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 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.

BibTeX - Entry

@InProceedings{williams:LIPIcs:2016:5830,
  author =	{Richard Ryan Williams},
  title =	{{Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Ran Raz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5830},
  URN =		{urn:nbn:de:0030-drops-58307},
  doi =		{10.4230/LIPIcs.CCC.2016.2},
  annote =	{Keywords: counting complexity, exponential-time hypothesis, interactive proofs, Merlin-Arthur games}
}

Keywords: counting complexity, exponential-time hypothesis, interactive proofs, Merlin-Arthur games
Collection: 31st Conference on Computational Complexity (CCC 2016)
Issue Date: 2016
Date of publication: 19.05.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI