Akmal, Shyan ;
Chen, Lijie ;
Jin, Ce ;
Raj, Malvika ;
Williams, Ryan
Improved MerlinArthur Protocols for Central Problems in FineGrained Complexity
Abstract
In a MerlinArthur 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 MerlinArthur proof systems for some key problems in finegrained complexity. In several cases our proof systems have optimal running time. Our main results include:
 Certifying that a list of n integers has no 3SUM solution can be done in MerlinArthur time Õ(n). Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in Õ(n^{1.5}) time (that is, there is a proof system with proofs of length Õ(n^{1.5}) and a deterministic verifier running in Õ(n^{1.5}) time).
 Counting the number of kcliques with total edge weight equal to zero in an nnode graph can be done in MerlinArthur time Õ(n^{⌈ k/2⌉}) (where k ≥ 3). For odd k, this bound can be further improved for sparse graphs: for example, counting the number of zeroweight triangles in an medge graph can be done in MerlinArthur time Õ(m). Previous MerlinArthur protocols by Williams [CCC'16] and Björklund and Kaski [PODC'16] could only count kcliques in unweighted graphs, and had worse running times for small k.
 Computing the AllPairs Shortest Distances matrix for an nnode graph can be done in MerlinArthur time Õ(n²). Note this is optimal, as the matrix can have Ω(n²) nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an Õ(n^{2.94}) nondeterministic time algorithm.
 Certifying that an nvariable kCNF is unsatisfiable can be done in MerlinArthur time 2^{n/2  n/O(k)}. We also observe an algebrization barrier for the previous 2^{n/2}⋅ poly(n)time MerlinArthur protocol of R. Williams [CCC'16] for #SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol for kUNSAT running in 2^{n/2}/n^{ω(1)} time. Therefore we have to exploit nonalgebrizing properties to obtain our new protocol.
 Certifying a Quantified Boolean Formula is true can be done in MerlinArthur time 2^{4n/5}⋅ poly(n). Previously, the only nontrivial result known along these lines was an ArthurMerlinArthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in 2^{2n/3}⋅poly(n) time. Due to the centrality of these problems in finegrained 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 MerlinArthur time 2^{n/3}⋅poly(n), improving on the previous best protocol by Nederlof [IPL 2017] which took 2^{0.49991n}⋅poly(n) time.
BibTeX  Entry
@InProceedings{akmal_et_al:LIPIcs.ITCS.2022.3,
author = {Akmal, Shyan and Chen, Lijie and Jin, Ce and Raj, Malvika and Williams, Ryan},
title = {{Improved MerlinArthur Protocols for Central Problems in FineGrained Complexity}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {3:13:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15599},
URN = {urn:nbn:de:0030drops155991},
doi = {10.4230/LIPIcs.ITCS.2022.3},
annote = {Keywords: Finegrained complexity, MerlinArthur proofs}
}
25.01.2022
Keywords: 

Finegrained complexity, MerlinArthur proofs 
Seminar: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Issue date: 

2022 
Date of publication: 

25.01.2022 