Research group on Theoretical Computer Science

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.

03.11.2023

Extended abstract to be presented at CSL 2024

A new paper with the title "Promise and Infinite-Domain Constraint Satisfaction" by Mottet has been accepted for publication in the proceedings of the international conference Computer Science Logic (CSL) and will be presented this February in Napoli.

In the paper, a method to build a bridge between two prominent fields of constraint satisfaction is exhibited. This bridge is used to answer some questions in the theory of Promise Constraint Satisfaction Problems (PCSPs) by means of methods coming from the study of infinite-domain constraint satisfaction problems (∞CSPs).