Startseite der Technischen UniversitŠt Dresden

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

Publikationen

Publications: Publications since 2014:

    2020+

  1. A draft of my book project with the title `Complexity of Infinite-Domain Constraint Satisfaction', submitted for publication in the LNL Series of Cambridge University Press, May 2020.
  2. Structures with Small Orbit Growth, with Bertalan Bodor. Preprint available at ArXiv:1810.05657.
  3. 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. In the proceedings of LICS'19. Preprint available at ArXiv:1901.04237.
  4. Temporal Constraint Satisfaction Problems in Fixed-Point Logic, with Jakub Rydval and Wied Pakusa. Accepted for publication in the proceedings of LICS'20.
  5. ASNP: a tame fragment of existential second-order logic, with Simon Knäuer and Florian Starke. Accepted for publication in the proceedings of Computing in Europe (CiE). Preprint available at ArXiv:2001.08190.
  6. Two-element structures modulo primitive positive constructability, with Albert Vucaj. Algebra Universalis, 81:20. Preprint available at ArXiv:1905.12333.
  7. Canonical Functions: a proof via topological dynamics, with Michael Pinsker. Contributions to Discrete Mathematics, to appear. ArXiv:1610.09660.
  8. A polynomial-time algorithm for median-closed semilinear constraints, with Marcello Mamino. Preprint available at ArXiv:1808.10068.
  9. Hardness of Network Satisfaction for Relation Algebras with Normal Representations, with Simon Knäuer, in the proceedings of RAMICS 2020, Palaiseau, ArXiv:1912.08482.
  10. Solving Equation Systems in Countably Categorical Algebras, with Thomas Quinn-Gregson, preprint, ArXiv:1912.09815.
  11. Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation, with Marcello Mamino and Caterina Viola. Submitted for journal publication. Preprint available at ArXiv:1912.09298.
  12. Smooth digraphs modulo primitive positive constructability, with Florian Starke and Albert Vucaj. Preprint available at ArXiv:1906.05699.
  13. The Complexity of Combinations of Qualitative Constraint Satisfaction Problems, with Johannes Greiner. Logical Methods in Computer Science, 16(1).
  14. 2019

  15. Homomorphisms to the clone of projections, with Michael Pinsker and András Pongrácz. Journal of Symbolic Logic. ArXiv:1409.4601.
  16. 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. In the proceedings of LICS'19. Preprint available at ArXiv:1901.04237.
  17. 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.
  18. 2018

  19. Discrete Temporal Constraint Satisfaction Problems, with Barnaby Martin and Antoine Mottet, Journal of the ACM 65(2): 9:1-9:41. ArXiv:1503.08572.
  20. The complexity of disjunctive linear Diophantine constraints, with Marcello Mamino, Barnaby Martin and Antoine Mottet, In the proceedings of MFCS'18: 33:1-33:16. ArXiv:1807.00985.
  21. Finite Relation Algebras with Normal Representations, RAMiCS'18: 3-17. Postprint available at ArXiv:1810.13335
  22. Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains, with Marcello Mamino and Caterina Viola. In the proceedings of CSL'18: 12:1-12:22. ArXiv:1804.01710.
  23. 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.
  24. 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.
  25. 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.
  26. 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.
  27. 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.
  28. 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.
  29. 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.
  30. 2017

  31. Reconstructing the topology of clones, with Michael Pinsker and András Pongrácz. Transactions of the AMS, 369(5):3707-3740. ArXiv:1312.7699.
  32. 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.
  33. A topological characterisation of endomorphism monoids of countable structures, with Friedrich Martin Schneider, Algebra Universalis, 77(3):251-269. ArXiv:1508.07404.
  34. A model-theoretic view on qualitative constraint reasoning, with Peter Jonsson, introductory survey article, Journal of Artificial Intelligence Research, 58:339-385, 2017.
  35. 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.
  36. 2016

  37. Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction, with Antoine Mottet, in the proceedings of LICS'16, pages 623-632. Postprint arXiv:1601.04520.
  38. 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
  39. 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.
  40. 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.
  41. 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.
  42. Max-closed semilinear constraints, with Marcello Mamino. In the proceedings of CSR'16: 88-101. Preprint of long version available at ArXiv:1506.04184.
  43. 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.
  44. 2015

  45. Schaefer's Theorem for Graphs, with Michael Pinsker. Journal of the ACM 62(3): 19, 2015. ArXiv:1011.2894.
  46. Constraint Satisfaction Problems over the Integers with Successor, with Barnaby Martin and Antoine Mottet, in the proceedings of ICALP 2015, 2015.
  47. 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.
  48. Topological Birkhoff, with Michael Pinsker. Transactions of the American Mathematical Society, 367: 2527-2549, 2015. ArXiv:1203.1876
  49. 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.

  50. 2014

  51. Minimal functions on the random graph (Manuel Bodirsky and Michael Pinsker), Israel Journal of Mathematics, 200(1):251-296, 2014. Preprint: ArXiv:1003.4030
  52. 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.
  53. New Ramsey Classes from Old. Electronic Journal of Combinatorics 21(2): P2.22, 2014. arXiv:1204.3258.


Stand: 3.05.2020
Autor: Manuel Bodirsky

Kontakt

Email:
Manuel.Bodirsky@tu-dresden.de

Sekretariat:
Cindy Röhling
Tel.: +49 351 463-35355
Email: i.algebra@tu-dresden.de

Sitz:
Zellescher Weg 12-14
Willersbau Zi. C 120


Post:
TU Dresden
01062 Dresden

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