Document Open Access Logo

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

Authors Shyan Akmal , Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.3.pdf
  • Filesize: 0.91 MB
  • 25 pages

Document Identifiers

Author Details

Shyan Akmal
  • MIT, EECS and CSAIL, Cambridge, MA, USA
Lijie Chen
  • MIT, EECS and CSAIL, Cambridge, MA, USA
Ce Jin
  • MIT, EECS and CSAIL, Cambridge, MA, USA
Malvika Raj
  • University of California Berkeley, CA, USA
Ryan Williams
  • MIT, EECS and CSAIL, Cambridge, MA, USA

Funding

Supported by NSF CCF-1909429, NSF CCF-2127597, and NSF CCF-2129139.
  • Akmal, Shyan: Additionally supported by a Siebel Scholarship.
  • Chen, Lijie: Additionally supported by an IBM Fellowship.

Acknowledgements

We thank Virginia Vassilevska Williams for offering helpful comments on early versions of our arguments. We thank Jesper Nederlof for answering a question about his Merlin-Arthur protocol for Subset Sum [Jesper Nederlof, 2021].

Cite AsGet BibTex

Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, and Ryan Williams. Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 3:1-3:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.3

Abstract

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). 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 k-cliques with total edge weight equal to zero in an n-node graph can be done in Merlin-Arthur 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 zero-weight triangles in an m-edge graph can be done in Merlin-Arthur time Õ(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²). 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 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}⋅ 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^{ω(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 2^{4n/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 2^{2n/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 2^{n/3}⋅poly(n), improving on the previous best protocol by Nederlof [IPL 2017] which took 2^{0.49991n}⋅poly(n) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Fine-grained complexity
  • Merlin-Arthur proofs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1):2:1-2:54, 2009. URL: https://doi.org/10.1145/1490270.1490272.
  2. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is Valiant’s parser. SIAM J. Comput., 47(6):2527-2555, 2018. URL: https://doi.org/10.1137/16M1061771.
  3. Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemysław Uznański, and Daniel Wolleb-Graf. Faster Algorithms for All-Pairs Bounded Min-Cuts. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), pages 7:1-7:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.7.
  4. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 1681-1697, 2015. URL: https://doi.org/10.1137/1.9781611973730.112.
  5. Amir Abboud, Richard Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 218-230, 2015. URL: https://doi.org/10.1137/1.9781611973730.17.
  6. Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, and Ryan Williams. Improved Merlin-Arthur protocols for central problems in fine-grained complexity. Electron. Colloquium Comput. Complex., 2021. URL: https://eccc.weizmann.ac.il/report/2021/165/.
  7. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 522-539, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  8. Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Dense Subset Sum may be the hardest. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), pages 13:1-13:14, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.13.
  9. Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight hardness results for maximum weight rectangles. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pages 81:1-81:13, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.81.
  10. Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 483-496, 2017. URL: https://doi.org/10.1145/3055399.3055466.
  11. Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Proofs of work from worst-case assumptions. In Proceedings of the 38th Annual International Cryptology Conference (CRYPTO 2018), Part I, pages 789-819, 2018. URL: https://doi.org/10.1007/978-3-319-96884-1_26.
  12. Andreas Björklund and Petteri Kaski. How proofs are prepared at Camelot: Extended abstract. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC 2016), pages 391-400, 2016. URL: https://doi.org/10.1145/2933057.2933101.
  13. Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. Listing triangles. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), Part I, pages 223-234, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_19.
  14. Enric Boix-Adserà, Matthew S. Brennan, and Guy Bresler. The average-case complexity of counting cliques in Erdős-Rényi hypergraphs. In Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 1256-1280, 2019. URL: https://doi.org/10.1109/FOCS.2019.00078.
  15. David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Pǎtraşcu, and Perouz Taslakian. Necklaces, convolutions, and X+Y. Algorithmica, 69(2):294-314, 2014. URL: https://doi.org/10.1007/s00453-012-9734-3.
  16. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS 2016), pages 261-270, 2016. URL: https://doi.org/10.1145/2840728.2840746.
  17. Amit Chakrabarti and Prantar Ghosh. Streaming verification of graph computations via graph structure. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of LIPIcs, pages 70:1-70:20, 2019. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.70.
  18. Amit Chakrabarti, Prantar Ghosh, and Justin Thaler. Streaming verification for graph problems: Optimal tradeoffs and nonlinear sketches. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), volume 176 of LIPIcs, pages 22:1-22:23, 2020. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.22.
  19. Timothy M. Chan and R. Ryan Williams. Deterministic APSP, Orthogonal Vectors, and more: Quickly derandomizing Razborov-Smolensky. ACM Trans. Algorithms, 17(1):2:1-2:14, 2021. URL: https://doi.org/10.1145/3402926.
  20. Lijie Chen and Ryan Williams. An equivalence class for orthogonal vectors. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 21-40. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.2.
  21. Marek Cygan, Marcin Mucha, Karol Węgrzycki, and Michał Włodarczyk. On problems equivalent to (min, +)-convolution. ACM Trans. Algorithms, 15(1):14:1-14:25, 2019. URL: https://doi.org/10.1145/3293465.
  22. Mina Dalirrooyfard, Andrea Lincoln, and Virginia Vassilevska Williams. New techniques for proving fine-grained average-case hardness. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020), pages 774-785, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00077.
  23. Charles M. Fiduccia. Polynomial evaluation via the division algorithm: The fast Fourier transform revisited. In Proceedings of the 4th Annual ACM Symposium on Theory of Computing (STOC 1972), pages 88-93, 1972. URL: https://doi.org/10.1145/800152.804900.
  24. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Comput. Geom., 5:165-185, 1995. URL: https://doi.org/10.1016/0925-7721(95)00022-2.
  25. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for first-order properties on sparse structures with algorithmic applications. ACM Trans. Algorithms, 15(2):23:1-23:35, 2019. URL: https://doi.org/10.1145/3196275.
  26. Oded Goldreich and Guy N. Rothblum. Counting t-cliques: Worst-case to average-case reductions and direct interactive proof systems. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2018), pages 77-88, 2018. URL: https://doi.org/10.1109/FOCS.2018.00017.
  27. Mika Göös, Toniann Pitassi, and Thomas Watson. The landscape of communication complexity classes. Comput. Complex., 27(2):245-304, 2018. Google Scholar
  28. Shuichi Hirahara and Nobutaka Shimizu. Nearly optimal average-case complexity of counting bicliques under SETH. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 2346-2365, 2021. URL: https://doi.org/10.1137/1.9781611976465.140.
  29. Ellis Horowitz. A fast method for interpolation using preconditioning. Inf. Process. Lett., 1(4):157-163, 1972. URL: https://doi.org/10.1016/0020-0190(72)90050-6.
  30. Ellis Horowitz and Sartaj Sahni. Computing partitions with applications to the knapsack problem. J. ACM, 21(2):277-292, 1974. URL: https://doi.org/10.1145/321812.321823.
  31. Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. An axiomatic approach to algebrization. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009), pages 695-704, 2009. URL: https://doi.org/10.1145/1536414.1536509.
  32. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2001.1727.
  33. Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM J. Comput., 7(4):413-423, 1978. URL: https://doi.org/10.1137/0207033.
  34. Zahra Jafargholi and Emanuele Viola. 3SUM, 3XOR, triangles. Algorithmica, 74(1):326-343, 2016. URL: https://doi.org/10.1007/s00453-014-9946-9.
  35. Kiran S. Kedlaya and Christopher Umans. Fast polynomial factorization and modular composition. SIAM J. Comput., 40(6):1767-1802, 2011. URL: https://doi.org/10.1137/08073408X.
  36. Hartmut Klauck. On Arthur Merlin games in communication complexity. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC 2011), pages 189-199, 2011. Google Scholar
  37. Marvin Künnemann. On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018), pages 56:1-56:16, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.56.
  38. Rio LaVigne, Andrea Lincoln, and Virginia Vassilevska Williams. Public-key cryptography in the fine-grained setting. In Proceedings of the 39th Annual International Cryptology Conference (CRYPTO 2019), Part III, pages 605-635, 2019. URL: https://doi.org/10.1007/978-3-030-26954-8_20.
  39. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pages 296-303, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  40. Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 1236-1252, 2018. URL: https://doi.org/10.1137/1.9781611975031.80.
  41. Jesper Nederlof. A short note on Merlin-Arthur protocols for subset sum. Inf. Process. Lett., 118:15-16, 2017. URL: https://doi.org/10.1016/j.ipl.2016.09.002.
  42. Jesper Nederlof. Personal communication, 2021. Google Scholar
  43. Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415-419, 1985. Google Scholar
  44. Mihai Pǎtraşcu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), pages 603-610, 2010. URL: https://doi.org/10.1145/1806689.1806772.
  45. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Efficient batch verification for UP. In Proceedings of the 33rd Computational Complexity Conference (CCC 2018), pages 22:1-22:23, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.22.
  46. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. SIAM J. Comput., 50(3), 2021. URL: https://doi.org/10.1137/16M1096773.
  47. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC 2012), pages 887-898, 2012. URL: https://doi.org/10.1145/2213977.2214056.
  48. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians, pages 3447-3487. World Scientific, 2018. Google Scholar
  49. Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, and Huacheng Yu. Finding four-node subgraphs in triangle time. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 1671-1680, 2015. URL: https://doi.org/10.1137/1.9781611973730.111.
  50. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. J. ACM, 65(5), August 2018. URL: https://doi.org/10.1145/3186893.
  51. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput., 42(3):831-854, 2013. URL: https://doi.org/10.1137/09076619X.
  52. Virginia Vassilevska Williams and Yinzhan Xu. Monochromatic triangles, triangle listing and APSP. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020), pages 786-797, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00078.
  53. R. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. SIAM J. Comput., 47(5):1965-1985, 2018. URL: https://doi.org/10.1137/15M1024524.
  54. Richard Ryan Williams. Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In Proceedings of the 31st Conference on Computational Complexity (CCC 2016), pages 2:1-2:17, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact