Constraint Satisfaction Problems:
beyond the finite case

a Ph.D. study opportunity at Jagiellonian University in Kraków

The research area of the dissertation

Project's aim is to investigate computational complexity of Constraint Satisfaction Problems, with a focus on problems defined by templates over infinite domains.

Research in the area uses tools from computational complexity, universal algebra, model theory, Ramsey theory, and a variety of recent algorithmic and hardness results. We investigate algebraic and combinatorial structure of (often infinite) templates and devise algorithms (or hardness proofs) based on the identified structural properties.

The prospective candidate needs:
  • a strong motivation for research,
  • a Master's degree in computer science, mathematics, or physics, with the thesis defended by the end of September 2022 (this requirement can be removed for candidates with exceptionally strong research record)
  • a background in computational complexity, combinatorics, or universal algebra is a plus but is not necessary.
The conditions of the study:
  • A PhD programme is a 4 year long and the stipend is awarded for the whole duration of study.
  • The total net value of the stipend is about 7300 PLN/month (~ 1600 EUR/month) during the first two years (over 300% of a standard stipend at Doctoral School of Exact and Natural Sciences of Jagiellonian University).
  • The stipend is further increased after the first two years.
  • The project covers travel costs related to the research.
Additional details:
  • The stipend consists of 2300 PLN/month standard stipend of Doctoral School of Exact and Natural Sciences and a 5000 PLN/month stipend funded by the project.
  • The application procedure is a two-step process.
  • If you are interested in applying contact marcin.kozik@uj.edu.pl for further information.