Publications from our group

2024

• Smooth approximations : an algebraic approach to CSPs over finitely bounded homogeneous structures
  Mottet, Antoine; Pinsker, Michael
  Journal of the ACM 71 (5): 36 (2024-10-05)
  Publisher DOI
• Generalized completion problems with forbidden tournaments
  Bitter, Zeno; Mottet, Antoine
  49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
  Open Access | Publisher DOI
• An order out of nowhere : a new algorithm for infinite-domain CSPs
  Mottet, Antoine; Nagy, Tomáš; Pinsker, Michael
  Leibniz International Proceedings in Informatics, LIPIcs 297: 148 (2024)
  Open Access | Publisher DOI
• Comlexity classification transfer for CSPs via algebraic products
  Bodirsky, Manuel; Jonsson, Peter; Martin, Barnaby; Wiehe, Antoine; Semanisinova, Zaneta
  SIAM Journal on Computing 53 (3): 1293-1353 (2024)
  Publisher DOI
• Promise and infinite-domain constraint satisfaction
  Mottet, Antoine
  32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). - Wadern, 2024. - (Leibniz International Proceedings in Informatics, LIPIcs ; 288): - Art. 41
  Publisher DOI

2023

• Symmetries of graphs and structures that fail to interpret a finite thing
  Barto, Libor; Bodor, Bertalan; Kozik, Marcin; Mottet, Antoine; Pinsker, Michael
  Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2023)
  Publisher DOI

2022

• Smooth approximations and CSPs over finitely bounded homogeneous structures
  Mottet, Antoine; Pinsker, Michael
  37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022)
  Publisher DOI
• When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems
  Gillibert, Pierre; Jonušas, Julius; Kompatscher, Michael; Mottet, Antoine; Pinsker, Michael
  SIAM Journal on Computing 51 (2): 175-213 (2022)
  Publisher DOI

2021

• New techniques for universality in unambiguous register automata
  Czerwiński, Wojciech; Mottet, Antoine; Quaas, Karin
  48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
  Publisher DOI
• Smooth approximations and relational width collapses
  Mottet, Antoine; Nagy, Tomáš; Pinsker, Michael; Wrona, Michał
  48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 198: 138 (2021)
  Publisher DOI
• Constraint Satisfaction Problems over Finite Structures
  Barto, Libor; Demeo, William; Mottet, Antoine
  36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021)
  Publisher DOI
• The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata
  Mottet, Antoine; Quaas, Karin
  Theory of Computing Systems 65 (4): 706-735 (2021-05)
  Publisher DOI
• CORES over RAMSEY STRUCTURES
  Mottet, Antoine; Pinsker, Michael
  Journal of Symbolic Logic 86 (1): 352-361 (2021-03)
  Publisher DOI
• ω-categorical structures avoiding height 1 identities
  Bodirsky, Manuel; Mottet, Antoine; Olšák, Miroslav; Opršal, Jakub; Pinsker, Michael; Willard, Ross
  Transactions of the American Mathematical Society 374 (1): 327-350 (2021-01)
  Publisher DOI
• A proof of the algebraic tractability conjecture for monotone monadic SNP
  Bodirsky, Manuel; Madelaine, Florent; Mottet, Antoine
  SIAM Journal on Computing 50 (4) : (2021)
  Publisher DOI

2020

• Hrushovski's encoding and ω-categorical CSP monsters
  Gillibert, Pierre; Jonušas, Julius; Kompatscher, Michael; Mottet, Antoine; Pinsker, Michael
  47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) 168: 131 (2021)
  Publisher DOI
• Extensions of unificationmodulo ACUI
  Baader, Franz; Marantidis, Pavlos; Mottet, Antoine; Okhotin, Alexander
  Mathematical Structures in Computer Science 30 (6): 597-626 (2020-06-01)
  Publisher DOI

2019

• Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
  Bodirsky, Manuel; Mottet, Antoine; Olšák, Miroslav; Opršal, Jakub; Pinsker, Michael; Willard, Ross
  Symposium on Logic in Computer Science (2019)
  Publisher DOI
• The containment problem for unambiguous register automata
  Mottet, Antoine; Quaas, Karin
  36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) 126: 53 (2019)
  Publisher DOI

2018

• The complexity of disjunctive linear diophantine constraints
  Bodirsky, Manuel; Martin, Barnaby; Mamino, Marcello; Mottet, Antoine
  43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) 117: 33 (2018)
  Publisher DOI
• A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
  Bodirsky, Manuel; Madelaine, Florent; Mottet, Antoine
  33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2018)
  Publisher DOI
• Classification transfer for qualitative reasoning problems
  Bodirsky, Manuel; Jonsson, Peter; Martin, Barnaby; Mottet, Antoine
  27th International Joint Conference on Artificial Intelligence (IJCAI 2018)
  Publisher DOI
• A dichotomy for first-order reducts of unary structures
  Bodirsky, Manuel; Mottet, Antoine
  Logical Methods in Computer Science 14 (2) : 13 (2018-05-22)
  Publisher DOI
• Discrete temporal constraint satisfaction problems
  Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine
  Journal of the ACM 65 (2): 9 (2018-02)
  Publisher DOI

2016

• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
  Bodirsky, Manuel; Mottet, Antoine
  31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016)
  Publisher DOI
• Distance constraint satisfaction problems
  Bodirsky, Manuel; Dalmau, Victor; Martin, Barnaby; Mottet, Antoine; Pinsker, Michael
  Information and Computation 247 : 87-105 (2016-04-01)
  Publisher DOI

2015

• Constraint satisfaction problems over the integers with successor
  Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine
  42nd International Colloquium on Automata, Languages and Programming (ICALP 2015)
  Publisher DOI