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.
I am the principal investigator of the Primus project PRIMUS/24/SCI/008 The subpower membership problem for algebras with cube term. Currently it employs Stefano Fioravanti, Bernardo Rossi and Albert Vucaj.
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 (project PowAlgDO of Standa Živný) and at Charles University (projects CoCoSym by Libor Barto and PRIMUS/SCI/12 of Alex Kazda).
(I am NOT conducting tests in a tunnel in Switzerland, or promoting wafers.)
News / upcoming events
- 10.09-13.09: Partecipation at the Algebra Week, Siena
- 22.09-28.09: Mal'tsev terms and compact representations, Tutorial at the 6th CSP World Congress, Kolfuschg - [slides], [slides2]
Teaching
In winter semester 2024/25 I am teaching:- Convex optimization:
The practicals are run by Alexey Barsukov. - Together with Zuzka Patáková I am organizing the weekly Algebra Colloquium.
For information about past teaching see here.
Publications
Preprints
-
Every finite nilpotent loop has a supernilpotent loop as reduct. [arXiv]
with Peter Mayr
preprint, 19 pages. -
CSAT and CEQV for nilpotent algebras of Fitting length > 2. [arXiv]
preprint, 20 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ﬡ0 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
-
The subpower membership problem of 2-nilpotent algebras. [doi] [arXiv]
Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), p46:1--46:17. -
Circuit equivalence in 2-nilpotent algebras. [doi] [arXiv]
with Piotr Kawałek, Jacek Krzaczkowski
Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), p45:1--45:17. -
Short definitions in constraint languages. [doi] [arXiv]
with Jakub Bulín
Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), p28:1--28:15. -
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
| 2024/04 | Interpolation over finite algebraic structures at the Algebra Colloquium | |
| 2024/04 | Interpolation over finite algebraic structures at the Set Theory and Analysis Seminar of CAS | |
| 2024/03 | The subpower membership problem of 2-nilpotent algebras. at STACS 2024, Clermont-Ferrand, France - [slides] | |
| 2024/02 | Difference clonoids and their applications at AAA104 in Blagoevgrad, Bulgaria - [slides] | |
| 2023/11 | ! Short pp-definitions in the Projektseminar für FWF P33878: Gleichungen in der universellen Algebra. (blackboard talk) |
|
| 2023/09 | Short pp-definitions at CWC2023 at Weissensee, Austria - [slides] | |
| 2023/08 | Short definitions in constraint languages at MFCS23, Bordeaux, France - [slides] | |
| 2023/07 | Algebras with short pp-definitions at TCA2023, Pocinho, Portugal - [slides] | |
| 2023/06 | Short pp-definitions for algebras with few subpowers at AAA93, Tartu, Estonia - [slides] | |
| 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
- 2024/05: I was the main organisers of AAA105 (105. Arbeitstagung Allgemeine Algebra) at Charles University from 31.05.-02.06.24
- 2024/05: Škola v přírodě of our department, talk coordination.
- 2023/12: Škola v přírodě of our department, talk coordination.
- 2023/03: Škola v přírodě of our department, 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