{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T12:40:05Z","timestamp":1756816805353,"version":"3.44.0"},"publisher-location":"New York, NY, USA","reference-count":6,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,22]]},"DOI":"10.1145\/3736229.3736259","type":"proceedings-article","created":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T10:07:28Z","timestamp":1756807648000},"page":"93-93","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Best of the Rest: Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7977-4441","authenticated-orcid":false,"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[{"name":"UMR 9189 CRIStAL, Univ. Lille, Inria Lille, CNRS, Centrale Lille, Lille, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-0538-3044","authenticated-orcid":false,"given":"Timothy","family":"van Bremen","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9423-5270","authenticated-orcid":false,"given":"Kuldeep S.","family":"Meel","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,2]]},"reference":[{"key":"e_1_3_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056121"},{"key":"e_1_3_3_1_3_2","series-title":"LIPIcs","first-page":"15:1\u201315:20","volume-title":"ICDT","author":"Amarilli Antoine","year":"2024","unstructured":"Antoine Amarilli, Timothy van Bremen, and Kuldeep\u00a0S. Meel. 2024. Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability. In ICDT(LIPIcs, Vol.\u00a0290). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315:20."},{"key":"e_1_3_3_1_4_2","doi-asserted-by":"crossref","unstructured":"Marcelo Arenas Luis\u00a0Alberto Croquevielle Rajesh Jayaram and Cristian Riveros. 2021. #NFA admits an FPRAS: Efficient enumeration counting and uniform generation for logspace classes. J. ACM 68 6 (2021). https:\/\/doi.org\/10.1145\/3477045 Extended version available as arXiv preprint arXiv:1906.09226 [cs.DS].","DOI":"10.1145\/3477045"},{"key":"e_1_3_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588677"},{"key":"e_1_3_3_1_6_2","volume-title":"VLDB","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In VLDB. IEEE Computer Society."},{"key":"e_1_3_3_1_7_2","doi-asserted-by":"crossref","unstructured":"Rico Zenklusen and Marco Laumanns. 2011. High-confidence estimation of small s-t reliabilities in directed acyclic networks. Networks 57 4 (2011). https:\/\/doi.org\/10.1002\/net.20412","DOI":"10.1002\/net.20412"}],"event":{"name":"PW' 25: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Berlin Germany","acronym":"PW' 25"},"container-title":["Proceedings of the ProvenanceWeek 2025"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3736229.3736259","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T11:58:40Z","timestamp":1756814320000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3736229.3736259"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,22]]},"references-count":6,"alternative-id":["10.1145\/3736229.3736259","10.1145\/3736229"],"URL":"https:\/\/doi.org\/10.1145\/3736229.3736259","relation":{},"subject":[],"published":{"date-parts":[[2025,6,22]]},"assertion":[{"value":"2025-09-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}