{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T13:18:11Z","timestamp":1779110291684,"version":"3.51.4"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T00:00:00Z","timestamp":1779062400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"European Research Council","award":["Project POCOCOP, ERC Synergy Grant 101071674"],"award-info":[{"award-number":["Project POCOCOP, ERC Synergy Grant 101071674"]}]},{"name":"DFG","award":["Project FinHom, Grant 467967530"],"award-info":[{"award-number":["Project FinHom, Grant 467967530"]}]},{"name":"DFG","award":["project LU 1417\/3-1 QTEC."],"award-info":[{"award-number":["project LU 1417\/3-1 QTEC."]}]},{"name":"Austrian Science Fund","award":["10.55776\/ESP6949724"],"award-info":[{"award-number":["10.55776\/ESP6949724"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2026,7,31]]},"abstract":"<jats:p>Valued Constraint Satisfaction Problems (VCSPs) constitute a large class of computational optimization problems. It was recently shown that, over finite domains, every VCSP is in P or NP-complete, depending on the admitted cost functions. In this article, we study cost functions over countably infinite domains whose automorphisms form an oligomorphic permutation group. Our results include a hardness condition based on a generalization of pp-constructability as known from classical CSPs and a polynomial-time tractability condition based on the concept of fractional polymorphisms. We then observe that the resilience problem for Unions of Conjunctive Queries (UCQs) studied in database theory, under bag semantics, may be viewed as a special case of the VCSPs that we consider. We obtain a complexity dichotomy for the case of incidence-acyclic UCQs and exemplarily use our methods to determine the complexity of a conjunctive query that has been stated as an open problem in the literature. We conjecture that our hardness and tractability conditions match for resilience problems for UCQs. Further, we obtain a complete dichotomy for resilience problems for two-way regular path queries, under bag semantics.<\/jats:p>","DOI":"10.1145\/3806207","type":"journal-article","created":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T13:46:12Z","timestamp":1775137572000},"page":"1-59","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Resilience Problems via Valued Constraint Satisfaction"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8228-3611","authenticated-orcid":false,"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Algebra, TU Dresden, Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8111-0671","authenticated-orcid":false,"given":"\u017daneta","family":"Semani\u0161inov\u00e1","sequence":"additional","affiliation":[{"name":"Institute of Discrete Mathematics and Geometry, TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8791-6702","authenticated-orcid":false,"given":"Carsten","family":"Lutz","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Leipzig University, Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Serge Abiteboul Richard Hull and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. Retrieved from http:\/\/webdam.inria.fr\/Alice\/"},{"key":"e_1_3_3_3_2","volume-title":"Infinite Dimensional Analysis: A Hitchhiker\u2019s Guide","author":"Aliprantis Charalambos D.","year":"2006","unstructured":"Charalambos D. Aliprantis and Kim C. Border. 2006. Infinite Dimensional Analysis: A Hitchhiker\u2019s Guide. Springer, Berlin, London."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3725245"},{"issue":"1","key":"e_1_3_3_5_2","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","article-title":"Correlation clustering","volume":"56","author":"Bansal Nikhil","year":"2004","unstructured":"Nikhil Bansal, Avrim Blum, and Shuchi Chawla. 2004. Correlation clustering. Machine Learning 56, 1-3 (2004), 89\u2013113.","journal-title":"Machine Learning"},{"issue":"1","key":"e_1_3_3_6_2","first-page":"1","article-title":"Absorbing subalgebras, cyclic terms and the constraint satisfaction problem","volume":"8","author":"Barto Libor","year":"2012","unstructured":"Libor Barto and Marcin Kozik. 2012. Absorbing subalgebras, cyclic terms and the constraint satisfaction problem. Logical Methods in Computer Science 8\/1, 07 (2012), 1\u201326.","journal-title":"Logical Methods in Computer Science"},{"issue":"1","key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s11856-017-1621-9","article-title":"The wonderland of reflections","volume":"223","author":"Barto Libor","year":"2018","unstructured":"Libor Barto, Jakub Opr\u0161al, and Michael Pinsker. 2018. The wonderland of reflections. Israel Journal of Mathematics 223, 1 (2018), 363\u2013398.","journal-title":"Israel Journal of Mathematics"},{"issue":"4","key":"e_1_3_3_8_2","first-page":"33","article-title":"Ontology-Based data access: A study through disjunctive datalog, CSP, and MMSNP","volume":"39","author":"Bienvenu Meghyn","year":"2014","unstructured":"Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter. 2014. Ontology-Based data access: A study through disjunctive datalog, CSP, and MMSNP. ACM Transactions of Database Systems 39, 4 (2014), 33.","journal-title":"ACM Transactions of Database Systems"},{"issue":"1","key":"e_1_3_3_9_2","first-page":"1","article-title":"Cores of countably categorical structures","volume":"3","author":"Bodirsky Manuel","year":"2007","unstructured":"Manuel Bodirsky. 2007. Cores of countably categorical structures. Logical Methods in Computer Science 3, 1 (2007), 1\u201316.","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781107337534"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3649445"},{"key":"e_1_3_3_12_2","unstructured":"Manuel Bodirsky \u00c9douard Bonnet and \u017daneta Semani\u0161inov\u00e1. 2024. Temporal valued constraint satisfaction problems. arXiv:2409.07285. Retrieved from https:\/\/arxiv.org\/abs\/2409.07285"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9083-9A"},{"key":"e_1_3_3_14_2","first-page":"105","volume-title":"Proceedings of the Symposium on Logic in Computer Science (LICS)","author":"Bodirsky Manuel","year":"2018","unstructured":"Manuel Bodirsky, Florent Madelaine, and Antoine Mottet. 2018. A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP. In Proceedings of the Symposium on Logic in Computer Science (LICS), 105\u2013114."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3488721"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-14(2:13)2018"},{"key":"e_1_3_3_17_2","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/978-3-540-45220-1_5","volume-title":"Proceedings of Computer Science Logic (CSL)","author":"Bodirsky Manuel","year":"2003","unstructured":"Manuel Bodirsky and Jaroslav Ne\u0161et\u0159il. 2003. Constraint satisfaction with countable homogeneous templates. In Proceedings of Computer Science Logic (CSL), 44\u201357."},{"issue":"1","key":"e_1_3_3_18_2","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1017\/jsl.2019.23","article-title":"Projective clone homomorphisms","volume":"86","author":"Bodirsky Manuel","year":"2021","unstructured":"Manuel Bodirsky, Michael Pinsker, and Andr\u00e1s Pongr\u00e1cz. 2021. Projective clone homomorphisms. The Journal of Symbolic Logic 86, 1 (2021), 148\u2013161.","journal-title":"The Journal of Symbolic Logic"},{"key":"e_1_3_3_19_2","first-page":"1","volume-title":"Proceedings of the 39th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS \u201924)","volume":"14","author":"Bodirsky Manuel","year":"2024","unstructured":"Manuel Bodirsky, \u017daneta Semani\u0161inov\u00e1, and Carsten Lutz. 2024. The complexity of resilience problems via valued constraint satisfaction problems. In Proceedings of the 39th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS \u201924). ACM, New York, NY, Article 14, 1\u201314. DOI: 10.1145\/3661814.3662071"},{"key":"e_1_3_3_20_2","volume-title":"Measure Theory, Vol. I, II","author":"Bogachev Vladimir I.","year":"2007","unstructured":"Vladimir I. Bogachev. 2007. Measure Theory, Vol. I, II. Springer-Verlag, Berlin."},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1109\/FOCS.2017.37","volume-title":"58th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201917)","author":"Bulatov Andrei A.","year":"2017","unstructured":"Andrei A. Bulatov. 2017. A dichotomy theorem for nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201917), 319\u2013330."},{"key":"e_1_3_3_22_2","volume-title":"Symmetries in Constraint Satisfaction: Weisfeiler-Leman Invariance and Promise Problems","author":"Butti Silvia","year":"2022","unstructured":"Silvia Butti. 2022. Symmetries in Constraint Satisfaction: Weisfeiler-Leman Invariance and Promise Problems. Ph.\u2009D. Dissertation, Universitat Pompeu Fabra, Barcelona."},{"key":"e_1_3_3_23_2","first-page":"361","volume-title":"15th Annual IEEE Symposium on Logic in Computer Science","author":"Calvanese Diego","year":"2000","unstructured":"Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2000. View-based query processing and constraint satisfaction. In 15th Annual IEEE Symposium on Logic in Computer Science, 361\u2013371."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/959060.959076"},{"key":"e_1_3_3_25_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511549809","volume-title":"Oligomorphic Permutation Groups","author":"Cameron Peter J.","year":"1990","unstructured":"Peter J. Cameron. 1990. Oligomorphic Permutation Groups. Cambridge University Press, Cambridge."},{"key":"e_1_3_3_26_2","first-page":"59","volume-title":"Proceedings of the 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS \u201993)","author":"Chaudhuri Surajit","year":"1993","unstructured":"Surajit Chaudhuri and Moshe Y. Vardi. 1993. Optimization of real conjunctive queries. In Proceedings of the 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS \u201993). ACM, New York, NY, 59\u201370. DOI: 10.1145\/153850.153856"},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1006\/aama.1998.0641","article-title":"Universal graphs with forbidden subgraphs and algebraic closure","volume":"22","author":"Cherlin Gregory","year":"1999","unstructured":"Gregory Cherlin, Saharon Shelah, and Niangdong Shi. 1999. Universal graphs with forbidden subgraphs and algebraic closure. Advances in Applied Mathematics 22 (1999), 454\u2013491.","journal-title":"Advances in Applied Mathematics"},{"issue":"5","key":"e_1_3_3_28_2","doi-asserted-by":"crossref","first-page":"1915","DOI":"10.1137\/130906398","article-title":"An algebraic theory of complexity for discrete optimization","volume":"42","author":"Cohen David A.","year":"2013","unstructured":"David A. Cohen, Martin C. Cooper, P\u00e1id\u00ed Creed, Peter G. Jeavons, and Stanislav \u017divn\u00fd. 2013. An algebraic theory of complexity for discrete optimization. SIAM Journal on Computing 42, 5 (2013), 1915\u20131939.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_3_29_2","first-page":"107","volume-title":"Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming (CP \u201906)","author":"Cohen David A.","year":"2006","unstructured":"David A. Cohen, Martin C. Cooper, and Peter Jeavons. 2006. An algebraic characterisation of complexity for valued constraints. In Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming (CP \u201906), 107\u2013121. DOI: 10.1007\/11889205_10"},{"key":"e_1_3_3_30_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"Cygan Marek","year":"2015","unstructured":"Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms (1st ed.). Springer Publishing Company, Incorporated.","edition":"1"},{"key":"e_1_3_3_31_2","unstructured":"Foniok Jan. 2007. Homomorphisms and Structural Properties of Relational Systems. Doctoral Thesis Charles University Prague Faculty of Mathematics and Physics."},{"key":"e_1_3_3_32_2","doi-asserted-by":"crossref","unstructured":"Cibele Freire Wolfgang Gatterbauer Neil Immerman and Alexandra Meliou. 2015. A characterization of the complexity of resilience and responsibility for self-join-free conjunctive queries. arXiv:1507.00674. Retrieved from http:\/\/arxiv.org\/abs\/1507.00674","DOI":"10.14778\/2850583.2850592"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850592"},{"key":"e_1_3_3_34_2","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1145\/3375395.3387647","volume-title":"Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS \u201920)","author":"Freire Cibele","year":"2020","unstructured":"Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, and Alexandra Meliou. 2020. New results for the complexity of resilience for binary conjunctive queries with self-joins. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS \u201920), 271\u2013284. DOI: 10.1145\/3375395.3387647"},{"issue":"3","key":"e_1_3_3_35_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2898438","article-title":"A Galois connection for weighted (relational) clones of infinite size","volume":"8","author":"Fulla Peter","year":"2016","unstructured":"Peter Fulla and Stanislav \u017divn\u00fd. 2016. A Galois connection for weighted (relational) clones of infinite size. ACM Transactions on Computation Theory 8, 3 (2016), Article 9, 1\u201321.","journal-title":"ACM Transactions on Computation Theory"},{"key":"e_1_3_3_36_2","volume-title":"A Guide to NP-Completeness","author":"Garey Michael","year":"1978","unstructured":"Michael Garey and David Johnson. 1978. A Guide to NP-Completeness. CSLI Press, Stanford."},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.5075\/epfl-thesis-7823"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_3_3_39_2","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"Hell Pavol","year":"2004","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford University Press, Oxford."},{"key":"e_1_3_3_40_2","volume-title":"A Shorter Model Theory","author":"Hodges Wilfrid","year":"1997","unstructured":"Wilfrid Hodges. 1997. A Shorter Model Theory. Cambridge University Press, Cambridge."},{"key":"e_1_3_3_41_2","first-page":"241","volume-title":"Logic Without Borders\u2014Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics","author":"Hubi\u010dka Jan","year":"2015","unstructured":"Jan Hubi\u010dka and Jaroslav Ne\u0161et\u0159il. 2015. Universal structures with forbidden homomorphisms. In Logic Without Borders\u2014Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics. De Gruyter, 241\u2013264."},{"issue":"2","key":"e_1_3_3_42_2","first-page":"229","article-title":"Homomorphism and embedding universal structures for restricted classes","volume":"27","author":"Hubi\u010dka Jan","year":"2016","unstructured":"Jan Hubi\u010dka and Jaroslav Ne\u0161et\u0159il. 2016. Homomorphism and embedding universal structures for restricted classes. Multiple-Valued Logic and Soft Computing 27, 2-3 (2016), 229\u2013253.","journal-title":"Multiple-Valued Logic and Soft Computing"},{"key":"e_1_3_3_43_2","first-page":"149","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA \u201921)","author":"Kim Eun Jung","year":"2021","unstructured":"Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlstr\u00f6m. 2021. Solving hard cut problems via flow-augmentation. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA \u201921), 149\u2013168."},{"key":"e_1_3_3_44_2","first-page":"938","volume-title":"54th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201922)","author":"Kim Eun Jung","year":"2022","unstructured":"Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlstr\u00f6m. 2022. Directed flow-augmentation. In 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201922), 938\u2013947."},{"key":"e_1_3_3_45_2","volume-title":"Probability Theory","author":"Klenke Achim","year":"2020","unstructured":"Achim Klenke. 2020. Probability Theory (3rd ed.). Springer Nature, Cham, Switzerland.","edition":"3"},{"key":"e_1_3_3_46_2","first-page":"1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP \u201919)","volume":"77","author":"Kolmogorov Vladimir","year":"2019","unstructured":"Vladimir Kolmogorov. 2019. Testing the complexity of a valued CSP language. In 46th International Colloquium on Automata, Languages, and Programming (ICALP \u201919). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, Article 77, 1\u201312. DOI: 10.4230\/LIPIcs.ICALP.2019.77"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091836"},{"issue":"1","key":"e_1_3_3_48_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/130945648","article-title":"The power of linear programming for general-valued CSPs","volume":"44","author":"Kolmogorov Vladimir","year":"2015","unstructured":"Vladimir Kolmogorov, Johan Thapper, and Stanislav \u017divn\u00fd. 2015. The power of linear programming for general-valued CSPs. SIAM Journal on Computing 44, 1 (2015), 1\u201336.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_3_49_2","first-page":"846","volume-title":"Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP \u201915), Part I","author":"Kozik Marcin","year":"2015","unstructured":"Marcin Kozik and Joanna Ochremiak. 2015. Algebraic properties of valued constraint satisfaction problem. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP \u201915), Part I, 846\u2013858."},{"key":"e_1_3_3_50_2","unstructured":"Marcin Kozik and Joanna Ochremiak.2015. Algebraic properties of valued constraint satisfaction problem. arXiv:1403.0476v3. Retrieved from https:\/\/arxiv.org\/abs\/1403.0476v3"},{"key":"e_1_3_3_51_2","first-page":"233","volume-title":"The Constraint Satisfaction Problem: Complexity and Approximability","volume":"7","author":"Krokhin Andrei","year":"2017","unstructured":"Andrei Krokhin and Stanislav \u017divn\u00fd. 2017. The Complexity of Valued CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability. Andrei Krokhin and Stanislav Zivny (Eds.). Dagstuhl Follow-Ups, Vol. 7, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 233\u2013266. DOI: 10.4230\/DFU.Vol7.15301.233"},{"issue":"4","key":"e_1_3_3_52_2","first-page":"1","article-title":"A characterisation of first-order constraint satisfaction problems","volume":"3","author":"Larose Benoit","year":"2007","unstructured":"Benoit Larose, Cynthia Loten, and Claude Tardif. 2007. A characterisation of first-order constraint satisfaction problems. Logical Methods in Computer Science 3, 4:6 (2007), 1\u201322.","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3626715"},{"key":"e_1_3_3_54_2","first-page":"1","volume-title":"21st International Conference on Database Theory (ICDT \u201918)","volume":"19","author":"Martens Wim","year":"2018","unstructured":"Wim Martens and Tina Trautner. 2018. Evaluation and enumeration problems for regular path queries. In 21st International Conference on Database Theory (ICDT \u201918). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Article 19, 1\u201321. DOI: 10.4230\/LIPICS.ICDT.2018.19"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"issue":"1","key":"e_1_3_3_56_2","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1017\/jsl.2021.6","article-title":"Cores over Ramsey structures","volume":"86","author":"Mottet Antoine","year":"2021","unstructured":"Antoine Mottet and Michael Pinsker. 2021. Cores over Ramsey structures. The Journal of Symbolic Logic 86, 1 (2021), 352\u2013361.","journal-title":"The Journal of Symbolic Logic"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3689207"},{"key":"e_1_3_3_58_2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1006\/jctb.2000.1970","article-title":"Duality theorems for finite structures","volume":"80","author":"Ne\u0161et\u0159il Jaroslav","year":"2000","unstructured":"Jaroslav Ne\u0161et\u0159il and Claude Tardif. 2000. Duality theorems for finite structures. Journal of Combinatorial Theory, Series B 80 (2000), 80\u201397.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"e_1_3_3_59_2","unstructured":"George Osipov. 2025. Personal communication."},{"key":"e_1_3_3_60_2","unstructured":"Friedrich Martin Schneider and Caterina Viola. 2022. An application of Farkas\u2019 lemma to finite-valued constraint satisfaction problems over infinite domains. arXiv:2208.04912. Retrieved from https:\/\/arxiv.org\/abs\/2208.04912"},{"key":"e_1_3_3_61_2","volume-title":"Graduate Studies in Mathematics","author":"Tao Terence","year":"2011","unstructured":"Terence Tao. 2011. An Introduction to Measure Theory. Graduate Studies in Mathematics, Vol. 126. American Mathematical Society."},{"key":"e_1_3_3_62_2","first-page":"695","volume-title":"Proceedings of the Symposium on Theory of Computing Conference (STOC)","author":"Thapper Johan","year":"2013","unstructured":"Johan Thapper and Stanislav \u017divn\u00fd. 2013. The complexity of finite-valued CSPs. In Proceedings of the Symposium on Theory of Computing Conference (STOC), 695\u2013704."},{"key":"e_1_3_3_63_2","volume-title":"Valued Constraint Satisfaction Problems over Infinite Domains","author":"Viola Caterina","year":"2020","unstructured":"Caterina Viola. 2020. Valued Constraint Satisfaction Problems over Infinite Domains. Ph.\u2009D. Dissertation. TU Dresden."},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3458041"},{"key":"e_1_3_3_65_2","volume-title":"Valued Constraint Satisfaction in Structures with an Oligomorphic Automorphism Group","author":"Semani\u0161inov\u00e1 \u017daneta","year":"2025","unstructured":"\u017daneta Semani\u0161inov\u00e1. 2025. Valued Constraint Satisfaction in Structures with an Oligomorphic Automorphism Group. Dissertation. TU Dresden, Dresden, Germany. Retrieved from https:\/\/nbn-resolving.org\/urn:nbn:de:bsz:14-qucosa2-974737"},{"key":"e_1_3_3_66_2","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1109\/FOCS.2017.38","volume-title":"58th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201917)","author":"Zhuk Dmitriy","year":"2017","unstructured":"Dmitriy Zhuk. 2017. A proof of CSP dichotomy conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201917), 331\u2013342. Retrieved from https:\/\/arxiv.org\/abs\/1704.01914"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3806207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T13:04:21Z","timestamp":1779109461000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3806207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":66,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,7,31]]}},"alternative-id":["10.1145\/3806207"],"URL":"https:\/\/doi.org\/10.1145\/3806207","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]},"assertion":[{"value":"2025-10-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-05-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}