pith. sign in

arxiv: 2502.06621 · v4 · submitted 2025-02-10 · 🧮 math.LO · cs.LO

Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction

Michael Pinsker , Jakub Rydval , Moritz Sch\"obi , Christoph Spiess , Paul Winkler This is my paper

Pith reviewed 2026-05-23 03:48 UTC · model grok-4.3

classification 🧮 math.LO cs.LO
keywords constraint satisfaction problemsinfinite domainsBodirsky-Pinsker conjecturepromise constraint satisfactionDatalog reductionsalgebraicityphylogeny CSPsfixed-point logic with counting
0
0 comments X

The pith

The Bodirsky-Pinsker conjecture for infinite-domain CSPs reduces to its algebraicity-free restriction and every non-trivially tractable template witnesses tractability of a finite-domain PCSP via the sandwich method.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper formulates three questions about the scope of the Bodirsky-Pinsker conjecture, an open extension of the finite-domain CSP dichotomy to well-behaved infinite templates, and answers them all positively. Two results simplify the scope: one shows the conjecture is equivalent to its restriction to templates without algebraicity, and the other shows that higher-arity invariants can be taken essentially injective while algebraic conditions for complexity classes are satisfiable by injections. The third result establishes that any non-trivially tractable template in the scope, after a Datalog-computable modification, serves as a witness for the tractability of a non-finitely tractable finite-domain PCSP by the sandwich method. A new case study on phylogeny CSPs illustrates the link by exhibiting a tractable infinite phylogeny CSP that pp-constructs a finite PCSP inexpressible in fixed-point logic with counting.

Core claim

The central results are that the Bodirsky-Pinsker conjecture is equivalent to its restriction to templates without algebraicity, that the higher-arity invariants of any template in the scope can be assumed essentially injective and that algebraic conditions characterizing complexity classes closed under Datalog reductions must be satisfiable by injections, and that any non-trivially tractable template within the scope serves, up to a Datalog-computable modification, as the witness of the tractability of a non-finitely tractable finite-domain PCSP by the sandwich method. The phylogeny case study shows a tractable phylogeny CSP that pp-constructs a finite-domain PCSP inexpressible in fixed-poi

What carries the argument

The sandwich method that uses an infinite template to witness tractability of a finite-domain PCSP, together with Datalog reductions and the equivalence of the conjecture to its non-algebraic restriction.

If this is right

  • The conjecture can now be investigated exclusively on templates without algebraicity.
  • Any algebraic condition used to characterize a complexity class inside the conjecture must admit solutions by injections.
  • Every non-trivially tractable infinite template yields a concrete finite-domain PCSP that is tractable but not finitely tractable.
  • Phylogeny CSPs provide concrete examples linking infinite-domain tractability to finite-domain inexpressibility in fixed-point logic with counting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Classifications obtained for infinite templates without algebraicity would immediately transfer to the full conjecture.
  • The phylogeny examples suggest that infinite templates could separate more finite PCSPs from fixed-point logic with counting than currently known finite templates alone.
  • If the conjecture holds, the sandwich method would give a uniform way to produce tractable finite PCSPs from infinite ones.

Load-bearing premise

The structural simplification that equates the full Bodirsky-Pinsker conjecture to its restriction on templates without algebraicity holds for the well-behaved infinite templates in the scope.

What would settle it

An explicit template inside the Bodirsky-Pinsker scope that is non-trivially tractable yet whose Datalog modification fails to witness tractability of any non-finitely tractable finite-domain PCSP by the sandwich method.

read the original abstract

The Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates, confirmed independently by Bulatov and Zhuk, has an extension to certain well-behaved infinite templates due to Bodirsky and Pinsker which remains wide open. We formulate three fundamental questions on the scope of the Bodirsky-Pinsker conjecture and provide positive answers to them. Our first two main results provide two simplifications of this scope, one of structural, and the other one of algebraic nature. The former simplification implies that the conjecture is equivalent to its restriction to templates without algebraicity, a crucial assumption in the most powerful classification methods. The latter yields that the higher-arity invariants of any template within its scope can be assumed to be essentially injective, and any algebraic condition characterizing any complexity class within the conjecture closed under Datalog reductions must be satisfiable by injections, thus lifting the mystery of the better applicability of certain algebraic conditions over others. Our third main result uses the first one to show that any non-trivially tractable template within the scope serves, up to a Datalog-computable modification of it, as the witness of the tractability of a non-finitely tractable finite-domain Promise Constraint Satisfaction Problem (PCSP) by the so-called sandwich method. This provides a particularly strong connection between the Bodirsky-Pinsker conjecture and finite-domain PCSPs. In the light of the third main result, we initiate a new case study-of phylogeny CSPs-which we investigate from the perspective of descriptive complexity. Within this study, we show that there exists a tractable phylogeny CSP that pp-constructs a finite-domain PCSP inexpressible in fixed-point logic with counting but does not pp-construct any finite-domain CSP with this property.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper formulates three fundamental questions regarding the scope of the Bodirsky-Pinsker conjecture for CSPs over well-behaved infinite templates and answers them positively. The first result establishes a structural simplification showing that the conjecture is equivalent to its restriction to templates without algebraicity. The second provides an algebraic simplification allowing higher-arity invariants to be assumed essentially injective and requiring algebraic conditions for complexity classes (closed under Datalog reductions) to be satisfiable by injections. The third result uses the first to show that any non-trivially tractable template in the scope, up to a Datalog-computable modification, witnesses the tractability of a non-finitely tractable finite-domain PCSP via the sandwich method; a case study on phylogeny CSPs is initiated, exhibiting a tractable phylogeny CSP that pp-constructs a finite-domain PCSP inexpressible in fixed-point logic with counting.

Significance. If the results hold, they would constitute a substantial advance by reducing the conjecture's scope in both structural and algebraic terms (with the former making the no-algebraicity assumption non-restrictive) and by forging a direct link between infinite-domain tractability and finite-domain PCSP tractability via the sandwich method. The phylogeny case study adds a concrete descriptive-complexity application. The paper ships explicit positive answers to open questions in the area, including an equivalence result and a Datalog-based connection.

minor comments (2)
  1. The abstract refers to 'the first main result' for the structural simplification, but the manuscript should include an explicit theorem label (e.g., Theorem 3.1 or similar) in §3 so that the equivalence statement can be cited precisely.
  2. In the phylogeny case study, the claim that the CSP 'does not pp-construct any finite-domain CSP with this property' would benefit from a brief clarification of the precise pp-construction notion used (standard pp vs. the modified Datalog version from the third result).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and supportive report, which recognizes the significance of our three results on the scope of the Bodirsky-Pinsker conjecture. The recommendation of minor revision is noted, but the report raises no specific major comments or concerns requiring response.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper formulates three questions on the Bodirsky-Pinsker conjecture and states three main results as positive answers: structural and algebraic simplifications of the scope, plus a connection via Datalog modification to finite-domain PCSPs. These are presented as theorems derived from prior work in the field (including self-citations that are not load-bearing for the new claims). No equations, definitions, or reductions in the abstract reduce a claimed prediction or result to a fitted parameter or self-referential input by construction. The full derivation chain cannot be inspected for hidden circularity from the given material, but nothing in the stated results matches the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract only; no details on free parameters, axioms, or invented entities are extractable.

pith-pipeline@v0.9.0 · 5866 in / 955 out tokens · 55019 ms · 2026-05-23T03:48:16.552736+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

71 extracted references · 71 canonical work pages

  1. [1]

    Bulatov, and Anuj Dawar

    Albert Atserias, Andrei A. Bulatov, and Anuj Dawar. Affine systems of equations and counting infinitary logic. Theor. Comput. Sci., 410(18):1666–1683, 2009

    work page 2009

  2. [2]

    (2 +𝜀)-Sat Is NP-hard

    Per Austrin, Venkatesan Guruswami, and Johan H˚astad. (2 +𝜀)-Sat Is NP-hard. SIAM J. Comput., 46(5):1554–1573,

    work page

  3. [3]

    A conference version appeared in the proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science - FOCS’14

    work page

  4. [4]

    Using model theory to find decidable and tractable description logics with concrete domains

    Franz Baader and Jakub Rydval. Using model theory to find decidable and tractable description logics with concrete domains. J. Autom. Reason., 66:357–407, 2022

    work page 2022

  5. [5]

    Promises make finite (constraint satisfaction) problems infinitary

    Libor Barto. Promises make finite (constraint satisfaction) problems infinitary. In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science - LICS’19 , pages 1–8. IEEE, 2019

    work page 2019

  6. [6]

    Symmetries of graphs and structures that fail to interpret a finite thing

    Libor Barto, Bertalan Bodor, Marcin Kozik, Antoine Mottet, and Michael Pinsker. Symmetries of graphs and structures that fail to interpret a finite thing. In Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science - LICS’23, pages 1–13. IEEE, 2023

    work page 2023

  7. [7]

    Algebraic approach to promise constraint satisfac- tion

    Libor Barto, Jakub Bul´ın, Andrei Krokhin, and Jakub Oprˇsal. Algebraic approach to promise constraint satisfac- tion. J. ACM., 68(4):28:1–28:66, 2021

    work page 2021

  8. [8]

    Equations in oligo- morphic clones and the constraint satisfaction problem for 𝜔-categorical structures

    Libor Barto, Michael Kompatscher, Miroslav Olˇs´ak, Van Pham Trung, and Michael Pinsker. Equations in oligo- morphic clones and the constraint satisfaction problem for 𝜔-categorical structures. J. Math. Log., 19(02):Article 1950010, 2019

    work page 2019

  9. [9]

    Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem

    Libor Barto and Marcin Kozik. Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Log. Methods Comput. Sci. , 8(1):7:1–7:27, 2012

    work page 2012

  10. [10]

    The wonderland of reflections

    Libor Barto, Jakub Oprˇsal, and Michael Pinsker. The wonderland of reflections. Isr. J. Math., 223(1):363–398, 2018

    work page 2018

  11. [11]

    The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems

    Libor Barto and Michael Pinsker. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science - LICS’16 , pages 615–622. ACM, 2016

    work page 2016

  12. [12]

    Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems)

    Libor Barto and Michael Pinsker. Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems). SIAM J. Comput., 49(2):365–393, 2020

    work page 2020

  13. [13]

    Generalized completion problems with forbidden tournaments

    Zeno Bitter and Antoine Mottet. Generalized completion problems with forbidden tournaments. In Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, MFCS’24 , volume 306 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 28:1–28:17. Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik, 2024

    work page 2024

  14. [14]

    Cores of countably categorical structures

    Manuel Bodirsky. Cores of countably categorical structures. Log. Methods Comput. Sci. , 3(1):2:1–2:16, 2007

    work page 2007

  15. [15]

    New Ramsey classes from old

    Manuel Bodirsky. New Ramsey classes from old. Electron. J. Comb., 21(2):P2.22, 2014

    work page 2014

  16. [16]

    Complexity of infinite-domain constraint satisfaction , volume 52

    Manuel Bodirsky. Complexity of infinite-domain constraint satisfaction , volume 52. Cambridge University Press,

    work page

  17. [17]

    Postprint available online

    work page

  18. [18]

    The reducts of equality up to primitive positive interdefin- ability

    Manuel Bodirsky, Hubie Chen, and Michael Pinsker. The reducts of equality up to primitive positive interdefin- ability. J. Symb. Log., 75(4):1249–1292, 2010. 16

    work page 2010

  19. [19]

    Datalog and constraint satisfaction with infinite templates.J

    Manuel Bodirsky and V´ıctor Dalmau. Datalog and constraint satisfaction with infinite templates.J. Comput. Syst. Sci., 79(1):79–100, 2013. A conference version appeared in the proceedings of the 34th Symposium on Theoretical Aspects of Computer Science - STACS’06

    work page 2013

  20. [20]

    Evans, Michael Kompatscher, and Michael Pinsker

    Manuel Bodirsky, David M. Evans, Michael Kompatscher, and Michael Pinsker. A counterexample to the reconstruction of 𝜔-categorical structures from their endomorphism monoid. Isr. J. Math., 224:57–82, 2018

    work page 2018

  21. [21]

    The complexity of combinations of qualitative constraint satisfaction problems

    Manuel Bodirsky and Johannes Greiner. The complexity of combinations of qualitative constraint satisfaction problems. Log. Methods Comput. Sci. , 16(1):21:1–21:19, 2020

    work page 2020

  22. [22]

    Tractable combinations of theories via sampling

    Manuel Bodirsky and Johannes Greiner. Tractable combinations of theories via sampling. In Proceedings of the 17th European Conference on Logics in Artificial Intelligence - JELIA’23 , pages 133–146. Springer, 2021

    work page 2021

  23. [23]

    Non-dichotomies in constraint satisfaction complexity

    Manuel Bodirsky and Martin Grohe. Non-dichotomies in constraint satisfaction complexity. In Proceedings of the 35th International Colloquium on Automata, Languages, and Programming - ICALP’08 , pages 184–196. Springer, 2008

    work page 2008

  24. [24]

    The complexity of temporal constraint satisfaction problems

    Manuel Bodirsky and Jan K´ara. The complexity of temporal constraint satisfaction problems. J. ACM., 57(2):9:1– 9:41, 2010. A conference version appeared in the proceedings of the 40th ACM Symposium on Theory of Computing - STOC’08

    work page 2010

  25. [25]

    A fast algorithm and datalog inexpressibility for temporal reasoning

    Manuel Bodirsky and Jan K ´ara. A fast algorithm and datalog inexpressibility for temporal reasoning. ACM Trans. Comput. Log., 11(3):15:1–15:21, 2010

    work page 2010

  26. [26]

    Madelaine, and Antoine Mottet

    Manuel Bodirsky, Florent R. Madelaine, and Antoine Mottet. A proof of the algebraic tractability conjecture for monotone monadic SNP. SIAM J. Comput., 50(4):1359–1409, 2021

    work page 2021

  27. [27]

    Constraint satisfaction problems for reducts of homogeneous graphs

    Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and Andr´as Pongr´acz. Constraint satisfaction problems for reducts of homogeneous graphs. SIAM J. Comput., 48(4):1224–1264, 2019. A conference version appeared in the proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP’16

    work page 2019

  28. [28]

    Reducts of finitely bounded homogeneous structures, and lifting tractabil- ity from finite-domain constraint satisfaction

    Manuel Bodirsky and Antoine Mottet. Reducts of finitely bounded homogeneous structures, and lifting tractabil- ity from finite-domain constraint satisfaction. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science - LICS’16, pages 623–632. ACM, 2016

    work page 2016

  29. [29]

    Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)

    Manuel Bodirsky, Antoine Mottet, Miroslav Olˇs´ak, Jakub Oprˇsal, Michael Pinsker, and Ross Willard. Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems). In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science - LICS’19 , pages 1–12. IEEE, 2019

    work page 2019

  30. [30]

    Constraint satisfaction with countable homogeneous templates

    Manuel Bodirsky and Jaroslav Neˇsetˇril. Constraint satisfaction with countable homogeneous templates. J. Log. Comput, 16(3):359–373, 2006. A conference version appeared in the proceedings of Computer Science Logic - CSL’03

    work page 2006

  31. [31]

    Schaefer’s theorem for graphs.Journal of the ACM , 62(3):19:1–19:52,

    Manuel Bodirsky and Michael Pinsker. Schaefer’s theorem for graphs.Journal of the ACM , 62(3):19:1–19:52,

    work page

  32. [32]

    A conference version appeared in the proceedings of the 43rd ACM Symposium on Theory of Computing - STOC’11

    work page

  33. [33]

    Topological Birkhoff

    Manuel Bodirsky and Michael Pinsker. Topological Birkhoff. Trans. Amer. Math. Soc., 367(4):2527–2549, 2015

    work page 2015

  34. [34]

    Canonical functions: a proof via topological dynamics

    Manuel Bodirsky and Michael Pinsker. Canonical functions: a proof via topological dynamics. Contrib. Discrete Math., 16(2):36–45, 2021

    work page 2021

  35. [35]

    Projective clone homomorphisms

    Manuel Bodirsky, Michael Pinsker, and Andr ´as Pongr´acz. Projective clone homomorphisms. J. Symb. Log. , 86(1):148–161, 2021

    work page 2021

  36. [36]

    On the descriptive complexity of temporal constraint satisfaction problems

    Manuel Bodirsky and Jakub Rydval. On the descriptive complexity of temporal constraint satisfaction problems. J. ACM., 70(1):2:1–2:58, 2022

    work page 2022

  37. [37]

    The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems

    Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav ˇZivn´y. The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems. SIAM J. Comput., 49(6):1232–1248, 2020

    work page 2020

  38. [38]

    Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. InProceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science - FOCS’17, pages 319–330. IEEE, 2017

    work page 2017

  39. [39]

    Bulatov, Peter Jeavons, and Andrei A

    Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720–742, 2005

    work page 2005

  40. [40]

    Hierarchies of minion tests for PCSPs through tensors

    Lorenzo Ciardo and Stanislav ˇZivn´y. Hierarchies of minion tests for PCSPs through tensors. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms - SODA’23, pages 568–580. SIAM, 2023

    work page 2023

  41. [41]

    Local consistency as a reduction between constraint satisfaction problems

    Victor Dalmau and Jakub Oprˇsal. Local consistency as a reduction between constraint satisfaction problems. In Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science - LICS’24 , pages 1–15, 2024

    work page 2024

  42. [42]

    Sandwiches for promise constraint satisfaction

    Guofeng Deng, Ezzeddine El Sai, Trevor Manders, Peter Mayr, Poramate Nakkirt, and Athena Sparks. Sandwiches for promise constraint satisfaction. Algebra Univers., 82(1):15:1–15:8, 2021

    work page 2021

  43. [43]

    Irit Dinur, Oded Regev, and Clifford. Smyth. The hardness of 3-uniform hypergraph coloring. InProceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science , pages 33–40. IEEE, 2002. 17

    work page 2002

  44. [44]

    Elliott, J

    L. Elliott, J. Jonuˇsas, J.D. Mitchell, Y. P´eresse, and M. Pinsker. Polish topologies on endomorphism monoids of relational structures. Advances in Mathematics, 431:Article 109214, 2023

    work page 2023

  45. [45]

    Evans and Paul R

    David M. Evans and Paul R. Hewitt. Counterexamples to a conjecture on relative categoricity. Ann. Pure Appl. Log., 46(2):201–209, 1990

    work page 1990

  46. [46]

    Tom´as Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57–104, 1998

    work page 1998

  47. [47]

    An algebraic proof of the graph orientation problem dichotomy for forbidden tournaments

    Roman Feller and Michael Pinsker. An algebraic proof of the graph orientation problem dichotomy for forbidden tournaments. Preprint arXiv:2405.20263, 2024

    work page arXiv 2024

  48. [48]

    Garey and David S

    Michael R. Garey and David S. Johnson. The complexity of near-optimal graph coloring. J. ACM., 23(1):43–49, 1976

    work page 1976

  49. [49]

    Uniform Birkhoff

    Mai Gehrke and Michael Pinsker. Uniform Birkhoff. J. Pure Appl. Algebra, 222(5):1242–1250, 2018

    work page 2018

  50. [50]

    When symmetries are not enough: A hierarchy of hard constraint satisfaction problems

    Pierre Gillibert, Julius Jonusas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker. When symmetries are not enough: A hierarchy of hard constraint satisfaction problems. SIAM J. Comput., 51(2):175–213, 2022

    work page 2022

  51. [51]

    Hrushovski’s encoding and 𝜔-categorical CSP monsters

    Pierre Gillibert, Julius Jonu ˇsas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker. Hrushovski’s encoding and 𝜔-categorical CSP monsters. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming- ICALP’20, volume 168 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 131:1–131:17. Schloss Dags...

    work page 2020

  52. [52]

    All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)

    Jan Hubiˇcka and Jaroslav Ne ˇsetˇril. All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms). Adv. Math., 356:Article 106791, 2019

    work page 2019

  53. [53]

    On the algebraic structure of combinatorial problems

    Peter Jeavons. On the algebraic structure of combinatorial problems. Theor. Comput. Sci., 200(1-2):185–204, 1998

    work page 1998

  54. [54]

    Closure properties of constraints

    Peter Jeavons, David Cohen, and Marc Gyssens. Closure properties of constraints. J. ACM., 44(4):527–548, 1997

    work page 1997

  55. [55]

    Kechris, Vladimir G

    Alexander S. Kechris, Vladimir G. Pestov, and Stevo Todorcevic. Fra¨ıss´e limits, Ramsey theory, and topological dynamics of automorphism groups. Geom. Funct. Anal., 15:106–189, 2005

    work page 2005

  56. [56]

    A complexity dichotomy for poset constraint satisfaction

    Michael Kompatscher and Trung Van Pham. A complexity dichotomy for poset constraint satisfaction. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science - STACS’17 , volume 66 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 47:1–47:12. Schloss Dagstuhl – Leibniz-Zentrum f ¨ur Informatik, 2017

    work page 2017

  57. [57]

    A survey of homogeneous structures

    Dugald Macpherson. A survey of homogeneous structures. Discrete Math., 311(15):1599–1634, 2011

    work page 2011

  58. [58]

    Minimal operations over per mutation groups,

    Paolo Marimon and Michael Pinsker. Binary symmetries of tractable non-rigid structures (Minimal operations over permutation groups). To appear at LICS’25; preprint arXiv:2410.22060, 2024

    work page arXiv 2024

  59. [59]

    Promise and infinite-domain constraint satisfaction

    Antoine Mottet. Promise and infinite-domain constraint satisfaction. In Proceedings of the 32nd EACSL Annual Conference on Computer Science Logic - CSL’24, volume 288 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1–41:19. Schloss Dagstuhl – Leibniz-Zentrum f ¨ur Informatik, 2024

    work page 2024

  60. [60]

    Algebraic and algorithmic synergies between promise and infinite-domain CSPs

    Antoine Mottet. Algebraic and algorithmic synergies between promise and infinite-domain CSPs. Preprint arXiv:2501.13740; to appear at LICS’24, 2025

    work page arXiv 2025

  61. [61]

    An order out of nowhere: A new algorithm for infinite- domain CSPs

    Antoine Mottet, Tom´aˇs Nagy, and Michael Pinsker. An order out of nowhere: A new algorithm for infinite- domain CSPs. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming - ICALP’24, volume 297 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 148:1–148:18. Schloss Dagstuhl – Leibniz-Zentrum f¨ur ...

    work page 2024

  62. [62]

    Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structures

    Antoine Mottet and Michael Pinsker. Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structures. J. ACM., 71(5):36:1–36:47, 2024

    work page 2024

  63. [63]

    Total ordering problem

    Jaroslav Opatrny. Total ordering problem. SIAM J. Comput., 8(1):111–114, 1979

    work page 1979

  64. [64]

    Current challenges in infinite-domain constraint satisfaction: Dilemmas of the infinite sheep

    Michael Pinsker. Current challenges in infinite-domain constraint satisfaction: Dilemmas of the infinite sheep. In Proceedings of the 52nd IEEE International Symposium on Multiple-Valued Logic, ISMVL’22 , pages 80–87. IEEE, 2022

    work page 2022

  65. [65]

    On the Zariski topology on endomorphism monoids of omega- categorical structures

    Michael Pinsker and Clemens Schindler. On the Zariski topology on endomorphism monoids of omega- categorical structures. J. Symb. Log., 2023. To appear

    work page 2023

  66. [66]

    Finitely bounded homogeneity turned inside-out

    Jakub Rydval. Finitely bounded homogeneity turned inside-out. Preprint arXiv:2108.00452v9, 2024

    work page arXiv 2024

  67. [67]

    Ramsey transfer to semi-retractions

    Lynn Scow. Ramsey transfer to semi-retractions. Ann. Pure Appl. Log., 172(3):Article 102891, 2021

    work page 2021

  68. [68]

    Mark H. Siggers. A strong Mal’cev condition for locally finite varieties omitting the unary type.Algebra Univers., 64:15–20, 2010

    work page 2010

  69. [69]

    A proof of CSP dichotomy conjecture

    Dmitriy Zhuk. A proof of CSP dichotomy conjecture. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science - FOCS’17, pages 331–342. IEEE, 2017

    work page 2017

  70. [70]

    A proof of the CSP dichotomy conjecture

    Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM., 67(5):30:1–30:78, 2020

    work page 2020

  71. [71]

    Decidability of definability J

    Manuel Bodirsky and Michael Pinsker and Todor Tsankov. Decidability of definability J. Symb. Log., 78(4):1036– 1054, 2013. 18 Appendix A. Algebraicity is irrelevant (for infinite-domain CSPs) A.1. Omitted definitions. We expand on some of the definitions appearing in the paper that were, for the sake of brevity, not presented in much detail. We also add t...

    work page 2013