photo

          

Michael Pinsker

Institut für Diskrete Mathematik & Geometrie
FG 1 Algebra
Technische Universität Wien
Wiedner Hauptstrasse 8-10/104
1040 Wien, Austria

       

Department of Algebra
Charles University Prague
Sokolovska 83
186 75 Prague 8
Czech Republic

Email:Write "marula", then the symbol commonly referred to as "at", and then gmx.at
Phone: +43 1 58801 10401
Fax:Really?


Who am I?

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

At the Vienna University of Technology, I am a faculty member of the Universal Algebra Group. I am also the principal investigator of the project Identities in polymorphism algebras of infinite structures of the Austrian Science Fund (FWF) from 05/2019 until 04/2022. Currently employed in the project are my PhD students Tomáš Nagy and Clemens Schindler. I am moreover hosting the Lise-Meitner FWF project An algebraic theory for PCSPs of Julius Jonušas.

At Charles University Prague, I am the principal investigator of the project Extending the scope of universal algebra of the Czech Grant Agency, carried out at the Department of Algebra from 01/2018 until 12/2020. My co-investigators are Libor Barto, Jakub Bulín, Michael Kompatscher, David Stanovský, and Mirek Olšák.

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

Here you can find my academic family, including my former doctoral advisor Martin Goldstern and my former doctoral student Michael Kompatscher.

          

photo

photo

          

News

Seminars:

In the current academic year, I am running two online seminars (in addition to the seminar of the research group): "Local Consistency Methods for Constraint Satisfaction Problems" (winter term) and "Automorphism groups of omega-categorical structures" (summer term). Please contact me if you are interested in joining any of these.

New preprint:

In Smooth approximations and CSPs over finitely bounded homogeneous structures (with A. Mottet), we develop a new machinery for proving CSP complexity dichotomies, and apply it to obtain a new one and to reprove (smoothly) many old ones.

Future talks and conference participation:

2021/01 Oligomorphic clones I, Homogeneous Structures: Model Theory meets Universal Algebra, Mathematisches Forschungsinstitut Oberwolfach (I'm also an organizer).
2021/02 Smooth approximations, 100th Arbeitstagung Allgemeine Algebra, Jagiellonian University, Kraków.
2021 Durham Symposium on the Mathematics of Constraint Satisfaction in Durham, UK (postponed from 2020/07).

These are slides / videos of some recent and not-so-recent talks of mine.

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


Publications

  • Smooth approximations and CSPs over finitely bounded homogeneous structures [arXiv]
    (with A. Mottet)
    Submitted.

  • Cores over Ramsey structures [arXiv]
    (with A. Mottet)
    Journal of Symbolic Logic, to appear.

  • 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.

  • When symmetries are not enough: a hierarchy of hard constraint satisfaction problems [arXiv]
    (with P. Gillibert, Y. Jonušas, M. Kompatscher, and A. Mottet)
    Submitted.

  • 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]
    (with M. Bodirsky)
    Contributions to Discrete Mathematics, to appear.

  • 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]
    (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, to appear (12 pages).

  • The universal homogeneous binary tree. [arXiv]
    (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.



Past scientific talks and conference participation

2020/09 Second CSP World Congress, Völs am Schlern (organizer).
2020/07 Hrushovski's encoding and omega-categorical CSP monsters, ICALP, The Cloud, Saarbrücken. [video]
2019/09 Topology: relevant or irrelevant? 57th Summer School on General Algebra and Ordered Sets in Karolinka, Czech Republic. [slides]
2019/06 What is symmetry?, CSP World Congress (CWC) 2019, Simon Fraser University, Vancouver.
2019/06 Topology is relevant (delivered by A. Mottet), Thirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) in Vancouver.
2019/03 (organizer), 97. Arbeitstagung Allgemeine Algebra (97th Workshop on General Algebra) at TU Wien.
2018/11 Canonical functions and the Ramsey property, revisited, Unifying Themes in Ramsey Theory at the Banff International Research Station (BIRS). [video]
2018/08 (no talk), Workshop on Logical Aspects of Quantum Information at the Lorentz center, Leiden.
2018/06 Loop conditions, The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl. [slides]
2018/04 Reconstructing structures from their clones, Set Theory, Model Theory and Applications, Eilat. [slides]
2018/01 Equations in algebras induced by beautiful first-order structures, Prague Gathering of Logicians/Beauty of Logic 2018, Prague. [slides]
2018/01 Canonical functions and the Ramsey property, revisited, AMS-ASL Special Session on Set Theory, Logic and Ramsey Theory at the JMM 2018, San Diego. [slides]
2017/07 Oligomorphic clones (tutorial), Tianfu Universal Algebra workshop, SWUFE Chengdu, China.
2017/06 The two dichotomy conjectures for infinite domain CSPs are equivalent, LICS 2017, Reykjavik. [slides]
2017/05 Equations in algebras from omega-categorical structures, Algebra seminar, TU Wien.
2017/03 Double shrinking Pseudo-Siggers, LIAFA, Paris 7.
2017/02 Equations in oligomorphic algebras, 93rd Workshop on General Algebra, Bern. [slides]
2016/10 Functions on homogeneous Ramsey structures (3 lectures), Ramsey DocCourse 2016, Charles University Prague. [poster] [Mike Pawliuk's notes]
2016/07 The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, LICS 2016, New York City. [slides]
2016/06 The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, Algebra Seminar, TU Wien.
2016/05 The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, Arbeitstagung Allgemeine Algebra 92, Prague.
2016/03 CSPs over homogeneous graphs, KAFKA seminar, Department of Algebra, Charles University Prague.
2016/01 Projecting function clones, Czech Academy of Sciences.
2015/12 Uniform Birkhoff, TU Dresden.
2015/11 Conjectures for clones over finitely bounded homogenous structures at the workshop Homogeneous Structures, Banff International Research Station [pdf]
2015/10 Uniform Birkhoff at the workshop Duality in Computer Science, Schloss Dagstuhl
2015/10 Uniform Birkhoff in the KAFKA seminar, Department of Algebra, Charles University Prague.
2015/09 New Topological Clones at LIAFA, Paris 7.
2015/07 Topological Clones at the LMS Durham Research Symposium Permutation Groups and Transformation Semigroups (2 lectures) [pdf]
2015/07 Constraint satisfaction problems on Kn-free graphs at the workshop The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl
2015/06 Topological Clones in Constraint Satisfaction at the conference Topology, Algebra, and Categories in Logic, Ischia, Italy [poster] [SLIDES]
2014/11 Constraint Satisfaction on infinite domains (tutorial) at Algebraic and Model Theoretical Methods in Constraint Satisfaction, Banff International Research Station. [pdf 1] [pdf 2] [pdf 3] [videos]
2014/11 Homogeneous structures: the older, the more descendants? at the University of Calgary.
2014/11 Algebraic and model theoretic methods in constraint satisfaction at CUNY Logic Workshop, New York. [pdf]
2014/10 Projective clone homomorphisms at STRUCO Meeting, Prague. [poster]
2014/10 Algebraic and model theoretic methods in constraint satisfaction at the Doc-Course, Prague. [pdf 1] [pdf 2] [pdf 3] [pdf 4] [poster]
2014/07 Clones on Ramsey structures at the Algebra and Clones Fest, Prague. [pdf]
2014/05 Reconstructing structures from their abstract clones at the ASL North American Annual Meeting (Special Session on Universal Algebra and CSPs), Boulder, Colorado. [pdf]
2014/04 Decomposing function clones on infinite sets in the Algebra Seminar at University of Colorado, Boulder.
2014/04 Introduction to Constraint Satisfaction over infinite structures at the Logic Seminar of the University of Colorado, Boulder [pdf].
2014/02 The topology of countable algebras, or: Polish clones at AAA 87, JKU Linz.
2014/01 Topological Birkhoff and Constraint Satisfaction at LIAFA, Automates et Applications, Paris.
2013/12 Reconstructing omega-categorical structures from their clones at Oberseminar mathematische Logik, Bonn.
2013/11 Topological Birkhoff and reconstructing the random graph at the Hausdorff Research Institute for Mathematics, Bonn.
2013/10 Reconstructing the topology of clones at Workshop on Homogeneous Structures (Hausdorff Research Institute for Mathematics, Bonn) [pdf].
2013/08 The 42 reducts of the random ordered graph at BLAST 2013: Boolean algebras, Lattices, Algebraic Logic, Set Theory, and Topology (Chapman University, Orange, California) [pdf slides] [pdf poster]
2013/06 The 42 reducts of the random ordered graph at the Vienna University of Technology
2013/06 The 42 reducts of the random ordered graph at the 4th Novi Sad Algebraic Conference - NSAC 2013 [pdf slides] [jpg poster]
2013/05 Finitary aspects of reducts of homogeneous structures at Eötvös University, Budapest
2012/11 Topological Birkhoff at the workshop The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl [pdf]
2012/07 TBA (=Topological Birkhoff and Applications) at the 2nd Workshop on Homogeneous Structures, Prague [pdf]
2012/06 Lattices of subgroups of the symmetric group at the AAA 84, Dresden [pdf]
2012/05 Schaefer's theorem for graphs, or: why to consult the infinite at times at the Tel Aviv University [pdf]
2012/05 Reducts of the random partial order at the Université Lyon 1
2012/03 Reducts of the random partial order at the Serbian Academy of Sciences and Arts, Belgrade
2012/03 Reducts of Ramsey structures: the canonical approach at the University of Novi Sad [pdf]
2012/03 Topological Birkhoff at the Technische Universität Wien
2012/03 Reducts of the random partial order at the Kurt Gödel Research Centre, Vienna
2011/12 Reducts of the random partial order at Paris 7 - Diderot
2011/11 Reducts of Ramsey structures: the canonical approach at Albert-Ludwigs-Universität Freiburg [pdf]
2011/10 Cooking with model theory, universal algebra and Ramsey theory in the complexity theory kitchen at Yeshiva University, New York  [pdf]
2011/08 Making the infinite finite: Polymorphisms on Ramsey structures at Workshop on Algebra and CSPs , Fields Institute, Toronto (pdf, audio mp3, Talk at Fields website)
2011/07 Reducts of Homogeneous Structures I: the Ramsey Property at London Mathematical Society Northern Regional Meeting and Workshop on Homogeneous Structures, University of Leeds (pdf)
2011/06 Constraint satisfaction with homogeneous templates at MALOA - From MAthematical LOgic to Applications, University of Leeds (pdf)
2011/06 Schaefer's theorem for graphs at STOC 2011, San Jose, California (pdf, video mp4)
2011/04 Decidability of definability at Eötvös University, Budapest
2011/04 Clone vs. permutation group lattices at Eötvös University, Budapest
2011/01 Ramsey clones and Schaefer's theorem for graphs in my habilitation colloquium at TU Wien (pdf)
2011/01 Decidability of definability at TU Wien
2010/10 Schaefer's theorem for graphs at Laboratoire d'Informatique de l'École Polytechnique (LIX), Palaiseau, France (pdf)
2010/07 Functions on reducts of the random graph at Logic Colloquium 2010, Paris 7 Diderot (pdf)
2010/06 Decidability of primitive positive definability at the Workshop on Algebra, Complexity, CSP, and sunshine, Centro de Algebra de Universidade de Lisboa (abstract)
2010/06 Clones on homogeneous structures and Schaefer's theorem for graphs at ICAL 2010 (``Jardafest''), Prague (abstract / slides)
2010/04 Reducts of homogeneous structures with the Ramsey-property at TU Wien (pdf)
2010/03 Reducts of homogeneous structures with the Ramsey-property at Paris 7 (pdf)
2009/10 Clones on the random graph: Towards Schaefer's theorem for graphs at at the RIMS research meeting on Logic and Algebra related to Computer Science, Kyoto
2009/08 Structure in mappings on the random graph at NSAC09, Novi Sad (pdf)
2009/06 All reducts of the random graph are model-complete in the Wiener Algebra Seminar at TU Wien
2009/05 Mappings on the random graph at Université Claude Bernard, Lyon
2009/01 Clones on infinite sets: Interactions with Set theory and Model theory at Paris 7 (pdf)
2008/11 Closed permutation groups and reducts of relational structures at Université de Caen
2008/10 Unterverbände des lokalen Klonverbandes in the Wiener Algebra Seminar at TU Wien
2008/08 Many independent equality constraints at SSAOS 2008 in Trest, Czech Republic (pdf)
2008/07 Monoidal intervals and algebraic lattices beyond ZFC at the RIMS research meeting on Clone Theory and Discrete Mathematics in Kyoto
2008/05 Sublattices of the lattice of local clones at ROGICS'08 in Mahdia, Tunisia (pdf)
2008/05 Clones on infinite sets at Université de Caen
2007/11 Applied Algebra 3: Further reducts of relational structures at TU Wien
2007/11 Sublattices of the clone lattice at Technische Universität Graz
2007/10 Reducts of relational structures and local clones in the Kafka seminar at Univerzita Karlova, Prague
2007/10 Clones I have met since 2004 in the legendary Trnková seminar at Univerzita Karlova, Prague
2007/10 Applied Algebra 2: Reducts of relational structures, CSP and local clones at TU Wien
2007/06 The reducts of (N,=) at OAL2007 in Nashville, Tennessee (pdf)
2007/06 Clones from ideals at the AAA 74 in Tampere (pdf)
2007/05 Clones in universal algebra in the lecture series ``Wissenswertes aus der Mathematik'' held at TU Wien (pdf)
2007/03 Cardinalities of intervals in the clone lattice at TU Wien
2007/02 Local clones containing the permutations at the AAA 73 in Klagenfurt
2007/01 The Constraint Satisfaction Problem and local clones at TU Wien
2006/11 An introduction to clones at the Humboldt-Universität zu Berlin
2006/06 Algebraische Verbände sind Unterverbände von Klonverbänden in the Wiener Algebra Seminar at TU Wien (pdf)
2006/06 Algebraic lattices are complete sublattices of the clone lattice over an infinite set at the AAA 72 in Budapest (pdf)
2006/02 Intervals of the clone lattice at the Warsaw University of Technology
2006/02 The minimal clones above the permutations at the AAA 71 in Bedlewo, Poland (pdf)
2005/08 Monoids above the permutations at the International Algebraic Conference in Ekaterinburg (pdf)
2005/07 Lattices of order ideals as monoidal intervals at NSAC'05 in Novi Sad (pdf)
2005/07 Monoids above the permutations at the conference on Universal Algebra and Lattice Theory in Szeged (pdf)
2005/06 The clone generated by all binary two-valued operations: An application of infinite to finite clone theory at RIMS in Kyoto
2005/06 A survey of clones on infinite sets at RIMS in Kyoto
2005/06 The interval above the clone T2 at Meiji University Tokyo
2005/01 The clone lattice: Introduction and partition at International Christian's University Tokyo
   
Older Talks  


Other activities