Linköping University advertises up to two (2) positions as PhD student in Computer Science, formally based at the Department of Computer and Information Science (IDA), within WASP.

Project Description

Constraint Satisfaction Problems (CSP) are a well-known and important class of computational problems with a wide range of applications within computer science, artificial intelligence, and mathematics. An instance of the constraint satisfaction problem consists of a set of variables, a set of possible variable values (known as the domain), and a set of constraints which impose restrictions on value assignments to the variables. To solve such a problem, a value has to be found for each variable so that all the constraints are satisfied. The computational complexity of CSP problems has been intensively studied during the last decades, and several breakthrough results have recently been presented for the finite-domain case. These results are to a large extent based on utilising methods from universal algebra and mathematical logic. This project aims at developing new mathematical methods for analysing the computational complexity of infinite-domain CSP problems—such problems have very interesting applications within computer science and AI (such as spatiotemporal reasoning, machine learning, scheduling, and bioinformatics). The project aim at constructing new algorithms with significantly better complexity than current algorithms. The work within this project includes the construction of new algorithms, analysing their complexity, and identifiying general methods for the algorithm construction and analysis.

This call is part of a joint call for doctoral students in Math/AI. It is done in several steps, where finding doctoral students is the second step. The first step, the project call, can be found here:

More Information and Application

View all positions