ECCC-Report TR21-165https://eccc.weizmann.ac.il/report/2021/165Comments and Revisions published for TR21-165en-usMon, 29 Nov 2021 19:18:29 +0200
Revision 1
| Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity |
Shyan Akmal,
Lijie Chen,
Ce Jin,
Malvika Raj,
Ryan Williams
https://eccc.weizmann.ac.il/report/2021/165#revision1In 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.Mon, 29 Nov 2021 19:18:29 +0200https://eccc.weizmann.ac.il/report/2021/165#revision1
Paper TR21-165
| Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity |
Shyan Akmal,
Lijie Chen,
Ce Jin,
Malvika Raj,
Ryan Williams
https://eccc.weizmann.ac.il/report/2021/165In 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.Sun, 21 Nov 2021 02:21:01 +0200https://eccc.weizmann.ac.il/report/2021/165