{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:42:37Z","timestamp":1775054557624,"version":"3.50.1"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T00:00:00Z","timestamp":1676592000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T00:00:00Z","timestamp":1676592000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100015597","name":"Siebel Scholars Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100015597","id-type":"DOI","asserted-by":"publisher"}]},{"name":"IBM Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Fano Undergraduate Research and Innovation Scholarship at MIT"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,8]]},"abstract":"Abstract<\/jats:title>In a Merlin\u2013Arthur 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\u2019s proof plus the running time of Arthur. We provide new Merlin\u2013Arthur 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 ofn<\/jats:italic>integers has no 3-SUM solution can be done in Merlin\u2013Arthur time$$\\tilde{O}(n)$$<\/jats:tex-math>O<\/mml:mi>~<\/mml:mo><\/mml:mover>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in$$\\tilde{O}(n^{1.5})$$<\/jats:tex-math>O<\/mml:mi>~<\/mml:mo><\/mml:mover>(<\/mml:mo>n<\/mml:mi>1.5<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time (that is, there is a proof system with proofs of length$$\\tilde{O}(n^{1.5})$$<\/jats:tex-math>O<\/mml:mi>~<\/mml:mo><\/mml:mover>(<\/mml:mo>n<\/mml:mi>1.5<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and a deterministic verifier running in$$\\tilde{O}(n^{1.5})$$<\/jats:tex-math>O<\/mml:mi>~<\/mml:mo><\/mml:mover>(<\/mml:mo>n<\/mml:mi>1.5<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time).<\/jats:p><\/jats:list-item>Counting the number ofk<\/jats:italic>-cliques with total edge weight equal to zero in ann<\/jats:italic>-node graph can be done in Merlin\u2013Arthur time$${\\tilde{O}}(n^{\\lceil k\/2\\rceil })$$<\/jats:tex-math>O<\/mml:mi>~<\/mml:mo><\/mml:mover>(<\/mml:mo>n<\/mml:mi>\u2308<\/mml:mo>k<\/mml:mi>\/<\/mml:mo>2<\/mml:mn>\u2309<\/mml:mo><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>(where$$k\\ge 3$$<\/jats:tex-math>k<\/mml:mi>\u2265<\/mml:mo>3<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>). For oddk<\/jats:italic>, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm<\/jats:italic>-edge graph can be done in Merlin\u2013Arthur time$${\\tilde{O}}(m)$$<\/jats:tex-math>O<\/mml:mi>~<\/mml:mo><\/mml:mover>(<\/mml:mo>m<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Previous Merlin\u2013Arthur protocols by Williams [CCC\u201916] and Bj\u00f6rklund and Kaski [PODC\u201916] could only countk<\/jats:italic>-cliques in unweighted graphs, and had worse running times for smallk<\/jats:italic>.<\/jats:p><\/jats:list-item>Computing the All-Pairs Shortest Distances matrix for ann<\/jats:italic>-node graph can be done in Merlin\u2013Arthur time$$\\tilde{O}(n^2)$$<\/jats:tex-math>O<\/mml:mi>~<\/mml:mo><\/mml:mover>(<\/mml:mo>n<\/mml:mi>2<\/mml:mn><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Note this is optimal, as the matrix can have$$\\Omega (n^2)$$<\/jats:tex-math>\u03a9<\/mml:mi>(<\/mml:mo>n<\/mml:mi>2<\/mml:mn><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an$$\\tilde{O}(n^{2.94})$$<\/jats:tex-math>O<\/mml:mi>~<\/mml:mo><\/mml:mover>(<\/mml:mo>n<\/mml:mi>2.94<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>nondeterministic time algorithm.<\/jats:p><\/jats:list-item>Certifying that ann<\/jats:italic>-variablek<\/jats:italic>-CNF is unsatisfiable can be done in Merlin\u2013Arthur time$$2^{n\/2 - n\/O(k)}$$<\/jats:tex-math>2<\/mml:mn>n<\/mml:mi>\/<\/mml:mo>2<\/mml:mn>-<\/mml:mo>n<\/mml:mi>\/<\/mml:mo>O<\/mml:mi>(<\/mml:mo>k<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We also observe an algebrization barrier for the previous$$2^{n\/2}\\cdot \\textrm{poly}(n)$$<\/jats:tex-math>2<\/mml:mn>n<\/mml:mi>\/<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:msup>\u00b7<\/mml:mo>poly<\/mml:mtext>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time Merlin\u2013Arthur protocol of R.\u00a0Williams [CCC\u201916] for$$\\#$$<\/jats:tex-math>#<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula>SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol fork<\/jats:italic>-UNSAT running in$$2^{n\/2}\/n^{\\omega (1)}$$<\/jats:tex-math>2<\/mml:mn>n<\/mml:mi>\/<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:msup>\/<\/mml:mo>n<\/mml:mi>\u03c9<\/mml:mi>(<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol.<\/jats:p><\/jats:list-item>Certifying a Quantified Boolean Formula is true can be done in Merlin\u2013Arthur time$$2^{4n\/5}\\cdot \\textrm{poly}(n)$$<\/jats:tex-math>2<\/mml:mn>4<\/mml:mn>n<\/mml:mi>\/<\/mml:mo>5<\/mml:mn><\/mml:mrow><\/mml:msup>\u00b7<\/mml:mo>poly<\/mml:mtext>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Previously, the only nontrivial result known along these lines was an Arthur\u2013Merlin\u2013Arthur protocol (where Merlin\u2019s proof depends on some of Arthur\u2019s coins) running in$$2^{2n\/3}\\cdot \\textrm{poly}(n)$$<\/jats:tex-math>2<\/mml:mn>2<\/mml:mn>n<\/mml:mi>\/<\/mml:mo>3<\/mml:mn><\/mml:mrow><\/mml:msup>\u00b7<\/mml:mo>poly<\/mml:mtext>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time.<\/jats:p><\/jats:list-item><\/jats:list>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 ton<\/jats:italic>integers can be done in Merlin\u2013Arthur time$$2^{n\/3}\\cdot \\textrm{poly}(n)$$<\/jats:tex-math>2<\/mml:mn>n<\/mml:mi>\/<\/mml:mo>3<\/mml:mn><\/mml:mrow><\/mml:msup>\u00b7<\/mml:mo>poly<\/mml:mtext>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, improving on the previous best protocol by Nederlof [IPL 2017] which took$$2^{0.49991n}\\cdot \\textrm{poly}(n)$$<\/jats:tex-math>2<\/mml:mn>0.49991<\/mml:mn>n<\/mml:mi><\/mml:mrow><\/mml:msup>\u00b7<\/mml:mo>poly<\/mml:mtext>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time.<\/jats:p>","DOI":"10.1007\/s00453-023-01102-6","type":"journal-article","created":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T13:57:28Z","timestamp":1676642248000},"page":"2395-2426","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Improved Merlin\u2013Arthur Protocols for Central Problems in Fine-Grained Complexity"],"prefix":"10.1007","volume":"85","author":[{"given":"Shyan","family":"Akmal","sequence":"first","affiliation":[]},{"given":"Lijie","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Ce","family":"Jin","sequence":"additional","affiliation":[]},{"given":"Malvika","family":"Raj","sequence":"additional","affiliation":[]},{"given":"Ryan","family":"Williams","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,17]]},"reference":[{"issue":"6","key":"1102_CR1","doi-asserted-by":"publisher","first-page":"2527","DOI":"10.1137\/16M1061771","volume":"47","author":"A Abboud","year":"2018","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: If the current clique algorithms are optimal, so is Valiant\u2019s parser. SIAM J. Comput. 47(6), 2527\u20132555 (2018)","journal-title":"SIAM J. Comput."},{"key":"1102_CR2","unstructured":"Abboud, A., Georgiadis, L., Italiano, G.F., Krauthgamer, R., Parotsidis, N., Trabelsi, O., Uzna\u0144ski, P., Wolleb-Graf, D.: Faster algorithms for all-pairs bounded min-cuts. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), pp. 7:1\u20137:15 (2019)"},{"key":"1102_CR3","doi-asserted-by":"crossref","unstructured":"Abboud, A., Grandoni, F., Williams, V.V.: Subcubic equivalences between graph centrality problems, APSP and diameter. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 1681\u20131697 (2015)","DOI":"10.1137\/1.9781611973730.112"},{"key":"1102_CR4","unstructured":"Austrin, P., Koivisto, M., Kaski, P., Nederlof, J.: Dense subset sum may be the hardest. In:Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), pp. 13:1\u201313:14 (2016)"},{"key":"1102_CR5","doi-asserted-by":"crossref","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pp. 522\u2013539 (2021)","DOI":"10.1137\/1.9781611976465.32"},{"issue":"1","key":"1102_CR6","doi-asserted-by":"publisher","first-page":"2:1","DOI":"10.1145\/1490270.1490272","volume":"1","author":"S Aaronson","year":"2009","unstructured":"Aaronson, S., Wigderson, A.: Algebrization: a new barrier in complexity theory. ACM Trans. Comput. Theory 1(1), 2:1-2:54 (2009)","journal-title":"ACM Trans. Comput. Theory"},{"key":"1102_CR7","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, R., Yu, H.: More applications of the polynomial method to algorithm design. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 218\u2013230 (2015)","DOI":"10.1137\/1.9781611973730.17"},{"key":"1102_CR8","doi-asserted-by":"crossref","unstructured":"Boix-Adser\u00e0, E., Brennan M.S., Bresler, G.: The average-case complexity of counting cliques in Erd\u0151s\u2013R\u00e9nyi hypergraphs. In: Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2019), pp. 1256\u20131280 (2019)","DOI":"10.1109\/FOCS.2019.00078"},{"issue":"2","key":"1102_CR9","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/s00453-012-9734-3","volume":"69","author":"D Bremner","year":"2014","unstructured":"Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., P\u01cetra\u015fcu, M., Taslakian, P.: Necklaces, convolutions, and X+Y. Algorithmica 69(2), 294\u2013314 (2014)","journal-title":"Algorithmica"},{"key":"1102_CR10","unstructured":"Backurs, A., Dikkala, N., Tzamos, C.: Tight hardness results for maximum weight rectangles. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pp. 81:1\u201381:13 (2016)"},{"key":"1102_CR11","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Kaski, P.: How proofs are prepared at Camelot: extended abstract. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC 2016), pp. 391\u2013400 (2016)","DOI":"10.1145\/2933057.2933101"},{"key":"1102_CR12","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Pagh, R., Williams, V.V., Zwick, U.: Listing triangles. In: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), Part I, pp. 223\u2013234 (2014)","DOI":"10.1007\/978-3-662-43948-7_19"},{"key":"1102_CR13","doi-asserted-by":"crossref","unstructured":"Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Average-case fine-grained hardness. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pp. 483\u2013496 (2017)","DOI":"10.1145\/3055399.3055466"},{"key":"1102_CR14","doi-asserted-by":"crossref","unstructured":"Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Proofs of work from worst-case assumptions. In: Proceedings of the 38th Annual International Cryptology Conference (CRYPTO 2018), Part I, pp. 789\u2013819 (2018)","DOI":"10.1007\/978-3-319-96884-1_26"},{"key":"1102_CR15","unstructured":"Chakrabarti, A., Ghosh, P.: Streaming verification of graph computations via graph structure. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2019), volume 145 of LIPIcs, pp. 70:1\u201370:20 (2019)"},{"key":"1102_CR16","doi-asserted-by":"crossref","unstructured":"Carmosino, M.L., Gao, J., Impagliazzo, R., Mihajlin, I., Paturi, R., Schneider, S.: 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), pp. 261\u2013270 (2016)","DOI":"10.1145\/2840728.2840746"},{"key":"1102_CR17","unstructured":"Chakrabarti, A., Ghosh, P., Thaler, J.: 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, pp. 22:1\u201322:23 (2020)"},{"key":"1102_CR18","doi-asserted-by":"crossref","unstructured":"Cygan, M., Mucha, M., W\u0119grzycki, K., \u0142odarczyk Micha\u0142 W,: On problems equivalent to (min, +)-convolution. ACM Trans. Algorithms 15(1), 14:1\u201314:25 (2019)","DOI":"10.1145\/3293465"},{"key":"1102_CR19","doi-asserted-by":"crossref","unstructured":"Chen, L., Williams, R.: An equivalence class for orthogonal vectors. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pp. 21\u201340. SIAM (2019)","DOI":"10.1137\/1.9781611975482.2"},{"issue":"1","key":"1102_CR20","doi-asserted-by":"publisher","first-page":"2:1","DOI":"10.1145\/3402926","volume":"17","author":"TM Chan","year":"2021","unstructured":"Chan, T.M., Williams, R.R.: Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov\u2013Smolensky. ACM Trans. Algorithms 17(1), 2:1-2:14 (2021)","journal-title":"ACM Trans. Algorithms"},{"key":"1102_CR21","doi-asserted-by":"crossref","unstructured":"Dalirrooyfard, M., Lincoln, A., Williams, V.V.: New techniques for proving fine-grained average-case hardness. In: Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020), pp. 774\u2013785 (2020)","DOI":"10.1109\/FOCS46700.2020.00077"},{"key":"1102_CR22","doi-asserted-by":"crossref","unstructured":"Fiduccia, C.M.: 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), pp. 88\u201393 (1972)","DOI":"10.1145\/800152.804900"},{"issue":"2","key":"1102_CR23","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/3196275","volume":"15","author":"J Gao","year":"2019","unstructured":"Gao, J., Impagliazzo, R., Kolokolova, A., Williams, R.: Completeness for first-order properties on sparse structures with algorithmic applications. ACM Trans. Algorithms 15(2), 23:1-23:35 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"1102_CR24","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/BF01200120","volume":"3","author":"J Goldsmith","year":"1993","unstructured":"Goldsmith, J., Joseph, D.: Relativized isomorphisms of NP-complete sets. Comput. Complex. 3, 186\u2013205 (1993)","journal-title":"Comput. Complex."},{"key":"1102_CR25","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of $$O(n^2)$$ problems in computational geometry. Comput. Geom. 5, 165\u2013185 (1995)","journal-title":"Comput. Geom."},{"issue":"2","key":"1102_CR26","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00037-018-0166-6","volume":"27","author":"M G\u00f6\u00f6s","year":"2018","unstructured":"G\u00f6\u00f6s, M., Pitassi, T., Watson, T.: The landscape of communication complexity classes. Comput. Complex. 27(2), 245\u2013304 (2018)","journal-title":"Comput. Complex."},{"key":"1102_CR27","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Rothblum G.N.: 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), pp. 77\u201388 (2018)","DOI":"10.1109\/FOCS.2018.00017"},{"key":"1102_CR28","unstructured":"Goldreich, O., Rothblum, G.N.: Simple doubly-efficient interactive proof systems for locally-characterizable sets. In: 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume\u00a094 of LIPIcs, pp. 18:1\u201318:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"1102_CR29","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Rothblum, G.N.: Constant-round interactive proof systems for AC0[2] and NC1. In: Computational Complexity and Property Testing - On the Interplay Between Randomness and Computation, volume 12050 of Lecture Notes in Computer Science, pp. 326\u2013351. Springer (2020)","DOI":"10.1007\/978-3-030-43662-9_18"},{"key":"1102_CR30","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Rothblum, G.N.: Worst-case to average-case reductions for subclasses of P. In: Computational Complexity and Property Testing - On the Interplay Between Randomness and Computation, volume 12050 of Lecture Notes in Computer Science, pp. 249\u2013295. Springer (2020)","DOI":"10.1007\/978-3-030-43662-9_15"},{"issue":"4","key":"1102_CR31","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(72)90050-6","volume":"1","author":"E Horowitz","year":"1972","unstructured":"Horowitz, E.: A fast method for interpolation using preconditioning. Inf. Process. Lett. 1(4), 157\u2013163 (1972)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1102_CR32","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM 21(2), 277\u2013292 (1974)","journal-title":"J. ACM"},{"key":"1102_CR33","doi-asserted-by":"crossref","unstructured":"Hirahara, S., Shimizu, N.: Nearly optimal average-case complexity of counting bicliques under SETH. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pp. 2346\u20132365 (2021)","DOI":"10.1137\/1.9781611976465.140"},{"key":"1102_CR34","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Kabanets, V., Kolokolova, A.: An axiomatic approach to algebrization. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009), pp. 695\u2013704 (2009)","DOI":"10.1145\/1536414.1536509"},{"issue":"2","key":"1102_CR35","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1102_CR36","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7(4), 413\u2013423 (1978)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1102_CR37","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/s00453-014-9946-9","volume":"74","author":"Z Jafargholi","year":"2016","unstructured":"Jafargholi, Z., Viola, E.: 3SUM, 3XOR, triangles. Algorithmica 74(1), 326\u2013343 (2016)","journal-title":"Algorithmica"},{"key":"1102_CR38","doi-asserted-by":"crossref","unstructured":"Klauck, H.: Rectangle size bounds and threshold covers in communication complexity. In: Proceedings of the 18th Annual IEEE Conference on Computational Complexity (CCC 2003), pp. 118\u2013134 (2003)","DOI":"10.1109\/CCC.2003.1214415"},{"key":"1102_CR39","doi-asserted-by":"crossref","unstructured":"Klauck, H.: On Arthur Merlin games in communication complexity. In:Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC 2011), pp. 189\u2013199 (2011)","DOI":"10.1109\/CCC.2011.33"},{"issue":"6","key":"1102_CR40","doi-asserted-by":"publisher","first-page":"1767","DOI":"10.1137\/08073408X","volume":"40","author":"KS Kedlaya","year":"2011","unstructured":"Kedlaya, K.S., Umans, C.: Fast polynomial factorization and modular composition. SIAM J. Comput. 40(6), 1767\u20131802 (2011)","journal-title":"SIAM J. Comput."},{"key":"1102_CR41","unstructured":"K\u00fcnnemann, M.: On nondeterministic derandomization of Freivalds\u2019 algorithm: consequences, avenues and algorithmic progress. In: Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018), pp. 56:1\u201356:16 (2018)"},{"key":"1102_CR42","doi-asserted-by":"crossref","unstructured":"Le\u00a0Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pp. 296\u2013303 (2014)","DOI":"10.1145\/2608628.2608664"},{"key":"1102_CR43","doi-asserted-by":"crossref","unstructured":"LaVigne, R., Lincoln, A., Vassilevska Williams, V.: Public-key cryptography in the fine-grained setting. In: Proceedings of the 39th Annual International Cryptology Conference (CRYPTO 2019), Part III, pp. 605\u2013635 (2019)","DOI":"10.1007\/978-3-030-26954-8_20"},{"key":"1102_CR44","doi-asserted-by":"crossref","unstructured":"Lincoln, A., Williams, V.V., Williams, R.L.: 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), pp. 1236\u20131252 (2018)","DOI":"10.1137\/1.9781611975031.80"},{"key":"1102_CR45","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.ipl.2016.09.002","volume":"118","author":"J Nederlof","year":"2017","unstructured":"Nederlof, J.: A short note on Merlin\u2013Arthur protocols for subset sum. Inf. Process. Lett. 118, 15\u201316 (2017)","journal-title":"Inf. Process. Lett."},{"key":"1102_CR46","unstructured":"Nederlof, J.: Personal communication (2021)"},{"issue":"2","key":"1102_CR47","first-page":"415","volume":"26","author":"J Ne\u0161et\u0159il","year":"1985","unstructured":"Ne\u0161et\u0159il, J., Poljak, S.: On the complexity of the subgraph problem. Comment. Math. Univ. Carol. 26(2), 415\u2013419 (1985)","journal-title":"Comment. Math. Univ. Carol."},{"key":"1102_CR48","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), pp. 603\u2013610 (2010)","DOI":"10.1145\/1806689.1806772"},{"key":"1102_CR49","unstructured":"Reingold, O., Rothblum, G.N., Rothblum, R.D.: Efficient batch verification for UP. In: Proceedings of the 33rd Computational Complexity Conference (CCC 2018), pp. 22:1\u201322:23 (2018)"},{"key":"1102_CR50","doi-asserted-by":"crossref","unstructured":"Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. SIAM J. Comput. 50(3), STOC16-255\u2013STOC16-340 (2021)","DOI":"10.1137\/16M1096773"},{"issue":"1","key":"1102_CR51","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/1008883.1008885","volume":"13","author":"U Sch\u00f6ning","year":"1981","unstructured":"Sch\u00f6ning, U.: A note on complete sets for the polynomial-time hierarchy. SIGACT News 13(1), 30\u201334 (1981)","journal-title":"SIGACT News"},{"key":"1102_CR52","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proceedings of the 44th Symposium on Theory of Computing Conference (STOC 2012), pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"},{"key":"1102_CR53","unstructured":"Williams, V.V.: On some fine-grained questions in algorithms and complexity. In: Proceedings of the International Congress of Mathematicians, pp. 3447\u20133487. World Scientific (2018)"},{"issue":"3","key":"1102_CR54","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1137\/09076619X","volume":"42","author":"Virginia Vassilevska Williams and Ryan Williams","year":"2013","unstructured":"Virginia Vassilevska Williams and Ryan Williams: Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42(3), 831\u2013854 (2013)","journal-title":"SIAM J. Comput."},{"key":"1102_CR55","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Williams, R.R. Subcubic equivalences between path, matrix, and triangle problems. J. ACM 65(5), 27 (2018)","DOI":"10.1145\/3186893"},{"key":"1102_CR56","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Wang, J.R., Williams, R., Yu, H.: Finding four-node subgraphs in triangle time. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 1671\u20131680 (2015)","DOI":"10.1137\/1.9781611973730.111"},{"key":"1102_CR57","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Xu, Y.: Monochromatic triangles, triangle listing and APSP. In: Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020), pp. 786\u2013797 (2020)","DOI":"10.1109\/FOCS46700.2020.00078"},{"key":"1102_CR58","unstructured":"Williams, R.: 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), pp. 2:1\u20132:17 (2016)"},{"issue":"5","key":"1102_CR59","doi-asserted-by":"publisher","first-page":"1965","DOI":"10.1137\/15M1024524","volume":"47","author":"RR Williams","year":"2018","unstructured":"Williams, R.R.: Faster all-pairs shortest paths via circuit complexity. SIAM J. Comput. 47(5), 1965\u20131985 (2018)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01102-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01102-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01102-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T14:08:08Z","timestamp":1728914888000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01102-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,17]]},"references-count":59,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["1102"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01102-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,17]]},"assertion":[{"value":"30 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"None","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest statement"}}]}}