pith. sign in

arxiv: 2509.04347 · v4 · submitted 2025-09-04 · 💻 cs.LO · math.LO· math.RA

When Darwin met Ianus: dichotomies of expressivity

Johanna Brunar , Michael Pinsker , Moritz Sch\"obi This is my paper

Pith reviewed 2026-05-18 18:57 UTC · model grok-4.3

classification 💻 cs.LO math.LOmath.RA
keywords constraint satisfactioninfinite-domain CSPpolymorphismstemporal languagesphylogeny constraint languagespp-interpretationsexpressivitydichotomy theorems
0
0 comments X

The pith

Temporal and phylogeny constraint languages that avoid constructing everything admit 4-ary pseudo-Siggers polymorphisms.

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

The paper shows that the tractable cases among temporal and phylogeny constraint languages—identified by existing dichotomies as those that do not pp-construct everything—have sharply restricted expressive power when measured by the graphs and hypergraphs they can pp-interpret. This restriction produces several new algebraic facts and supplies uniform proofs for earlier invariance results. The proofs for the two families proceed along parallel lines and expose a shared core, even though the families had appeared to rest on different algorithmic ideas. If the claim holds, it keeps open the prospect that 4-ary pseudo-Siggers polymorphisms appear across a wider range of infinite-domain CSPs.

Core claim

Temporal and phylogeny constraint languages that do not pp-construct everything possess very limited expressive power via pp-interpretations and therefore admit 4-ary pseudo-Siggers polymorphisms; the same limitation yields uniform proofs for known invariance properties and reveals a common core between the two families.

What carries the argument

Limitation on the graphs and hypergraphs that can be pp-interpreted, which forces the existence of 4-ary pseudo-Siggers polymorphisms.

If this is right

  • New algebraic consequences follow for all such tractable languages.
  • Uniform proofs become available for previously known invariance properties.
  • The result keeps alive the possibility that 4-ary pseudo-Siggers polymorphisms exist for every tractable case covered by the Bodirsky-Pinsker conjecture.

Where Pith is reading between the lines

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

  • Similar limited-expressivity arguments might apply to other infinite-domain CSP classes whose dichotomies rest on pp-construction.
  • The shared proof structure could guide the search for polymorphisms in additional temporal or evolutionary constraint families.
  • If the polymorphisms turn out to be algorithmically useful, they might yield new uniform solvers for both temporal and phylogeny problems.

Load-bearing premise

The known dichotomy theorems correctly mark exactly the languages that do not pp-construct everything as the tractable ones.

What would settle it

A temporal or phylogeny constraint language shown to be solvable in polynomial time yet lacking any 4-ary pseudo-Siggers polymorphism.

Figures

Figures reproduced from arXiv: 2509.04347 by Johanna Brunar, Michael Pinsker, Moritz Sch\"obi.

Figure 1
Figure 1. Figure 1: Polymorphisms of temporal constraint languages Aut(Q) pp dual(pp) lex min mi mx max dual(mx) dual(mi) ℓℓ dual(ℓℓ) generate the same clone, and the same holds for mx. Note that our definition of mi differs slightly from the original one in [BK10]. Operations mi defined either way generate the same clone, and in particular each other. Our definition of mi is in line with [BR22]. Definition 2.2. For q ∈ Q, le… view at source ↗
read the original abstract

The classifications of temporal and phylogeny constraint languages stand among the most seminal complexity classifications within infinite-domain Constraint Satisfaction Problems (CSPs), yet remain the most mysterious in terms of algorithms and algebraic invariants for the tractable cases. We show that those languages which do not pp-construct EVERYTHING (and thus by the classifications are solvable in polynomial time) have, in fact, very limited expressive power as measured by the graphs and hypergraphs they can pp-interpret. This limitation yields many previously unknown algebraic consequences, while also providing new, uniform proofs for known invariance properties. In particular, we show that such temporal and phylogeny constraint languages admit $4$-ary pseudo-Siggers polymorphisms -- a result that sustains the possibility that the existence of such polymorphisms extends to the much broader context of the Bodirsky-Pinsker conjecture. Although temporal and phylogeny constraint languages appear to follow fundamentally different algorithmic principles, our proofs reveal a common core and proceed along strikingly similar lines.

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 investigates the expressive power of temporal and phylogeny constraint languages within infinite-domain CSPs. Leveraging established dichotomy classifications, it shows that languages which do not pp-construct everything possess limited expressive power, measured by the graphs and hypergraphs they can pp-interpret. This limitation yields new algebraic consequences, including the existence of 4-ary pseudo-Siggers polymorphisms for both classes, along with uniform proofs for known invariance properties. The work highlights a common core in the proofs despite differing algorithmic principles and sustains the possibility that such polymorphisms extend to the Bodirsky-Pinsker conjecture.

Significance. If the central results hold, this manuscript is significant for identifying a shared algebraic invariant (4-ary pseudo-Siggers polymorphisms) across two major classes of tractable infinite-domain CSPs. It supplies uniform structural arguments based on restricted pp-interpretability, offers new consequences from the classifications, and provides independent support for invariance properties. The approach strengthens connections between expressivity limitations and polymorphism existence without relying on circular reasoning.

minor comments (2)
  1. [§2] §2 (Preliminaries): the notation for pp-interpretations of hypergraphs could be introduced with an explicit example to aid readers unfamiliar with the temporal vs. phylogeny distinction.
  2. [Main theorem section] The statement of the main theorem (likely in §4 or §5) would benefit from a brief reminder of how the 4-ary pseudo-Siggers condition is verified from the limited interpretability, even if the full derivation is in an appendix.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and insightful report, which accurately summarizes our results on the limited expressive power of tractable temporal and phylogeny constraint languages and the resulting algebraic consequences, including the existence of 4-ary pseudo-Siggers polymorphisms. We appreciate the recognition of the common core in the proofs and the support this provides for broader conjectures such as Bodirsky-Pinsker. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation builds on external classifications

full rationale

The paper identifies tractable temporal and phylogeny constraint languages via their established dichotomy classifications (which are treated as given external results), then derives the existence of 4-ary pseudo-Siggers polymorphisms from limited pp-interpretability of graphs and hypergraphs using uniform structural arguments. No step reduces by construction to a self-defined input, fitted parameter renamed as prediction, or load-bearing self-citation chain; the algebraic consequences and new proofs for invariance properties are obtained independently from the classifications themselves. The central claim therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on prior dichotomy classifications for temporal and phylogeny languages as the foundation for defining the tractable cases under study; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption The established dichotomy classifications correctly characterize tractable temporal and phylogeny constraint languages as those that do not pp-construct everything.
    Directly invoked in the abstract to delimit the languages for which the new expressivity and polymorphism results are claimed.

pith-pipeline@v0.9.0 · 5697 in / 1182 out tokens · 50302 ms · 2026-05-18T18:57:47.192925+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Equivalences of promise compactness principles

    math.CO 2026-04 unverdicted novelty 8.0

    For structure pairs (A,B) without Olšák polymorphisms, the promise compactness K_(A,B) is equivalent to the ultrafilter principle over ZF, including K_(K3,K5) and K_(H2,Hc).

Reference graph

Works this paper leans on

62 extracted references · 62 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    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

  2. [2]

    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

  3. [3]

    Forbidden tournaments and the orientation completion problem

    Manuel Bodirsky and Santiago Guzm\' a n-Pro. Forbidden tournaments and the orientation completion problem. SIAM J. Discrete Math. , 39(1):170--205, 2025

    work page 2025

  4. [4]

    Point algebras for temporal reasoning: Algorithms and complexity

    Mathias Broxvall and Peter Jonsson. Point algebras for temporal reasoning: Algorithms and complexity. Artif. Intell. , 149(2):179--220, 2003

    work page 2003

  5. [5]

    Bulatov, Peter Jeavons, and Andrei A

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

    work page 2005

  6. [6]

    Complexity classification transfer for CSP s via algebraic products

    Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet, and Z aneta Semani s inov \'a . Complexity classification transfer for CSP s via algebraic products. SIAM J. Comput. , 53(5):1293--1353, 2024

    work page 2024

  7. [7]

    The Complexity of Phylogeny Constraint Satisfaction

    Manuel Bodirsky, Peter Jonsson, and Trung Van Pham. The Complexity of Phylogeny Constraint Satisfaction . In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) , volume 47 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 20:1--20:13, 2016

    work page 2016

  8. [8]

    The Complexity of Phylogeny Constraint Satisfaction Problems

    Manuel Bodirsky, Peter Jonsson, and Trung Van Pham. The Complexity of Phylogeny Constraint Satisfaction Problems . ACM Transactions on Computational Logic (TOCL) , 18(3), 2017. An extended abstract appeared in the conference STACS 2016

    work page 2017

  9. [9]

    The complexity of equality constraint languages

    Manuel Bodirsky and Jan K \'a ra. The complexity of equality constraint languages. Theory Comput. Syst. , 43:136--158, 2008. A conference version appeared in the proceedings of Computer Science Russia - CSR '06

    work page 2008

  10. [10]

    The complexity of temporal constraint satisfaction problems

    Manuel Bodirsky and Jan K\'ara. The complexity of temporal constraint satisfaction problems. In Proceedings of the 40th annual ACM symposium on Theory of computing - STOC '08 , pages 29--38. ACM, 2008

    work page 2008

  11. [11]

    Constraint satisfaction problems of bounded width

    Libor Barto and Marcin Kozik. Constraint satisfaction problems of bounded width. In Proceedings of the 50th IEEE Annual Symposium on Foundations of Computer Science - FOCS '09 , pages 595--603. IEEE, 2009

    work page 2009

  12. [12]

    The complexity of temporal constraint satisfaction problems

    Manuel Bodirsky and Jan K\'ara. The complexity of temporal constraint satisfaction problems. J. ACM. , 57(2):1--41, 2010

    work page 2010

  13. [13]

    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

  14. [14]

    Constraint satisfaction problems solvable by local consistency methods

    Libor Barto and Marcin Kozik. Constraint satisfaction problems solvable by local consistency methods. J. ACM. , 61(1):3:1--3:19, 2014

    work page 2014

  15. [15]

    The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of B ang- J ensen and H ell)

    Libor Barto, Marcin Kozik, and Todd Niven. The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of B ang- J ensen and H ell). SIAM J. Comput. , 38(5):1782--1802, 2009

    work page 2009

  16. [16]

    The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems

    Johanna Brunar, Marcin Kozik, Tom \' a s Nagy, and Michael Pinsker. The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems. In Proceedings of the 40th Annual ACM/IEEE Symposium on Logic in Computer Science - LICS '25 , pages 1--13. IEEE , 2025. to appear, preprint available at: https://arxiv.org/abs/2501.17060

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  17. [17]

    The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems

    Libor Barto, Michael Kompatscher, Miroslav Ol s \' a k, Trung Van Pham, and Michael Pinsker. The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems. In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science - LICS '16 , pages 1--12. IEEE, 2017

    work page 2017

  18. [18]

    Equations in oligomorphic clones and the constraint satisfaction problem for -categorical structures

    Libor Barto, Michael Kompatscher, Miroslav Ol s \'a k, Van Pham Trung, and Michael Pinsker. Equations in oligomorphic clones and the constraint satisfaction problem for -categorical structures. J. Math. Log. , 19(02):Article 1950010, 2019

    work page 2019

  19. [19]

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

    Manuel Bodirsky and Antoine Mottet. Reducts of finitely bounded homogeneous structures, and lifting tractability 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

  20. [20]

    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 \"u r Informatik, 2024

    work page 2024

  21. [21]

    A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP

    Manuel Bodirsky, Florent Madelaine, and Antoine Mottet. A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP . In Proceedings of the 33st Annual ACM/IEEE Symposium on Logic in Computer Science - LICS '18 , pages 105--114. ACM, 2018

    work page 2018

  22. [22]

    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

  23. [23]

    Constraint satisfaction problems for reducts of homogeneous graphs

    Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and Andr \' a s Pongr \' a cz. 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

  24. [24]

    Constraint satisfaction with countable homogeneous templates

    Manuel Bodirsky and Jaroslav Ne s et r il. 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

  25. [25]

    Complexity of infinite-domain constraint satisfaction , volume 52

    Manuel Bodirsky. Complexity of infinite-domain constraint satisfaction , volume 52. Cambridge University Press, 2021. Postprint available online https://wwwpub.zih.tu-dresden.de/ bodirsky/Book.pdf

    work page 2021

  26. [26]

    The wonderland of reflections

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

    work page 2018

  27. [27]

    Schaefer's theorem for graphs

    Manuel Bodirsky and Michael Pinsker. Schaefer's theorem for graphs. J. ACM. , 62(3):19:1--19:52, 2015. A conference version appeared in the proceedings of the 43rd ACM Symposium on Theory of Computing - STOC '11

    work page 2015

  28. [28]

    Topological B irkhoff

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

    work page 2015

  29. [29]

    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

  30. [30]

    T opology I s I rrelevant ( I n a D ichotomy C onjecture for I nfinite D omain C onstraint S atisfaction P roblems)

    Libor Barto and Michael Pinsker. T opology I s I rrelevant ( I n a D ichotomy C onjecture for I nfinite D omain C onstraint S atisfaction P roblems). SIAM J. Comput. , 49(2):365--393, 2020

    work page 2020

  31. [31]

    Projective clone homomorphisms

    Manuel Bodirsky, Michael Pinsker, and Andr \'a s Pongr \'a cz. Projective clone homomorphisms. J. Symb. Log. , 86(1):148--161, 2021

    work page 2021

  32. [32]

    Decidability of definability

    Manuel Bodirsky, Michael Pinsker, and Todor Tsankov. Decidability of definability. J. Symb. Log. , 78(4):1036--1054, 2013. A conference version appeared in the proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science - LICS '11

    work page 2013

  33. [33]

    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. A conference version under the title ``Temporal Constraint Satisfaction Problems in Fixed-Point Logic'' appeared in the proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science - LICS '20

    work page 2022

  34. [34]

    Identities in finite taylor algebras

    Johanna Brunar. Identities in finite taylor algebras. Diploma thesis, 2023

    work page 2023

  35. [35]

    Andrei A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM. , 53(1):66--120, 2006

    work page 2006

  36. [36]

    Andrei A. Bulatov. A dichotomy theorem for nonuniform CSP s. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science - FOCS '17 , pages 319--330. IEEE, 2017

    work page 2017

  37. [37]

    Computational complexity of temporal constraint problems

    Thomas Drakengren and Peter Jonsson. Computational complexity of temporal constraint problems. In Handbook of Temporal Reasoning in Artificial Intelligence , volume 1 of Foundations of Artificial Intelligence , pages 197--218. Elsevier, 2005

    work page 2005

  38. [38]

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

    Roman Feller and Michael Pinsker. An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments. SIAM J. Discrete Math. , 2025. to appear, preprint available at: https://arxiv.org/abs/2405.20263

    work page arXiv 2025

  39. [39]

    Tom\'as Feder and Moshe Y. Vardi. Monotone monadic SNP and constraint satisfaction. In Proceedings of the 25th annual ACM symposium on Theory of Computing - STOC '93 , pages 612--622. ACM, 1993

    work page 1993

  40. [40]

    Tom \' a s 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

  41. [41]

    Hrushovski's encoding and -categorical CSP monsters

    Pierre Gillibert, Julius Jonu s as, 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 Da...

    work page 2020

  42. [42]

    Pseudo-loop conditions

    Pierre Gillibert, Julius Jonu s as, and Michael Pinsker. Pseudo-loop conditions. Bull. Lond. Math. Soc. , 51(5):917--936, 2019

    work page 2019

  43. [43]

    On the complexity of H -coloring

    Pavol Hell and Jaroslav Ne s et r il. On the complexity of H -coloring. Journal of Combinatorial Theory, Series B , 48:92--110, 1990

    work page 1990

  44. [44]

    A complete classification of tractability in RCC -5

    Peter Jonsson and Thomas Drakengren. A complete classification of tractability in RCC -5. J. Artif. Intell. Res. , 6:211--221, 1997

    work page 1997

  45. [45]

    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

  46. [46]

    Krokhin, Peter Jeavons, and Peter Jonsson

    Andrei A. Krokhin, Peter Jeavons, and Peter Jonsson. Reasoning about temporal relations: The tractable subalgebras of A llen's interval algebra. J. ACM. , 50(5):591--640, 2003

    work page 2003

  47. [47]

    Kearnes, Petar Markovi\'c, and Ralph McKenzie

    Keith A. Kearnes, Petar Markovi\'c, and Ralph McKenzie. Optimal strong M al'cev conditions for omitting type 1 in locally finite varieties. Algebra Univers. , 72(1):91--100, 2015

    work page 2015

  48. [48]

    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 \"u r Informatik, 2017

    work page 2017

  49. [49]

    A complexity dichotomy for poset constraint satisfaction

    Michael Kompatscher and Trung Van Pham. A complexity dichotomy for poset constraint satisfaction. IfCoLoG J. Log. their Appl. , 5(8):1663--1696, 2018

    work page 2018

  50. [50]

    The csp dichotomy, the axiom of choice, and cyclic polymorphisms

    Tam \'a s K \'a tay, L \'a szl \'o M \'a rton T \'o th, and Zolt \'a n Vidny \'a nszky. The csp dichotomy, the axiom of choice, and cyclic polymorphisms. Preprint arXiv:2310.00514, 2024

    work page arXiv 2024

  51. [51]

    Richard E. Ladner. On the structure of polynomial time reducibility. J. ACM. , 22(1):155--171, 1975

    work page 1975

  52. [52]

    Existence theorems for weakly symmetric operations

    Mikl\'os Mar\'oti and Ralph McKenzie. Existence theorems for weakly symmetric operations. Algebra Univers. , 59(3):463--489, 2008

    work page 2008

  53. [53]

    Algebraic and algorithmic synergies between promise and infinite-domain csps

    Antoine Mottet. Algebraic and algorithmic synergies between promise and infinite-domain csps. In Proceedings of the 40th Annual ACM/IEEE Symposium on Logic in Computer Science - LICS '25 , pages 1--13. IEEE , 2025. to appear, preprint available at: https://arxiv.org/abs/2501.13740

    work page arXiv 2025

  54. [54]

    Smooth approximations and csps over finitely bounded homogeneous structures

    Antoine Mottet and Michael Pinsker. Smooth approximations and csps over finitely bounded homogeneous structures. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science - LICS '22 , pages 36:1--36:13, 2022

    work page 2022

  55. [55]

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

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

    work page 2024

  56. [56]

    The weakest nontrivial idempotent equations

    Miroslav Ol s \'a k. The weakest nontrivial idempotent equations. Bull. Lond. Math. Soc. , 49(6):1028--1047, 2017

    work page 2017

  57. [57]

    Total ordering problem

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

    work page 1979

  58. [58]

    Three fundamental questions in modern infinite-domain constraint satisfaction

    Michael Pinsker, Jakub Rydval, Moritz Sch\"obi, and Christoph Spiess. Three fundamental questions in modern infinite-domain constraint satisfaction. In Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science - MFCS '25 , volume 345, pages 83:1--83:20. Leibniz International Proceedings in Informatics (LIPIcs), 2025

    work page 2025

  59. [59]

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

    work page 2010

  60. [60]

    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

  61. [61]

    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

  62. [62]

    Strong subalgebras and the constraint satisfaction problem

    Dmitriy Zhuk. Strong subalgebras and the constraint satisfaction problem. J. Multiple Valued Log. Soft Comput. , 36(4-5):455--504, 2020

    work page 2020