Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity

In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include: Certifying that a list of n integers has no 3-SUM solution can be done in Merlin–Arthur time Õ(n) O~(n) . Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in Õ(n1.5) O~(n1.5) time (that is, there is a proof system with proofs of length Õ(n1.5) O~(n1.5) and a deterministic verifier running in Õ(n1.5) O~(n1.5) time). Counting the number of k -cliques with total edge weight equal to zero in an n -node graph can be done in Merlin–Arthur time Õ(nk/2) O~(n⌈k/2⌉) (where k≥ 3 k≥3 ). For odd k , this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in an m -edge graph can be done in Merlin–Arthur time Õ(m) O~(m) . Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only count k -cliques in unweighted graphs, and had worse running times for small k . Computing the All-Pairs Shortest Distances matrix for an n -node graph can be done in Merlin–Arthur time Õ(n²) O~(n2) . Note this is optimal, as the matrix can have Ω (n²) Ω(n2) nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an Õ(n2.94) O~(n2.94) nondeterministic time algorithm. Certifying that an n -variable k -CNF is unsatisfiable can be done in Merlin–Arthur time 2n/2 - n/O(k) 2n/2-n/O(k) . We also observe an algebrization barrier for the previous 2n/2· poly(n) 2n/2·poly(n) -time Merlin–Arthur protocol of R. Williams [CCC’16] for $$#$$ # SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol for k -UNSAT running in 2n/2/nω (1) 2n/2/nω(1) time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol. Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time 24n/5· poly(n) 24n/5·poly(n) . Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in 22n/3· poly(n) 22n/3·poly(n) time. Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution to n integers can be done in Merlin–Arthur time 2n/3· poly(n) 2n/3·poly(n)</mml: