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.
Quantum constraint satisfaction
The Mermin square is a famous example of a game that can be won with the use of quantum resources, but that cannot be won classically.
Quantum constraint satisfaction studies constraint satisfaction problems through the lens of games: a classical instance can be viewed as a homomorphism game, in which cooperating players try to demonstrate that one mathematical structure maps to another while answering consistently without communication. In the quantum version of this game, the players may share entanglement and use quantum measurements to coordinate their answers. This opens the door to quantum advantage: situations where quantum resources allow a perfect winning strategy even though no classical strategy exists. These phenomena connect logic, combinatorics, operator algebras, and theoretical computer science. At our institute, we investigate when such quantum advantages arise and how they can be characterized mathematically. We also study the computational complexity of deciding who wins these nonlocal games, a problem that reveals deep links between constraint satisfaction, quantum information, and the limits of algorithmic reasoning.
Approximation and Constraint Satisfaction with Promises
Given a directed graph that has a directed 2-layering of large value, it is possible to find a large acyclic subgraph containing at least as many edges.
Many computational problems are too hard to solve exactly in full generality, so a central goal is to design algorithms that find solutions which are still provably good. Promise constraint satisfaction studies this idea under additional assumptions: rather than asking for a perfect solution, we ask what can be efficiently achieved when the input is promised to have some strong hidden structure. For example, consider a directed network whose vertices are divided into k layers, and count the edges that point forward from an earlier layer to a later one. Finding the layering that maximizes this number is computationally hard for every k. But what if we are promised that a very good k-layering exists, and only want to find a large acyclic part of the network? This question has a surprisingly delicate answer: it is efficiently solvable for k=2, known to be hard for k ≥ 4, and the case k=3 remains open. At our institute, we study such approximation problems using the framework of promise constraint satisfaction, aiming to understand precisely when useful approximate solutions can be found efficiently.
Coloring problems and infinite-domain constraint satisfaction
An example of an edge-coloring of a graph that avoids monochromatic triangles. The problem of finding such a coloring is considered computationally intractable (even on a quantum computer).
How hard is it to color a network while avoiding certain “bad” local configurations? A famous example is 3-coloring: given a network, can we color each node with one of three colors so that no edge connects two nodes of the same color? Despite its simple formulation, this problem is computationally difficult, and it appears in practical settings such as assigning variables to CPU registers in compilers or choosing frequencies for communication channels without interference.
More broadly, we study coloring problems for vertices or edges in which a fixed list of forbidden patterns is specified in advance, and the task is to decide whether a given network can be colored while avoiding all of them. This viewpoint captures many central constraint satisfaction problems, including Boolean satisfiability and graph colorability. At our institute, we use methods from algebra, logic, and model theory to understand the boundary between problems that admit efficient algorithms and those that are inherently hard.
