Papers › Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation
Ryan Williams
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit C(x₁,…,xₙ) of size s and degree d over a field 𝔽, and any inputs a₁,…,a_K ∈𝔽ⁿ, ∙ the Prover sends the Verifier the values C(a₁), …, C(a_K) ∈𝔽 and a proof of Õ(K ·d) length, and ∙ the Verifier tosses poly(log(dK|𝔽|/ε)) coins and can check the proof in about Õ(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 cⁿ 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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections