{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:21Z","timestamp":1750220781839,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,5,13]],"date-time":"2020-05-13T00:00:00Z","timestamp":1589328000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSERC Discovery"},{"name":"Royal Society University Research Fellowship"},{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["714532"],"award-info":[{"award-number":["714532"]}]},{"name":"European Research Council"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>\n            In this article, we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP(\n            <jats:italic>C<\/jats:italic>\n            , -), in which the goal is, given a relational structure\n            <jats:bold>A<\/jats:bold>\n            from a class\n            <jats:italic>C<\/jats:italic>\n            of structures and an arbitrary structure\n            <jats:bold>B<\/jats:bold>\n            , to find the number of homomorphisms from\n            <jats:bold>A<\/jats:bold>\n            to\n            <jats:bold>B<\/jats:bold>\n            . Flum and Grohe showed that #CSP(\n            <jats:italic>C<\/jats:italic>\n            , -) is solvable in polynomial time if\n            <jats:italic>C<\/jats:italic>\n            has bounded treewidth [FOCS\u201902]. Building on the work of Grohe\u00a0[JACM\u201907] on decision CSPs, Dalmau and Jonsson then showed that if\n            <jats:italic>C<\/jats:italic>\n            is a recursively enumerable class of relational structures of bounded arity, then, assuming FPT\u2260 #W[1], there are no other cases of #CSP(\n            <jats:italic>C<\/jats:italic>\n            , -) solvable exactly in polynomial time (or even fixed-parameter time)\u00a0[TCS\u201904].\n          <\/jats:p>\n          <jats:p>\n            We show that, assuming FPT \u2260 W[1] (under randomised parameterised reductions) and for\n            <jats:italic>C<\/jats:italic>\n            satisfying certain general conditions, #CSP(\n            <jats:italic>C<\/jats:italic>\n            ,-) is not solvable even\n            <jats:italic>approximately<\/jats:italic>\n            for\n            <jats:italic>C<\/jats:italic>\n            of unbounded treewidth; that is, there is no fixed parameter tractable (and thus also not fully polynomial) randomised approximation scheme for #CSP(\n            <jats:italic>C<\/jats:italic>\n            , -). In particular, our condition generalises the case when\n            <jats:italic>C<\/jats:italic>\n            is closed undertaking minors.\n          <\/jats:p>","DOI":"10.1145\/3389390","type":"journal-article","created":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T10:23:19Z","timestamp":1589883799000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Approximate Counting CSP Seen from the Other Side"],"prefix":"10.1145","volume":"12","author":[{"given":"Andrei A.","family":"Bulatov","sequence":"first","affiliation":[{"name":"School of Computing Science, Simon Fraser University, Burnaby BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":false,"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,5,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36136-7_40"},{"volume-title":"Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915)","year":"2015","author":"Brault-Baron Johann","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528400"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201919)","volume":"138","author":"Andrei","year":"2019"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2822891"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.06.006"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0016"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.008"},{"volume-title":"Vardi","year":"2002","author":"Dalmau V\u00edctor","key":"e_1_2_1_11_1"},{"edition":"4","volume-title":"Graph Theory","author":"Diestel Reinhard","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00317-9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.08.003"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811258"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","year":"2005","author":"Feder Tom\u00e1s","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.37236\/976"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652181"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427203"},{"volume-title":"Parametrized Complexity Theory","author":"Flum J\u00f6rg","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1020551"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037381"},{"volume-title":"Johnson","year":"1979","author":"Garey Michael R.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"volume-title":"Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC\u201901)","year":"2001","author":"Grohe Martin","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.06.019"},{"edition":"2","volume-title":"Probability and Computing","author":"Mitzenmacher Michael","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.012"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3389390","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3389390","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:31Z","timestamp":1750200091000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3389390"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,13]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3389390"],"URL":"https:\/\/doi.org\/10.1145\/3389390","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2020,5,13]]},"assertion":[{"value":"2019-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}