PhD Student in Theoretical Computer Science

In the project Fine-Grained Complexity of Satisfiability and Constraint Satisfaction Problems

Linköping University invites applications for a fully-funded position as a PhD student in the laboratory of theoretical computer science, TCSLAB.

Qualifications

• Master’s degree in computer science, mathematics, or a related field.
• Ability to independently define, motivate, and plan research projects, as evidenced in e.g. your master’s thesis.
• Fluency in spoken and written English.
• Strong problem solving skills, especially in the construction and analysis of algorithms.

Thesis project

Your thesis project will be in the area of theoretical computer science, with a special focus on the fine-grained complexity of constraint satisfaction problems (CSPs). Here, the idea is to study the complexity of intractable (typically NP-complete) CSPs under a more fine-grained lense than ordinary polynomial-time reductions. For example, if a given CSP is NP-complete, then it is unlikely to be solvable in polynomial time, but how fast can be be solved by a superpolynomial algorithm? Is it possible to construct mathematical methods which allows us to say whether a certain algorithmic scheme is applicable? As the ultimate goal, can one characterize all CSPs solvable faster than exhaustive search?

The project encompasses both finite-domain CSPS (generalising Boolean satisfiability problems and colouring problems) and infinite-domain CSPs (generalising e.g. temporal CSPs and reasoning problems such as the region connection calculus and Allen's interval algebra). For these problems we are interested not only in finding improved algorithms, but also to prove lower bounds under stronger complexity theoretical assumptions than P != NP.

For additional information regarding the position, or the project, contact Victor Lagerkvist.

Page responsible: Victor Lagerkvist
Last updated: 2020-09-01