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

• For general qualifications, see the CUGS announcement of the PhD student positions.
• 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 and mathematical maturity. A theoretical and/or mathematical background is meritorious.

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 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?

Specifically, these questions will be pursued with the algebraic approach for studying complexity of CSPs. The fine-grained setting is similar to the classical setting but the basic objects are partial polymorphisms rather than total polymorphisms, and a main focus of the research project is to (1) classify relevant properties of partial operations which are sufficient to yield improved algorithms, (2) develop a theory of algebras of partial operations in the context of strong Maltsev conditions. Which techniques from the total setting can be adapted to the partial case?

For additional information regarding the position, or the project, contact Victor Lagerkvist. The co-supervisor for the PhD student in this project will be Peter Jonsson (peter.jonsson@liu.se).

Page responsible: Victor Lagerkvist
Last updated: 2023-11-15