Ph. D. Student

Universities and Institutes of Poland


September 23, 2022


  • Organisation/Company: Jagiellonian University
  • Research Field: Computer science › Other
  • Researcher Profile: First Stage Researcher (R1)
  • Application Deadline: 23/09/2022 23:00 - Europe/Athens
  • Location: Poland › Kraków
  • The research area of the dissertation

    We employ algebraic tools to investigate the computational complexity of certain problems. More precisely, the research is focused on Promise Constraint Satisfaction Problem (PCSP) on a Boolean domain.

    An example of a Promise CSP is the approximate coloring problem: deciding whether the chromatic number of a graph is at most 3 or at least 17. The doctoral research aims to investigate the computational complexity of such problems, but defined on a Boolean domain.

    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,
  • a background in computational complexity, combinatorics, or universal algebra is a plus but is not necessary.
  • For further information see website.

    Contact Information
  • Organisation/Company: Jagiellonian University
  • Department: Faculty of Mathematics and Computer Science
  • Organisation Type: Higher Education Institute
  • Website: https:// www.
  • E-Mail:
  • Country: Poland
  • City: Kraków
  • Postal Code: 30-348
  • Street: ul. Łojasiewicza 6