Michael Kompatscher

Address:
KA MFF UK
Sokolovská 83
18675 Praha 8
Czech Republic

Room: K313 on the 3rd floor

Email: kompatscher@karlin.mff.cuni.cz, michael@logic.at

ResearchGate: Michael Kompatscher
OrcID: 0000-0002-0163-6604

About me

I am an assistant professor at the Department of Algebra of Charles University in Prague. In my research I mainly focus on universal algebra and its applications in theoretical computer science. My broader interest also include model theory, and structural Ramsey theory.

I finished my PhD in 2017 at TU Wien under the supervision of Michael Pinsker, for my academic family tree, see here. I have also been a postdoctorial reseacher at the University of Oxford (under Standa Živný) and Charles University (under Libor Barto and Alex Kazda).

News / upcoming talks

Together with Zuzka Patáková I am organizing the weekly Algebra Colloquium.
09.06-11.06: Short pp-definitions for algebras with few subpowers at AAA93, Tartu, Estonia
02.07-07.07: Algebras with short pp-definitions at TCA2023, Pocinho, Portugal

Teaching

In spring semester 2023 I am teaching

Algebra 2 for Computer Scientists
Exercise sessions of Universal Algebra 2

For information about past teaching see here.

Publications

Preprints

Short definitions in constraint languages. [arXiv]
with Jakub Bulín
submitted, 14 pages.
CSAT and CEQV for nilpotent algebras of Fitting length > 2. [arXiv]
preprint, 20 pages.
Circuit equivalence in 2-nilpotent algebras. [arXiv]
with Piotr Kawałek, Jacek Krzaczkowski
preprint, 15 pages.

In Journals

Forbidden cycles in metrically homogeneous graphs. [arXiv]
with Jan Hubička, Matěj Konečný
to appear in the European Journal of Combinatorics, 25 pages.
Ramsey expansions of metrically homogeneous graphs. [arXiv]
with Andrés Aranda, David Bradley-Williams, Jan Hubička, Miltiadis Karamanlis, Matěj Konečný, Micheal Pawliuk
to appear in the European Journal of Combinatorics, 57 pages.
The local-global property for G-invariant terms. [doi] [arXiv]
with Alex Kazda
International Journal of Algebra and Computation, 32(6), 1209-1231, 2022.
CC-circuits and the expressive power of nilpotent algebras. [doi] [arXiv]
Logical Methods in Computer Science, 18(2), 12:1–12:15, 2022.
When symmetries are not enough: A hierarchy of hard constraint satisfaction problems. [doi] [arXiv]
with Pierre Gillibert, Julius Jonušas, Antoine Mottet, Michael Pinsker
SIAM Journal on Computing, 5(2), 175-213, 2022.
Completing graphs to metric spaces. [url] [doi] [arXiv]
with Andrés Aranda, David Bradley-Williams, Eng Keat Hng, Jan Hubička, Miltiadis Karamanlis, Matěj Konečný, Micheal Pawliuk
Contributions to Discrete Mathematics, 16(2) 71-89, 2021.
Some notes on extended equation solvability and identity checking for groups. [doi] [arXiv]
Acta Mathematica Hungarica, 159(1) 246-256, Oct 2019.
The equation solvability problem over supernilpotent algebras with Mal’cev term. [doi] [arXiv]
International Journal of Algebra and Computation, 28(6) 1005–1015, 2018.
Equations in oligomorphic clones and the constraint satisfaction problem for ⍵-categorical structures. [doi] [arXiv]
with Libor Barto, Mirek Olšák, Michael Pinsker, Trung Van Pham
Journal of Mathematical Logic, 19(2) #1950010, 2019.
A complexity dichotomy for poset constraint satisfaction. [url] [arXiv]
with Trung Van Pham
Journal of Applied Logic, 5(8) 1663-1696, 2018.
2^ﬡ₀ pairwise nonisomorphic maximal-closed subgroups of Sym(N) via the classification of the reducts of the Henson digraphs. [doi] [arXiv]
with Lovkush Agarwal
Journal of Symbolic Logic, 83(2) 395-415, 2018.
A counterexample to the reconstruction of ⍵-categorical structures from their endomorphism monoids. [doi] [arXiv]
with Manuel Bodirsky, David Evans, Michael Pinsker
Israel Journal of Mathematics, 224(1) 57-82, 2018.

In Proceedings

Hrushovski's encoding and omega-categorical CSP monsters. [doi]
with Pierre Gillibert, Julius Jonušas, Antoine Mottet, Michael Pinsker
Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP 2020), p131:1--131:17.
Completing graphs to metric spaces. [doi]
with Andrés Aranda, David Bradley-Williams, Eng Keat Hng, Jan Hubička, Miltiadis Karamanlis, Matěj Konečný, Micheal Pawliuk
Special Issue of EUROCOMB'17 in Electronic Notes in Discrete Mathematics, Volume 61, August 2017, Pages 53-60.
The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems. [doi]
with Libor Barto, Mirek Olšák, Michael Pinsker and Trung Van Pham
Proceedings of the 32nd Symposium on Logic in Computer Science (LICS 2017), 1-12.
A complexity dichotomy for poset constraint satisfaction. [doi]
with Trung Van Pham
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), p47:1–47:12

Theses

Clones and homogeneous structures.
PhD thesis, TU Wien 2017, supervised by Michael Pinsker.
Gegenbeispiele zu drei Vermutungen über Kategorizität.
Master thesis, TU Wien 2014, supervised by Martin Goldstern.

Talks


2023/03	Introduction of the new assistant professors of the School of Mathematics - [slides]
2021/06	Finitely based 2-nilpotent Maltsev algebras at AAA102, University of Szeged - [slides]
2021/05	! Finitely tractable PCSPs at The Constraint Satisfaction Problem: Complexity and Approximability at Schloss Dagstuhl – Leibniz-Zentrum für Informatik - [slides]
2021/11	G-terms and the local-global property, at the PALS online seminar - [slides]
2021/10	Solving equations: a computational perspective at the Algebra Colloquium of the Department of Algebra, Charles University.
2021/02	Failure of local-to-global at AAA100 in Krakow (online) - [slides]
2020/11	CEQV and CSAT for nilpotent Maltsev algebras, at the Panglobal Algbra and Logic Seminar of CU Boulder - [slides]
2020/03	The complexity of solving equations, SIAM Chapters seminar Prague
2020/02	! CC-Circuits and the expressive power of nilpotent algebras, AAA99, Siena - [slides]
2020/01	! CC-Circuits and the expressive power of nilpotent algebras, Birkhoff Seminar, CU Boulder - [slides]
2020/01	Topology is relevant (in discussing the complexity of omega-categorical CSPs), Joint Mathematics Meetings, AMS Session on Algebra and Algebraic Geometry, Denver - [slides]
2019/11	Computational problems over nilpotent algebras (from modular varieties), Seminar of Algebra and Discrete Mathematics, JKU Linz
2019/09	CC-circuits and the expressive power of nilpotent algebras, SSAOS2019, Karolinka, Czech Republic - [slides]
2019/06	The equivalence problem for nilpotent algebras, AAA98, TU Dresden - [slides]
2019/06	Checking commutator identities in finite groups, SANDGAL2019, Cremona - [slides]
2019/05	The equivalence problem for nilpotent algebras, BLAST2019, Boulder - [slides] (see AAA98 for corrected version)
2019/03	Solving equations in finite groups extended by their commutator, at AAA97, TU Wien - [slides]
2018/06	! Nilpotency and the complexity of the equation solvability problem, at the First Algebra Week, University of Siena.
2018/06	! The Equivalence of Two Dichotomy Conjectures for Infinite Domain CSPs, at The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2018/05	The complexity of solving equations and checking identities, at the International Seminar of the Institute for Algebra of TU Dresden
2018/03	! CSPs of infinite structures and equations in oligomorphic clones, in the Theoretical Computer Science Seminar of Jagiellonian University in Krakow.
2018/03	The equation solvability problem, at the Algebra Seminar of TU Wien.
2018/02	Equation solving over supernilpotent Mal'cev algebras is tractable at AAA95 in Bratislava - [slides]
2017/12	Equation solvability in supernilpotent Mal'cev algebras, in the KAFKA Seminar
2017/07	! Oligomorphic clones - tutorial with Michael Pinsker, Tianfu Universal Algebra workshop, SWUFE Chengdu, China
2017/06	Linearization of certain non-trivial equations in oligomorphic clones at AAA94+NSAC2017, University of Novi Sad - [slides]
2017/05	Completing edge-labelled graphs to metric spaces - AGDM Seminar, Wien - [slides]
2017/05	Cores of omega-categorical structures - in the Algebra Seminar of TU Wien
2017/03	A complexity dichotomy for poset constraint satisfaction - STACS2017, Hannover - [slides]
2017/02	A new proof of the existence of cores of ⍵-categorical structures - AAA93, FH Bern - [slides]
2017/01	The two dichotomy conjectures for infinite domain CSPs - Theory and Logic Seminar of TU Wien
2016/11	An introduction to Ramsey theory, at the Fall school of the Algebra department of Charles University - [slides]
2016/08	Constraint satisfaction problems over the random poset, at the Logic Colloquium 2016, Leeds
2016/05	CSPs over the random partial order, at AAA92 in Prague - [slides]
2016/04	Constraint satisfaction problems over infinite domains with Trung Van Pham, in the Theory and Logic Seminar of TU Wien - [slides]
2016/04	A complexity dichotomy for Poset-SAT in the Algebra Seminar of TU Wien - [slides]
2016/02	2^⍵ many maximal-closed subgroups of Sym(⍵) via Henson digraphs at New Pathways between Group Theory and Model Theory in Mülheim an der Ruhr - [slides]
2015/12	Maximal subgroups of Sym(⍵) via Henson digraphs in the KAFKA Seminar, Charles-University Prague - [slides]
2015/11	! A counterexample on the reconstruction of oligomorphic clones at the workshop Homogeneous structures at BIRS, Banff - [video]
2015/10	! Algebraic methods in constraint satisfaction at Matej Bel University, Banská Bystrica
2015/10	Reducts of Henson digraphs in the Wiener Algebra Seminar of TU Wien
2015/06	Endomorphism monoids of ⍵-categorical structures at TACL 2015, Ischia, Italy - [slides]
2015/05	Dichotomy results for constraint satisfaction problems at PhDs in Logic VII, TU Wien - [slides]
2015/04	Reconstruction of ⍵-categorical structures in the KAFKA Seminar, Charles-University Prague
2015/04	! Endomorphism monoids of ⍵-categorical structures in the International Seminar of the Institut für Algebra, TU Dresden - [slides]
2014/10	Definierbare Strukturen in the Algebra Seminar of TU Wien

!... invited talks/invitational events

Other conferences and workshops

2023/03: Spring school of the Department of Algebra, talk coordination
2022/09: 4th CSP World Congress in Molveno, Italy.
2021/11: Škola v přírodě of the Department of Algebra, Charles University.
2020/09: I was one of the organizers of the second CSP World Congress in my hometown Völs am Schlern
2020/06: AAA101, Novi Sad (online)
2019/06: Second Algebra Week, Siena
2018/09: From permutation groups to model theory, Edinburgh
2018/09: 56th Summer school on algebra and ordered sets, Špindlerův Mlýn, Czech Republic.
2018/08: Midsummer combinatorial workshop XXIII at KAM, Charles University Prague.
2018/01: Prague Gathering of Logicians and Beauty of Logic 2018, Prague
2016/2017: Participation at the Ramsey DocCourse 2016 at DIMATIA, Charles University in Prague and its extension in March 2017.
2017/08: Midsummer Combinatorial Workshop XXII at Charles University, Prague
2015/07: LMS symposium Permutation groups and transformation semigroups, Durham University
2015/07: TACL 2015 Summer School, University of Salerno