Michael Pinsker

Who am I?

I am a mathematician. My research interests include universal algebra and interactions with model theory, theoretical computer science, and Ramsey theory.

At the Vienna University of Technology, I am a full professor and head of the research unit Algebra. Moreover, I am a principal investigator of the Synergy Grant POCOCOP (Polynomial-time Computation: Opening the Blackboxes in Constraint Problems) of the European Research Council (ERC) (03/2023 - 02/2029, jointly with Libor Barto and Manuel Bodirsky). I am also a principal investigator of the project Constraint Satisfaction Problems: beyond the finite case of the Austrian Science Fund (FWF) and the Polish Science Center (NCN) (10/2022 - 09/2026, jointly with Marcin Kozik). Currently working in my research unit: Gerhard Dorfer, Mike Behrisch, and Peter Holy (faculty); Piotr Kawalek, Paolo Marimon, and Jakub Rydval (postdocs); Johanna Brunar, Moritz Schöbi, Roman Feller (PhD students); Tomas Nagy (visiting postdoc); Christoph Spiess (MA student); Maximilian König (project manager POCOCOP).

I am an associate editor of the journal Algebra Universalis, published by Springer. We welcome submissions through the journal's editorial system.

I am a member of the steering committees of the Workshop on General Algebra and the CWC, and a regular co-organizer of the latter.

I belong to the executive board of the Vienna School of Mathematics. I moreover co-organize the yearly Early Student Award meetings of the Austrian Mathematical Society.

Here you can find my academic family, including my former doctoral advisor Martin Goldstern and my former PhD students Clemens Schindler, Tomas Nagy, and Michael Kompatscher.

News

ERC Synergy Grant POCOCOP:

Together with Libor Barto (Charles University Prague) and Manuel Bodirsky (TU Dresden) we have been awarded a Synergy Grant by the European Research Council (ERC) for our project POCOCOP (Polynomial-time Computation: Opening the Blackboxes in Constraint Problems). The project started in 03/2023 for a duration of 6 years. [TU Wien Press release (German)] [ERC press release]

Jobs:

Informal inquiries about future postdoc or Ph.D. positions are welcome!

Students:

Please contact me if you are interested in writing a thesis (at any level) or seminar work on a topic at least remotely connected to my research interests!
In the academic year 2024/25, I am going to be involved in the following courses: Winter term: Linear Algebra I (4.5+2), Algebra II (3+1), Model theory II (2), Local Consistency of CSPs (2); Summer term: Linear Algebra II (4+2), Finite Model Theory (2+1), Automorphism groups of omega-categorical structures (2).

Recent and future events:

All slides / videos of all scientific talks ever can be found further down the page.

Publications

• Minimal operations over permutation groups [arXiv]
  (with P. Marimon)
  Preprint.

• Containment for Guarded Monotone Strict NP [arXiv]
  (with A. Barsukov and J. Rydval)
  Submitted.

• An algebraic proof of the graph orientation problem dichotomy for forbidden tournaments [arXiv]
  (with R. Feller)
  Submitted.

• Strict width for Constraint Satisfaction Problems over homogeneous structures of finite duality [arXiv]
  (with T. Nagy)
  Submitted.

• On the Zariski topology on endomorphism monoids of omega-categorical structures [arXiv] [DOI]
  (with C. Schindler)
  Journal of Symbolic Logic, to appear.

• The semigroup of increasing functions on the rational numbers has a unique Polish topology [arXiv]
  (with C. Schindler)
  Submitted.

• Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structures
  (with A. Mottet)
  Journal of the ACM 71(5), #36, 1-47, 2024.

• Symmetries of structures that fail to interpret something finite [arXiv]
  (with L. Barto, B. Bodor, M. Kozik, A. Mottet)
  Proceedings of the Thirty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 1-13, 2023. (distinguished paper)

• Polish topologies on endomorphism monoids of relational structures [arXiv] [DOI]
  (with L. Elliott, J. Jonušas, J. D. Mitchell, Y. Péresse)
  Advances in Mathematics 431, 109214, 2023.

• An order out of nowhere: a new algorithm for infinite-domain CSPs [arXiv] [DOI]
  (with A. Mottet, T. Nagy)
  51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 148:1--148:18, 2024.

• Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough [arXiv]
  (with A. Mottet, T. Nagy, M. Wrona)
  SIAM Journal on Computing, to appear.

• SURVEY! Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep [arXiv] [DOI]
  Proceedings of the 2022 IEEE 52nd Conference on Multi-Valued Logic, 80-87, 2022. (invited paper)

• Permutation groups on countable vector spaces over prime fields [arXiv]
  (with B. Bodor, L. Schiffer, and Cs. Szabó)
  Submitted.

• Smooth approximations and relational width collapses [arXiv] [DOI]
  (with A. Mottet, T. Nagy, and M. Wrona)
  Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP 2021), 138:1-138:20, 2021.

• Smooth approximations and CSPs over finitely bounded homogeneous structures [arXiv] [DOI]
  (with A. Mottet)
  Proceedings of the Thirty-Seventh Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), #36, 1-13, 2022.

• Cores over Ramsey structures [arXiv] [DOI]
  (with A. Mottet)
  Journal of Symbolic Logic 86(1), 352 - 361, 2021.

• Omega-categorical structures avoiding height 1 identities [arXiv] [DOI]
  (with M. Bodirsky, A. Mottet, M. Olšák, J. Opršal, and R. Willard)
  Transactions of the AMS 374(1), 327-350, 2021.

• Hrushovski's encoding and omega-categorical CSP monsters [DOI]
  (with P. Gillibert, Y. Jonušas, M. Kompatscher, and A. Mottet)
  Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP 2020), 131:1-131:17, 2020.

• When symmetries are not enough: a hierarchy of hard constraint satisfaction problems [arXiv]
  (with P. Gillibert, Y. Jonušas, M. Kompatscher, and A. Mottet)
  SIAM Journal on Computing 51(2), 175-213, 2022.

• Topology is relevant [arXiv] [DOI]
  (with M. Bodirsky, A. Mottet, M. Olšák, J. Opršal, and R. Willard)
  34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2019.

• Pseudo-loop conditions [arXiv] [DOI]
  (with P. Gillibert and J. Jonušas)
  Bulletin of the London Mathematical Society 51(5), 917-936, 2019.

• Topology is irrelevant [arXiv] [DOI]
  (with L. Barto)
  SIAM Journal on Computing 49(2), 365-393, 2020.

• Equations in oligomorphic clones and the Constraint Satisfaction Problem for omega-categorical structures [arXiv] [DOI]
  (with L. Barto, M. Kompatscher, M. Olšák, and T. van Pham)
  Journal of Mathematical Logic 19(2), #1950010, 2019.

• The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems [DOI]
  (with L. Barto, M. Kompatscher, M. Olšák, and T. van Pham)
  Proceedings of the Symposium on Logic in Computer Science (LICS) 2017, 1-12.

• Canonical functions: a proof via topological dynamics [arXiv] [DOI]
  (with M. Bodirsky)
  Contributions to Discrete Mathematics 16(2), 36-45, 2021.

• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. [arXiv] [DOI]
  (with L. Barto)
  Proceedings of the Symposium on Logic in Computer Science (LICS) 2016, 615-622, 2016.

• Uniform Birkhoff. [pdf][DOI]
  (with M. Gehrke)
  Journal of Pure and Applied Algebra 222(5), 1242-1250, 2018.

• Constraint satisfaction problems for reducts of homogeneous graphs. [arXiv][DOI]
  (with M. Bodirsky, B. Martin, and A. Pongrácz)
  SIAM Journal on Computing 48(4), 1224-1264, 2019.
  A conference version appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP) 2016, 119:1-119:12, 2016. [DOI]

• A counterexample to the reconstruction of omega-categorical structures from their endomorphism monoids. [arXiv] [DOI]
  (with M. Bodirsky, D. Evans, and M. Kompatscher)
  Israel Journal of Mathematics 224(1), 57-82, 2018.

• The wonderland of reflections (= the double shrink). [arXiv]
  (with L. Barto and J. Opršal)
  Israel Journal of Mathematics 223(1), 363-398, 2018.

• Projective clone homomorphisms. [arXiv] [DOI]
  (with M. Bodirsky and A. Pongrácz)
  Journal of Symbolic Logic 86(1), 148-161, 2021.

• The universal homogeneous binary tree. [arXiv] [DOI]
  (with M. Bodirsky, D. Bradley-Williams, A. Pongrácz)
  Journal of Logic and Computation 28(1), 133-163, 2018.

• Permutations on the random permutation. [pdf]
  (with J. Linman)
  Electronic Journal of Combinatorics 22 (2), #P2.54, 1-22, 2015.

• Reconstructing the topology of clones. [arXiv]
  (with M. Bodirsky and A. Pongrácz)
  Transactions of the AMS 369, 3707-3740, 2017.

• The 42 reducts of the random ordered graph. [pdf]
  (with M. Bodirsky and A. Pongrácz)
  Proceedings of the LMS 111 (3), 591-632, 2015 (42 pages).

• Reducts of the random partial order. [pdf]
  (with P. P. Pach, G. Pluhár, A. Pongrácz, Cs. Szabó)
  Advances in Mathematics 267, 94-120, 2014.

• Lattices of subgroups of the symmetric group.
  (with S. Shelah)
  In preparation.

• Topological Birkhoff. [pdf]
  (with M. Bodirsky)
  Transactions of the AMS 367, 2527-2549, 2015.

• A new operation on partially ordered sets. [pdf]
  (with P. P. Pach, A. Pongrácz, Cs. Szabó)
  Journal of Combinatorial Theory, Series A 120, 1450-1462, 2013.

• A closed algebra with a non-Borel clone and an ideal with a Borel clone. [pdf]
  (with M. Goldstern and S. Shelah)
  International Journal of Algebra and Computation 23 (5), 1115-1125, 2013.

• Universality of the lattice of transformation monoids. [pdf]
  (with S. Shelah)
  Proceedings of the AMS 141 (9), 3005-3011, 2013.

• SURVEY! Reducts of Ramsey structures. [pdf]
  (with M. Bodirsky)
  AMS Contemporary Mathematics vol. 558 (Model Theoretic Methods in Finite Combinatorics), 489-519, 2011.

• Decidability of definability. [pdf]
  (with M. Bodirsky and T. Tsankov)
  Journal of Symbolic Logic 78 (4), 1036-1054, 2013. A conference version appeared in the Proceedings of LICS 2011, pages 321-328.

• Schaefer's theorem for graphs. [pdf conference version]; [full version (arXiv)]
  (with M. Bodirsky)
  Journal of the ACM 62 (3), #19, 2015 (52 pages). A conference version appeared in the Proceedings of STOC 2011, pages 655-664.

• More clones on infinite sets.
  Habilitation thesis, Technische Universität Wien, 2011.

• Non-properties of canonical extensions of local clones. [pdf]
  (with M. Goldstern)
  Preprint, 12 pages.

• Minimal functions on the random graph. [pdf]
  (with M. Bodirsky)
  Israel Journal of Mathematics 200 (1), 251-296, 2014.

• Distance constraint satisfaction problems. [arXiv] [DOI]
  (with M. Bodirsky, V. Dalmau, B. Martin, and A. Mottet)
  Information and Computation 247, 87-105, 2016. A conference version appeared in the Proceedings of MFCS 2010, pages 162-173.

• All reducts of the random graph are model-complete. [pdf]
  (with M. Bodirsky)
  Preprint, 14 pages.

• More sublattices of the lattice of local clones. [pdf]
  Order 27 (3), 353-364, 2010.

• Sublattices of the lattice of local clones. [pdf]
  Proceedings of the ROGICS'08 conference, pages 80-87, 2008.

• The reducts of equality up to primitive positive interdefinability. [pdf]
  (with M. Bodirsky and H. Chen)
  Journal of Symbolic Logic 75 (4), 1249-1292, 2010.

• Clones from ideals. [pdf]
  (with M. Beiglböck, L. Heindorf, and M. Goldstern)
  International Journal of Algebra and Computation 19 (3), 397-421, 2009.

• Ideal clones: Solution to a problem of Czédli and Heindorf. [pdf]
  (with M. Goldstern)
  Studia Scientiarum Mathematicarum Hungarica 47 (4), 419-429, 2010.

• SURVEY! A survey of clones on infinite sets. [pdf]
  (with M. Goldstern)
  Algebra Universalis 59, 365-403, 2008.

• Algebraic lattices are complete sublattices of the clone lattice over an infinite set. [pdf]
  Fundamenta Mathematicae 195(1), 1-10, 2007.

• The minimal clones above the permutations. [pdf]
  (with H. Machida)
  Semigroup Forum 75, 181-211, 2007.

• Monoidal intervals of clones on infinite sets. [pdf]
  Discrete Mathematics 308, 59-70, 2008.

• T2. [pdf]
  RIMS Kokyuroku Vol. 1846, 87-93, 2013.

• Some polynomials generating minimal clones. [pdf]
  (with H. Machida)
  Journal of Multiple-Valued Logic 13 (4-6), 353-366, 2007.

• Polynomials as generators of minimal clones.
  (with H. Machida)
  Proc. 37th Int. Symposium on Multiple-Valued Logic (IEEE), 2007.

• Some observations on minimal clones.
  (with H. Machida)
  Proc. 36th Int. Symposium on Multiple-Valued Logic (IEEE), 2006.

• Precomplete clones on infinite sets which are closed under conjugation. [pdf]
  Monatshefte für Mathematik 148(2), 139-152, 2006.

• The number of unary clones containing the permutations on an infinite set. [pdf]
  Acta Scientiarum Mathematicarum 71, 461-467, 2005.

• Maximal clones on uncountable sets that include all permutations. [pdf]
  Algebra Universalis 54 (2), 129-148, 2005.

• Clones on infinite sets. [arXiv]
  Ph.D. Thesis, Technische Universität Wien.

• Clones containing all almost unary functions. [pdf]
  Algebra Universalis 51, 235-255, 2004.

• The clone generated by the median functions. [pdf]
  Contributions to General Algebra 15, 99-108, 2004.

• Rosenberg's characterization of maximal clones. [arXiv]
  Diploma Thesis, Technische Universität Wien.

    Preprints of most publications can also be downloaded from the arXiv.org archive.