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:

$\bullet$ Certifying that a list of $n$ integers has no 3-SUM solution can be done in Merlin-Arthur time $\tilde{O}(n)$. Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in $\tilde{O}(n^{1.5})$ time (that is, there is a proof system with proofs of length $\tilde{O}(n^{1.5})$ and a deterministic verifier running in $\tilde{O}(n^{1.5})$ time).

$\bullet$ 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 $\tilde O(n^{\lceil k/2\rceil })$ (where $k\ge 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 $\tilde O(m)$. Previous Merlin-Arthur protocols by Williams [CCC'16] and Bj\"orklund and Kaski [PODC'16] could only count $k$-cliques in unweighted graphs, and had worse running times for small $k$.

$\bullet$ Computing the All-Pairs Shortest Distances matrix for an $n$-node graph can be done in Merlin-Arthur time $\tilde{O}(n^2)$. Note this is optimal, as the matrix can have $\Omega(n^2)$ nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an $\tilde{O}(n^{2.94})$ nondeterministic time algorithm.

$\bullet$ Certifying that an $n$-variable $k$-CNF is unsatisfiable can be done in Merlin-Arthur time $2^{n/2 - n/O(k)}$. We also observe an algebrization barrier for the previous $2^{n/2}\cdot \mathrm{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 $2^{n/2}/n^{\omega(1)}$ time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol.

$\bullet$ Certifying a Quantified Boolean Formula is true can be done in Merlin-Arthur time $2^{4n/5}\cdot \mathrm{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 $2^{2n/3}\cdot\mathrm{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 $2^{n/3}\cdot\mathrm{poly}(n)$, improving on the previous best protocol by Nederlof [IPL 2017] which took $2^{0.49991n}\cdot\mathrm{poly}(n)$ time.

Added citations

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:

$\bullet$ Certifying that a list of $n$ integers has no 3-SUM solution can be done in Merlin-Arthur time $\tilde{O}(n)$. Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in $\tilde{O}(n^{1.5})$ time (that is, there is a proof system with proofs of length $\tilde{O}(n^{1.5})$ and a deterministic verifier running in $\tilde{O}(n^{1.5})$ time).

$\bullet$ 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 $\tilde O(n^{\lceil k/2\rceil })$ (where $k\ge 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 $\tilde O(m)$. Previous Merlin-Arthur protocols by Williams [CCC'16] and Bj\"orklund and Kaski [PODC'16] could only count $k$-cliques in unweighted graphs, and had worse running times for small $k$.

$\bullet$ Computing the All-Pairs Shortest Distances matrix for an $n$-node graph can be done in Merlin-Arthur time $\tilde{O}(n^2)$. Note this is optimal, as the matrix can have $\Omega(n^2)$ nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an $\tilde{O}(n^{2.94})$ nondeterministic time algorithm.

$\bullet$ Certifying that an $n$-variable $k$-CNF is unsatisfiable can be done in Merlin-Arthur time $2^{n/2 - n/O(k)}$. We also observe an algebrization barrier for the previous $2^{n/2}\cdot \mathrm{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 $2^{n/2}/n^{\omega(1)}$ time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol.

$\bullet$ Certifying a Quantified Boolean Formula is true can be done in Merlin-Arthur time $2^{4n/5}\cdot \mathrm{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 $2^{2n/3}\cdot\mathrm{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 $2^{n/3}\cdot\mathrm{poly}(n)$, improving on the previous best protocol by Nederlof [IPL 2017] which took $2^{0.49991n}\cdot\mathrm{poly}(n)$ time.