Forschungsbericht 2024

Theoretische Informatik E-EXK6

Leitung: Mottet, Antoine
Gründungsdatum: 1.3.2022

Institut auf TORE
Institutswebsite

The research group for Theoretical Computer Science is dedicated to the investigation of questions related to the nature of computation and its complexity. The main focus points are constraint satisfaction problems, complexity theory, and algebraic and logical methods used for their study.

Publikationen

• Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough - Journal Article
  Mottet, Antoine; Nagy, Tomáš; Pinsker, Michael; Wrona, Michał
  SIAM Journal on Computing 53 (6): 1709-1745 (2024)
  Publisher DOI
  
  
• Finite algebras with hom-sets of polynomal size - Journal Article
  Barto, Libor; Mottet, Antoine
  Transactions of the American Mathematical Society 378 (1): 569-596 (2025)
  Publisher DOI
  
  
• Smooth approximations : an algebraic approach to CSPs over finitely bounded homogeneous structures - Journal Article
  Mottet, Antoine; Pinsker, Michael
  Journal of the ACM 71 (5): 36 (2024)
  Publisher DOI
  
  
• Generalized completion problems with forbidden tournaments - Conference Paper
  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 - Conference Paper
  Mottet, Antoine; Nagy, Tomáš; Pinsker, Michael
  51st EATCS International Colloquium on Automata, Languages and Programming, ICALP 2024
  Open Access | Publisher DOI
  
  
• Complexity classification transfer for CSPs via algebraic products - Journal Article
  Bodirsky, Manuel; Jonsson, Peter; Martin, Barnaby; Mottet, Antoine; Semanisinova, Zaneta
  SIAM Journal on Computing 53 (3): 1293-1353 (2024)
  Publisher DOI
  
  
• Promise and infinite-domain constraint satisfaction - Conference Paper
  Mottet, Antoine
  32nd EACSL Annual Conference on Computer Science Logic, CSL 2024
  Publisher DOI
  
  

Projekte

• Glatte Approximationen und Bedingungserfüllung
  Deutsche Forschungsgemeinschaft (DFG); Laufzeit 2024-2027
  Projektleitung: Mottet, Antoine