Postdoctoral Research Associate

The Role

Applications are invited for a Postdoctoral Research Associate in Computer Science with a particular emphasis on Mathematical and Complexity-theoretic aspects of Constraint Satisfaction Problems (CSPs). The research project is the EPSRC-funded “Promise Constraint Satisfaction Problems: Structure and Complexity”, led by Professor Andrei Krokhin. The aim of the project is to understand the mathematical structure of Promise CSPs that makes them easy or hard from the algorithmic point of view. This project is particularly suitable for researchers in mathematics and theoretical computer science looking to expand their expertise into a new exciting area of much international interest.

The CSPs are very general combinatorial problems that can be expressed in many different ways: for example, via logic (e.g. logical satisfiability problems), combinatorics (e.g. graph homomorphisms), or algebra (e.g. systems of equations over a field). Such problems can have different computational complexity (e.g. polynomial-time solvable or NP-hard), and the question how exactly the inherent mathematical structure of problems affects the complexity is the essence of the project. There are many mathematical approaches that can be used in this research -- recent examples include universal algebra, logic and model theory, combinatorics and graph theory, algebraic topology and topological combinatorics, combinatorial optimisation, category theory, matrix analysis, and Boolean function analysis. The successful applicant will use their own mathematical backgro! und, poss ibly in combination with some of the existing approaches, to assist the project team in developing a new mathematical theory of Promise CSPs, a recently proposed generalisation of the standard CSPs.

This post is fixed term for 36 months, as funding is available for this period only.