{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:16Z","timestamp":1750694776252,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,2,10]],"date-time":"2021-02-10T00:00:00Z","timestamp":1612915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council (ERC) under the European Union\u2019s Seventh Framework Programme","award":["FP7\/2007\u20132013"],"award-info":[{"award-number":["FP7\/2007\u20132013"]}]},{"name":"ERC","award":["334828"],"award-info":[{"award-number":["334828"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            In this article, we introduce a general framework for fine-grained reductions of approximate counting problems to their decision versions. (Thus, we use an oracle that decides whether any witness exists to multiplicatively approximate the number of witnesses with minimal overhead.) This mirrors a foundational result of Sipser (STOC 1983) and Stockmeyer\u00a0(SICOMP 1985) in the polynomial-time setting, and a similar result of M\u00fcller\u00a0(IWPEC 2006) in the FPT setting. Using our framework, we obtain such reductions for some of the most important problems in fine-grained complexity: the Orthogonal Vectors problem, 3SUM, and the Negative-Weight Triangle problem (which is closely related to All-Pairs Shortest Path). While all these problems have simple algorithms over which it is conjectured that no polynomial improvement is possible, our reductions would remain interesting even if these conjectures were proved; they have only polylogarithmic overhead and can therefore be applied to subpolynomial improvements such as the\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            \/ exp(\u0398 (\u221a log\n            <jats:italic>n<\/jats:italic>\n            ))-time algorithm for the Negative-Weight Triangle problem due to Williams\u00a0(STOC\u00a02014). Our framework is also general enough to apply to versions of the problems for which more efficient algorithms are known. For example, the Orthogonal Vectors problem over GF(\n            <jats:italic>m<\/jats:italic>\n            )\n            <jats:italic>d<\/jats:italic>\n            for constant\u00a0\n            <jats:italic>m<\/jats:italic>\n            can be solved in time\n            <jats:italic>n<\/jats:italic>\n            \u00b7 poly (\n            <jats:italic>d<\/jats:italic>\n            ) by a result of Williams and Yu (SODA 2014); our result implies that we can approximately count the number of orthogonal pairs with essentially the same running time.\n          <\/jats:p>\n          <jats:p>\n            We also provide a fine-grained reduction from approximate #SAT to SAT. Suppose the Strong Exponential Time Hypothesis (SETH) is false, so that for some 1 &lt;\n            <jats:italic>c<\/jats:italic>\n            &lt; 2 and all\n            <jats:italic>k<\/jats:italic>\n            there is an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>c<\/jats:italic>\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            )-time algorithm for\n            <jats:italic>k<\/jats:italic>\n            -SAT. Then we prove that for all\n            <jats:italic>k<\/jats:italic>\n            , there is an\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>c<\/jats:italic>\n            +\n            <jats:italic>o<\/jats:italic>\n            (1))\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            )-time algorithm for approximate #\n            <jats:italic>k<\/jats:italic>\n            -SAT. In particular, our result implies that the Exponential Time Hypothesis (ETH) is equivalent to the seemingly weaker statement that there is no algorithm to approximate #3-SAT to within a factor of 1+\u025b in time 2\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n            <\/jats:sup>\n            (\n            <jats:italic>n<\/jats:italic>\n            )\/ \u025b\n            <jats:sup>2<\/jats:sup>\n            (taking \u025b &gt; 0 as part of the input).\n          <\/jats:p>","DOI":"10.1145\/3442352","type":"journal-article","created":{"date-parts":[[2021,2,10]],"date-time":"2021-02-10T18:00:59Z","timestamp":1612980059000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Fine-Grained Reductions from Approximate Counting to Decision"],"prefix":"10.1145","volume":"13","author":[{"given":"Holger","family":"Dell","sequence":"first","affiliation":[{"name":"Goethe University Frankfurt, Germany and IT University of Copenhagen, Denmark and Basic Algorithms Research Copenhagen (BARC), Denmark"}]},{"given":"John","family":"Lapinskas","sequence":"additional","affiliation":[{"name":"University of Bristol, Bristol, UK"}]}],"member":"320","published-online":{"date-parts":[[2021,2,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 26h Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Abboud Amir","year":"2015","unstructured":"Amir Abboud , Richard Ryan Williams , and Huacheng Yu . 2015 . More applications of the polynomial method to algorithm design . In Proceedings of the 26h Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915) , Piotr Indyk (Ed.). SIAM, 218--230. DOI:https:\/\/doi.org\/10.1137\/1.978161 1973730.17 10.1137\/1.9781611973730.17 Amir Abboud, Richard Ryan Williams, and Huacheng Yu. 2015. More applications of the polynomial method to algorithm design. In Proceedings of the 26h Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915), Piotr Indyk (Ed.). SIAM, 218--230. DOI:https:\/\/doi.org\/10.1137\/1.9781611973730.17"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9036-3"},{"key":"e_1_2_1_3_1","volume-title":"9th Innovations in Theoretical Computer Science Conference (ITCS\u201918)","volume":"94","author":"Beame Paul","year":"2018","unstructured":"Paul Beame , Sariel Har-Peled , Sivaramakrishnan Natarajan Ramamoorthy , Cyrus Rashtchian , and Makrand Sinha . 2018 . Edge estimation with independent set oracles . In 9th Innovations in Theoretical Computer Science Conference (ITCS\u201918) (LIPIcs), Anna R. Karlin (Ed.) , Vol. 94 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 38:1--38:21. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2018.38 10.4230\/LIPIcs.ITCS.2018.38 Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. 2018. Edge estimation with independent set oracles. In 9th Innovations in Theoretical Computer Science Conference (ITCS\u201918) (LIPIcs), Anna R. Karlin (Ed.), Vol. 94. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 38:1--38:21. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2018.38"},{"key":"e_1_2_1_4_1","volume-title":"Triangle estimation using polylogarithmic queries. CoRR abs\/1808.00691","author":"Bhattacharya Anup","year":"2018","unstructured":"Anup Bhattacharya , Arijit Bishnu , Arijit Ghosh , and Gopinath Mishra . 2018. Triangle estimation using polylogarithmic queries. CoRR abs\/1808.00691 ( 2018 ). arxiv:1808.00691 http:\/\/arxiv.org\/abs\/1808.00691 Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. 2018. Triangle estimation using polylogarithmic queries. CoRR abs\/1808.00691 (2018). arxiv:1808.00691 http:\/\/arxiv.org\/abs\/1808.00691"},{"key":"e_1_2_1_5_1","volume-title":"Hyperedge estimation using polylogarithmic subset queries. CoRR abs\/1908.04196","author":"Bhattacharya Anup","year":"2019","unstructured":"Anup Bhattacharya , Arijit Bishnu , Arijit Ghosh , and Gopinath Mishra . 2019. Hyperedge estimation using polylogarithmic subset queries. CoRR abs\/1908.04196 ( 2019 ). arxiv:1908.04196 http:\/\/arxiv.org\/abs\/1908.04196 Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. 2019. Hyperedge estimation using polylogarithmic subset queries. CoRR abs\/1908.04196 (2019). arxiv:1908.04196 http:\/\/arxiv.org\/abs\/1908.04196"},{"key":"e_1_2_1_6_1","volume-title":"29th International Symposium on Algorithms and Computation (ISAAC\u201918)","volume":"123","author":"Bishnu Arijit","year":"2018","unstructured":"Arijit Bishnu , Arijit Ghosh , Sudeshna Kolay , Gopinath Mishra , and Saket Saurabh . 2018 . Parameterized query complexity of hitting set using stability of sunflowers . In 29th International Symposium on Algorithms and Computation (ISAAC\u201918) (LIPIcs), Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao (Eds.) , Vol. 123 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 25:1--25:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.25 10.4230\/LIPIcs.ISAAC.2018.25 Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, and Saket Saurabh. 2018. Parameterized query complexity of hitting set using stability of sunflowers. In 29th International Symposium on Algorithms and Computation (ISAAC\u201918) (LIPIcs), Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao (Eds.), Vol. 123. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 25:1--25:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.25"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.015"},{"volume-title":"Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC\u201915)","author":"Timothy","key":"e_1_2_1_8_1","unstructured":"Timothy M. Chan and Moshe Lewenstein. 2015. Clustered integer 3SUM via additive combinatorics . In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC\u201915) , Rocco A. Servedio and Ronitt Rubinfeld (Eds.). ACM, 31--40. DOI:https:\/\/doi.org\/10.1145\/2746539.2746568 10.1145\/2746539.2746568 Timothy M. Chan and Moshe Lewenstein. 2015. Clustered integer 3SUM via additive combinatorics. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC\u201915), Rocco A. Servedio and Ronitt Rubinfeld (Eds.). ACM, 31--40. DOI:https:\/\/doi.org\/10.1145\/2746539.2746568"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch87"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Chen Xi","year":"2020","unstructured":"Xi Chen , Amit Levi , and Erik Waingarten . 2020 . Nearly optimal edge estimation with independent set queries . In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920) , Shuchi Chawla (Ed.). SIAM, 2916--2935. DOI:https:\/\/doi.org\/10.1137\/1.978161 1975994.177 10.1137\/1.9781611975994.177 Xi Chen, Amit Levi, and Erik Waingarten. 2020. Nearly optimal edge estimation with independent set queries. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920), Shuchi Chawla (Ed.). SIAM, 2916--2935. DOI:https:\/\/doi.org\/10.1137\/1.9781611975994.177"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Dell Holger","year":"2020","unstructured":"Holger Dell , John Lapinskas , and Kitty Meeks . 2020 . Approximately counting and sampling small witnesses using a colourful decision oracle . In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920) , Shuchi Chawla (Ed.). SIAM, 2201--2211. DOI:https:\/\/doi.org\/10.1137\/1.978161 1975994.135 10.1137\/1.9781611975994.135 Holger Dell, John Lapinskas, and Kitty Meeks. 2020. Approximately counting and sampling small witnesses using a colourful decision oracle. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920), Shuchi Chawla (Ed.). SIAM, 2201--2211. DOI:https:\/\/doi.org\/10.1137\/1.9781611975994.135"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Gao Jiawei","year":"2017","unstructured":"Jiawei Gao , Russell Impagliazzo , Antonina Kolokolova , and Richard Ryan Williams . 2017 . Completeness for first-order properties on sparse structures with algorithmic applications . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917) , Philip N. Klein (Ed.). SIAM, 2162--2181. DOI:https:\/\/doi.org\/10.1137\/1.978161 1974782.141 10.1137\/1.9781611974782.141 Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Richard Ryan Williams. 2017. Completeness for first-order properties on sparse structures with algorithmic applications. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917), Philip N. Klein (Ed.). SIAM, 2162--2181. DOI:https:\/\/doi.org\/10.1137\/1.9781611974782.141"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/120868177"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"Impagliazzo Russell","year":"2012","unstructured":"Russell Impagliazzo , William Matthews , and Ramamohan Paturi . 2012 . A satisfiability algorithm for AC0 . In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912) , Yuval Rabani (Ed.). SIAM, 961--972. DOI:https:\/\/doi.org\/10.1137\/1.978161 1973099.77 10.1137\/1.9781611973099.77 Russell Impagliazzo, William Matthews, and Ramamohan Paturi. 2012. A satisfiability algorithm for AC0. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912), Yuval Rabani (Ed.). SIAM, 961--972. DOI:https:\/\/doi.org\/10.1137\/1.9781611973099.77"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.06.017"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_5"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910)","author":"Patrascu Mihai","year":"2010","unstructured":"Mihai Patrascu . 2010 . Towards polynomial lower bounds for dynamic problems . In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910) , Leonard J. Schulman (Ed.). ACM, 603--610. DOI:https:\/\/doi.org\/10.1145\/ 1806689.1806772 10.1145\/1806689.1806772 Mihai Patrascu. 2010. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910), Leonard J. Schulman (Ed.). ACM, 603--610. DOI:https:\/\/doi.org\/10.1145\/1806689.1806772"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066101"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.02.013"},{"key":"e_1_2_1_26_1","volume-title":"Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference, J. Siemons (Ed.). London Mathematical Society Lecture Note Series","author":"McDiarmid C.","year":"1989","unstructured":"C. McDiarmid . 1989 . On the method of bounded differences . In Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference, J. Siemons (Ed.). London Mathematical Society Lecture Note Series . Cambridge University Press, 148--188. DOI:10.1017\/CBO9781107359949.008 10.1017\/CBO9781107359949.008 C. McDiarmid. 1989. On the method of bounded differences. In Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference, J. Siemons (Ed.). London Mathematical Society Lecture Note Series. Cambridge University Press, 148--188. DOI:10.1017\/CBO9781107359949.008"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808762"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214060"},{"key":"e_1_2_1_29_1","volume-title":"29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","volume":"14","author":"Thurley Marc","year":"2012","unstructured":"Marc Thurley . 2012 . An approximation algorithm for #k-SAT . In 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912) (LIPIcs), Christoph D\u00fcrr and Thomas Wilke (Eds.) , Vol. 14 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 78--87. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2012.78 10.4230\/LIPIcs.STACS.2012.78 Marc Thurley. 2012. An approximation algorithm for #k-SAT. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912) (LIPIcs), Christoph D\u00fcrr and Thomas Wilke (Eds.), Vol. 14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 78--87. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2012.78"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0134-y"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90135-0"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2015.17"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591811"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.SOSA.2018.6"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634209"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442352","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:21Z","timestamp":1750195461000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,10]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3442352"],"URL":"https:\/\/doi.org\/10.1145\/3442352","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2021,2,10]]},"assertion":[{"value":"2019-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}