{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T05:12:59Z","timestamp":1768626779099,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451014","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1015-1027","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["When is approximate counting for conjunctive queries tractable?"],"prefix":"10.1145","author":[{"given":"Marcelo","family":"Arenas","sequence":"first","affiliation":[{"name":"PUC, Chile \/ IMFD, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luis Alberto","family":"Croquevielle","sequence":"additional","affiliation":[{"name":"PUC, Chile \/ IMFD, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajesh","family":"Jayaram","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[{"name":"PUC, Chile \/ IMFD, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"The Age of Algorithms","author":"Abiteboul Serge","unstructured":"Serge Abiteboul and Gilles Dowek. 2020. The Age of Algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_2_1","volume-title":"10th International Conference, TACAS 2004, Proceedings. 467\u2013481","author":"Alur Rajeev","unstructured":"Rajeev Alur, Kousha Etessami, and P. Madhusudan. 2004. A Temporal Logic of Nested Calls and Returns. In Tools and Algorithms for the Construction and Analysis of Systems, 10th International Conference, TACAS 2004, Proceedings. 467\u2013481."},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"Alur Rajeev","year":"2004","unstructured":"Rajeev Alur and P. Madhusudan. 2004. Visibly pushdown languages. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004. 202\u2013211."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516518"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90252-O"},{"key":"e_1_3_2_1_6_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming, ICALP 2017","author":"Amarilli Antoine","year":"2017","unstructured":"Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel. 2017. A Circuit-Based Approach to Efficient Enumeration. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland. 111:1\u2013111:15."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319702"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319704"},{"key":"e_1_3_2_1_9_1","volume-title":"Rajesh Jayaram, and Cristian Riveros.","author":"Arenas Marcelo","year":"2020","unstructured":"Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. 2020. When is Approximate Counting for Conjunctive Queries Tractable? arXiv preprint arXiv:2005.10029 (2020). https:\/\/arxiv.org\/abs\/2005.10029"},{"key":"e_1_3_2_1_10_1","unstructured":"Franz Baader Diego Calvanese Deborah L. McGuinness Daniele Nardi and Peter F. Patel-Schneider (Eds.). 2003. The Description Logic Handbook: Theory Implementation and Applications. Cambridge University Press."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46541-3_47"},{"key":"e_1_3_2_1_12_1","volume-title":"Frontiers in Artificial Intelligence and Applications","volume":"185","author":"Biere Armin","year":"2009","unstructured":"Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (Eds.). 2009. Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, Vol. 185. IOS Press."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136043"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3389390"},{"key":"e_1_3_2_1_15_1","first-page":"84","article-title":"Reasoning in expressive description logics with fixpoints based on automata on infinite trees","volume":"99","author":"Calvanese Diego","year":"1999","unstructured":"Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini. 1999. Reasoning in expressive description logics with fixpoints based on automata on infinite trees. In IJCAI, Vol. 99. 84\u201389.","journal-title":"IJCAI"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC'77)","author":"Ashok","unstructured":"Ashok K. Chandra and Philip M. Merlin. 1977. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC'77). 77\u201390."},{"key":"e_1_3_2_1_17_1","volume-title":"Narasayya","author":"Chaudhuri Surajit","year":"1999","unstructured":"Surajit Chaudhuri, Rajeev Motwani, and Vivek R. Narasayya. 1999. On Random Sampling over Joins. In SIGMOD. 263\u2013274."},{"key":"e_1_3_2_1_18_1","volume-title":"Conjunctive Query Containment Revisited. In Database Theory - ICDT '97, 6th International Conference, Delphi, Greece, January 8-10, 1997, Proceedings. 56\u201370","author":"Chekuri Chandra","year":"1997","unstructured":"Chandra Chekuri and Anand Rajaraman. 1997. Conjunctive Query Containment Revisited. In Database Theory - ICDT '97, 6th International Conference, Delphi, Greece, January 8-10, 1997, Proceedings. 56\u201370."},{"key":"e_1_3_2_1_19_1","first-page":"1","article-title":"Random Sampling and Size Estimation Over Cyclic Joins","volume":"7","author":"Chen Yu","year":"2020","unstructured":"Yu Chen and Ke Yi. 2020. Random Sampling and Size Estimation Over Cyclic Joins. In ICDT. 7:1\u20137:18.","journal-title":"ICDT."},{"key":"e_1_3_2_1_20_1","unstructured":"H. Comon M. Dauchet R. Gilleron C. L\u00f6ding F. Jacquemard D. Lugiez S. Tison and M. Tommasi. 2007. Tree Automata Techniques and Applications. Available on: http:\/\/tata.gforge.inria.fr\/. release October 12th 2007."},{"key":"e_1_3_2_1_21_1","volume-title":"The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and computation 85, 1","author":"Courcelle Bruno","year":"1990","unstructured":"Bruno Courcelle. 1990. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and computation 85, 1 (1990), 12\u201375."},{"key":"e_1_3_2_1_22_1","series-title":"SIAM monographs on discrete mathematics and applications","volume-title":"Complexity classifications of Boolean constraint satisfaction problems","author":"Creignou Nadia","unstructured":"Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. 2001. Complexity classifications of Boolean constraint satisfaction problems. SIAM monographs on discrete mathematics and applications, Vol. 7. SIAM."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.008"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502091"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.989"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9543-y"},{"key":"e_1_3_2_1_27_1","volume-title":"Tree automata, mu-calculus and determinacy. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science","author":"Allen Emerson E","unstructured":"E Allen Emerson and Charanjit S Jutla. 1991. Tree automata, mu-calculus and determinacy. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. IEEE, 368\u2013377."},{"key":"e_1_3_2_1_28_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_3_2_1_29_1","volume-title":"Marc Roth, and Stanislav \\vZivn\\`y.","author":"Focke Jacob","year":"2021","unstructured":"Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav \\vZivn\\`y. 2021. Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. arXiv preprint arXiv:2103.12468 (2021)."},{"key":"e_1_3_2_1_30_1","unstructured":"Carla P. Gomes Ashish Sabharwal and Bart Selman. 2009. Model Counting. In Handbook of Satisfiability. 633\u2013654."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2621"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_3_2_1_33_1","volume-title":"The Complexity of Acyclic Conjunctive Queries. In 39th Annual Symposium on Foundations of Computer Science, FOCS'98","author":"Gottlob Georg","year":"1998","unstructured":"Georg Gottlob, Nicola Leone, and Francesco Scarcello. 1998. The Complexity of Acyclic Conjunctive Queries. In 39th Annual Symposium on Foundations of Computer Science, FOCS'98, November 8-11, 1998, Palo Alto, California, USA. 706\u2013715."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00078-3"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings on 33rd Annual ACM Symposium on Theory of Computing","author":"Grohe Martin","year":"2001","unstructured":"Martin Grohe, Thomas Schwentick, and Luc Segoufin. 2001. When is the evaluation of conjunctive queries tractable?. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece (STOC'01). 657\u2013666."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"e_1_3_2_1_39_1","volume-title":"Graphs and homomorphisms. Oxford lecture series in mathematics and its applications","author":"Hell Pavol","unstructured":"Pavol Hell and Jaroslav Nesetril. 2004. Graphs and homomorphisms. Oxford lecture series in mathematics and its applications, Vol. 28. Oxford University Press."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313803"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90038-2"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90033-7"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601869"},{"key":"e_1_3_2_1_46_1","unstructured":"Umut Oztok and Adnan Darwiche. 2014. CV-width: A New Complexity Parameter for CNFs.. In ECAI. 675\u2013680."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.012"},{"key":"e_1_3_2_1_48_1","first-page":"517","article-title":"New Compilation Languages Based on Structured Decomposability","volume":"8","author":"Pipatsrisawat Knot","year":"2008","unstructured":"Knot Pipatsrisawat and Adnan Darwiche. 2008. New Compilation Languages Based on Structured Decomposability. In AAAI, Vol. 8. 517\u2013522.","journal-title":"AAAI"},{"key":"e_1_3_2_1_49_1","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin Michael O","year":"1969","unstructured":"Michael O Rabin. 1969. Decidability of second-order theories and automata on infinite trees. Transactions of the american Mathematical Society 141 (1969), 1\u201335.","journal-title":"Transactions of the american Mathematical Society"},{"key":"e_1_3_2_1_50_1","volume-title":"Database management systems","author":"Ramakrishnan Raghu","unstructured":"Raghu Ramakrishnan, Johannes Gehrke, and Johannes Gehrke. 2003. Database management systems. Vol. 3. McGraw-Hill New York."},{"key":"e_1_3_2_1_51_1","volume-title":"Peter Van Beek, and Toby Walsh","author":"Rossi Francesca","year":"2006","unstructured":"Francesca Rossi, Peter Van Beek, and Toby Walsh. 2006. Handbook of constraint programming. Elsevier."},{"key":"e_1_3_2_1_52_1","volume-title":"Artificial intelligence: a modern approach. Malaysia","author":"Russell Stuart J","unstructured":"Stuart J Russell and Peter Norvig. 2016. Artificial intelligence: a modern approach. Malaysia; Pearson Education Limited,."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.003"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219027"},{"key":"e_1_3_2_1_55_1","first-page":"159","volume-title":"Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99","author":"Ternovskaia Eugenia","year":"1999","unstructured":"Eugenia Ternovskaia. 1999. Automata Theory for Reasoning About Actions. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99, Stockholm, Sweden, July 31 - August 6, 1999. 2 Volumes, 1450 pages. 153\u2013159."},{"key":"e_1_3_2_1_56_1","volume-title":"Wright","author":"Thatcher James W.","year":"1968","unstructured":"James W. Thatcher and Jesse B. Wright. 1968. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical systems theory 2, 1 (1968), 57\u201381."},{"key":"e_1_3_2_1_57_1","volume-title":"Handbook of formal languages","author":"Thomas Wolfgang","unstructured":"Wolfgang Thomas. 1997. Languages, automata, and logic. In Handbook of formal languages. Springer, 389\u2013455."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_3_2_1_60_1","volume-title":"Computer Science Today","author":"Vardi Moshe Y","unstructured":"Moshe Y Vardi. 1995. Alternating automata and program verification. In Computer Science Today. Springer, 471\u2013485."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335209"},{"key":"e_1_3_2_1_62_1","volume-title":"7th International Conference","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. 82\u201394."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"crossref","unstructured":"Zhuoyue Zhao Robert Christensen Feifei Li Xiao Hu and Ke Yi. 2018. Random Sampling over Joins Revisited. In SIGMOD. 1525\u20131539.","DOI":"10.1145\/3183713.3183739"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451014","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451014"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":63,"alternative-id":["10.1145\/3406325.3451014","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451014","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}