Address:
Department of Computer Science, University of Oxford
Wolfson Building
15 Parks Road
Oxford OX1 3QD
UK
Room: 322, 3rd floor
Email: michael@logic.at, michael.kompatscher@cs.ox.ac.uk
ResearchGate: Michael Kompatscher
OrcID: 0000000201636604
Since October 2020 I am a postdoctoral researcher at the Department of Computer Science of the University of Oxford. My research interests include universal algebra, model theory, Ramsey theory and their application in theoretical computer science.
I'm employed in ERC grant Power of Algorithms in Discrete Optimisation lead by Standa Živný
I finished my PhD in 2017 at TU Wien under the supervision of Michael Pinsker, for my academic family tree, see here.
For information about my teaching in past semesters, click here.
CCcircuits and the expressive power of nilpotent algebras. [arXiv]
submitted, 11 pages.
Circuit equivalence in 2nilpotent algebras.
with Piotr Kawałek, Jacek Krzaczkowski
in preparation.
When symmetries are not enough: A hierarchy of hard constraint satisfaction problems. [arXiv]
with Pierre Gillibert, Julius Jonušas, Antoine Mottet, Michael Pinsker
preprint, 31 pages.
Some notes on extended equation solvability and identity checking for groups. [pdf] [arXiv]
in Acta Mathematica Hungarica, 159(1) 246256, Oct 2019.
Forbidden cycles in metrically homogeneous graphs. [arXiv]
with Jan Hubička, Matěj Konečný
submitted, 24 pages.
The equation solvability problem over supernilpotent algebras with Mal’cev term. [arXiv]
International Journal of Algebra and Computation, 28(6) 1005–1015, 2018.
Ramsey expansions of metrically homogeneous graphs. [arXiv]
with Andrés Aranda, David BradleyWilliams, Jan Hubička, Miltiadis Karamanlis, Matěj Konečný, Micheal Pawliuk
submitted, 57 pages.
Completing graphs to metric spaces. [arXiv]
with Andrés Aranda, David BradleyWilliams, Eng Keat Hng, Jan Hubička, Miltiadis Karamanlis, Matěj Konečný, Micheal Pawliuk
submitted, 19 pages.
Equations in oligomorphic clones and the constraint satisfaction problem for ⍵categorical structures. [arXiv]
with Libor Barto, Mirek Olšák, Michael Pinsker and Trung Van Pham
Journal of Mathematical Logic, 19(2), #1950010, 2019.
A complexity dichotomy for poset constraint satisfaction. [arXiv]
with Trung Van Pham
Journal of Applied Logic, 5(8) 16631696, 2018.
2^{ﬡ0} pairwise nonisomorphic maximalclosed subgroups of Sym(N) via the classification of the reducts of the Henson digraphs. [arXiv]
with Lovkush Agarwal
Journal of Symbolic Logic, 83(2), 395415, 2018.
A counterexample to the reconstruction of ⍵categorical structures from their endomorphism monoids. [arXiv]
with Manuel Bodirsky, David Evans, and Michael Pinsker
Israel Journal of Mathematics, 224(1), 5782, 2018.
Hrushovski's encoding and omegacategorical CSP monsters.
with Pierre Gillibert, Julius Jonušas, Antoine Mottet, Michael Pinsker
Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP 2020), accepted.
Completing graphs to metric spaces.
with Andrés Aranda, David BradleyWilliams, Eng Keat Hng, Jan Hubička, Miltiadis Karamanlis, Matěj Konečný, Micheal Pawliuk
Special Issue of EUROCOMB'17, Electronic Notes in Discrete Mathematics, Volume 61, August 2017, Pages 5360.
The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems. [pdf]
with Libor Barto, Mirek Olšák, Michael Pinsker and Trung Van Pham
Proceedings of the 32nd Symposium on Logic in Computer Science (LICS) 2017, 112.
A complexity dichotomy for poset constraint satisfaction. [pdf]
with Trung Van Pham
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS) 2017, p47:1–47:12
Clones and homogeneous structures. [pdf]
PhD thesis, 2017, supervised by Michael Pinsker.
Gegenbeispiele zu drei Vermutungen über Kategorizität. [pdf]
Master thesis, 2014, supervised by Martin Goldstern.
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  CCCircuits and the expressive power of nilpotent algebras, Invited talk at AAA99, Siena  [slides]  
2020/01  CCCircuits and the expressive power of nilpotent algebras, Birkhoff Seminar, CU Boulder  [slides]  
2020/01  Topology is relevant (in discussing the complexity of omegacategorical 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  CCcircuits 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 – LeibnizZentrum 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 nontrivial equations in oligomorphic clones at AAA94+NSAC2017, University of Novi Sad  [slides] 

2017/05  Completing edgelabelled graphs to metric spaces  AGDM Seminar, Wien  [slides]  
2017/05  Cores of omegacategorical 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 PosetSAT in the Algebra Seminar of TU Wien  [slides]  
2016/02  2^{⍵} many maximalclosed 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, CharlesUniversity 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, CharlesUniversity 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 