Startseite der Technischen UniversitŠt Dresden

Persšnliche Werkzeuge
TU Dresden » Institute der Mathematik » Algebra » Professur für Algebra und Diskrete Strukturen


Publications: Preprints and publications since 2014:


  1. Topology is relevant (in the infinite-domain dichotomy conjecture for constraint satisfaction problems), with Antoine Mottet, Miroslav Olsak, Jakub Oprsal, Michael Pinsker, and Ross Willard. Accepted for publication in the proceedings of LICS'19. Preprint available at ArXiv:1901.04237.
  2. Structures with Small Orbit Growth, with Bertalan Bodor. Preprint available at ArXiv:1810.05657.
  3. Homomorphisms to the clone of projections (with Michael Pinsker and András Pongrácz). To appear in the Journal of Symbolic Logic. ArXiv:1409.4601.
  4. Two-element structures modulo primitive positive constructability, with Albert Vucaj. Preprint available at ArXiv:1905.12333.
  5. Canonical Functions: a proof via topological dynamics (with Michael Pinsker), Contributions to Discrete Mathematics, to appear. ArXiv:1610.09660.
  6. A polynomial-time algorithm for median-closed semilinear constraints, with Marcello Mamino. Preprint available at ArXiv:1808.10068.
  7. Constraint Satisfaction Problems for Reducts of Homogeneous Graphs (with Barnaby Martin, Michael Pinsker and András Pongrácz), Siam Journal on Computing, 49(4): 1224-1264. ArXiv:1602.05819.
  8. 2018

  9. Discrete Temporal Constraint Satisfaction Problems, with Barnaby Martin and Antoine Mottet, Journal of the ACM 65(2): 9:1-9:41. ArXiv:1503.08572.
  10. The complexity of disjunctive linear Diophantine constraints, with Marcello Mamino, Barnaby Martin and Antoine Mottet, In the proceedings of MFCS 2018: 33:1-33:16. ArXiv:1807.00985.
  11. Finite Relation Algebras with Normal Representations, RAMiCS 2018: 3-17. Postprint available at ArXiv:1810.13335
  12. Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains, with Marcello Mamino and Caterina Viola. CSL 2018: 12:1-12:22. ArXiv:1804.01710.
  13. Classification transfer for qualitative reasoning problems, with Barnaby Martin, Antoine Mottet, and Peter Jonsson. In the proceedings of IJCAI'18: 1256-1262. ArXiv:1805.02038.
  14. A Dichotomy for First-order Reducts of Unary Structures, with Antoine Mottet. Logical Methods in Computer Science 14(2). An extended abstract of an earlier version covering some of the results appeared under the title ``Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction'' in the proceedings of LICS'16, pages 623-632. ArXiv:1601.04520.
  15. The Universal Homogeneous Binary Tree (with David Bradley-Williams, Michael Pinsker, and András Pongrácz). Journal of Logic and Computation, 28(1): 133-163. ArXiv:1409.2170.
  16. A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP,

    with Florent Madelaine and Antoine Mottet. In the proceedings of LICS'18. ArXiv:1802.03255.
  17. Complexity of Combinations of Qualitative Constraint Satisfaction Problems (with Johannes Greiner). In the proceedings of IJCAR'18: 263-278 (the 9th International Joint Conference on Automated Reasoning). Available under arXiv:1801.05965.
  18. A counterexample to the reconstruction of countably categorical structures from their endomorphism monoids (with David Evans, Michael Kompatscher, and Michael Pinsker). Israel Journal of Mathematics, 224 (1): 57-82, 2018. Preprint available under arXiv:1510.00356.
  19. Tropically Convex Constraint Satisfaction, with Marcello Mamino. Theory of Computing Systems, 62(3): 481-509. An extended abstract of the paper appeared under the title "Max-Closed Semilinear Constraints" in the proceedings of CSR'16: 88-101. ArXiv:1506.04184.
  20. 2017

  21. Reconstructing the topology of clones (with Michael Pinsker and András Pongrácz). Transactions of the AMS, 369(5):3707-3740. ArXiv:1312.7699.
  22. Constraint Satisfaction Problems over Numeric Domains, survey with Marcello Mamino, pages 79--111 in: The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups Series, Volume 7, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
  23. A topological characterisation of endomorphism monoids of countable structures, with Friedrich Martin Schneider, Algebra Universalis, 77(3):251-269. ArXiv:1508.07404.
  24. A model-theoretic view on qualitative constraint reasoning, with Peter Jonsson, introductory survey article, Journal of Artificial Intelligence Research, 58:339-385, 2017.
  25. The complexity of phylogeny constraint satisfaction problems, with Peter Jonsson and Trung Phan Pham, ACM Transactions on Computational Logic (TOCL), 18(3). A conference version of this article appeared at STACS'16. ArXiv:1503.07310.
  26. 2016

  27. Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction, with Antoine Mottet, in proceedings of LICS'16, pages 623-632, arXiv:1601.04520.
  28. The Reducts of the Homogeneous Binary Branching C-relation, with Peter Jonsson and Trung Phan Pham, Journal of Symbolic Logic, 81(4), 1255-1297, 2016. ArXiv:1408.2554
  29. Distance Constraint Satisfaction Problems (with Barnaby Martin, Antoine Mottet, Michael Pinsker, and Víctor Dalmau), Information and Computation 247, 87-105, 2016. ArXiv:1004.3842.
  30. Reducts of structures and maximal-closed permutation groups (with Dugald Machpherson). In the Journal of Symbolic Logic, 81(3): 1087-1114 (2016). ArXiv:1310.6393.
  31. The complexity of phylogeny constraint satisfaction, with Peter Jonsson and Trung Phan Pham, in the proceedings of STACS'16, 20:1-20:13, 2016. ArXiv:1503.07310.
  32. Max-closed semilinear constraints, with Marcello Mamino. In the proceedings of CSR'16: 88-101. Preprint of long version available at ArXiv:1506.04184.
  33. Constraint Satisfaction Problems for reducts of homogeneous graphs (with Barnaby Martin, Michael Pinsker and András Pongrácz), in the proceedings of ICALP'16, 119:1-119:14. ArXiv:1602.05819.
  34. 2015

  35. Schaefer's Theorem for Graphs (with Michael Pinsker). Journal of the ACM 62(3): 19, 2015. ArXiv:1011.2894.
  36. Constraint Satisfaction Problems over the Integers with Successor, with Barnaby Martin and Antoine Mottet, in the proceedings of ICALP 2015, 2015.
  37. Ramsey Classes: Examples and Constructions, invited survey article for the British Combinatorial Conference, Surveys in Combinatorics 2015, London Mathematical Society Lecture Note Series 424, Cambridge University Press. ArXiv:1502.05146, 2015.
  38. Topological Birkhoff (with Michael Pinsker), Transactions of the American Mathematical Society, 367: 2527-2549, 2015. ArXiv:1203.1876
  39. The 42 reducts of the random ordered graph (with Michael Pinsker and András Pongrácz). Journal of the London Mathematical Society, 111(3): 591-632. ArXiv:1309.2165.

  40. 2014

  41. Minimal functions on the random graph (Manuel Bodirsky and Michael Pinsker), Israel Journal of Mathematics, 200(1):251-296, 2014. Preprint: ArXiv:1003.4030
  42. Tractability of quantified temporal constraints to the max (with Hubie Chen and Michal Wrona), International Journal of Algebra and Computation, 24(8):1141-1156, 2014.
  43. New Ramsey Classes from Old. Electronic Journal of Combinatorics 21(2): P2.22, 2014. arXiv:1204.3258.

Stand: 31.7.2019
Autor: Manuel Bodirsky



Gudrun Heinisch
Tel.: +49 351 463-35355

Zellescher Weg 12-14
Willersbau Zi. C 120

TU Dresden
01062 Dresden

Institut für Algebra
TU Dresden
Willersbau C 120
Zellescher Weg 12-14
01069 Dresden