[Job-offers-cs] PhD and Postdoc positions in theoretical computer science, algebra, and logic (Barto, Bodirsky, Pinsker)

[Pekka Orponen]

The ERC Synergy Grant POCOCOP (Polynomial-time computation: opening the 
black boxes in constraint problems) is offering several postdoc and PhD 
positions at TU Wien and TU Dresden. The goal of the project is to 
systematically explore polynomial-time tractability in the field of 
constraint satisfaction and its extensions, in particular promise CSPs, 
valued CSPs, and CSPs over infinite domains. The project is jointly led 
by three principal investigators: Manuel Bodirsky (TU Dresden), Michael 
Pinsker (TU Vienna), and Libor Barto (Charles University, Prague). The 
project website is https://pococop.eu/>

We are looking for highly motivated and creative candidates and in 
particular encourage female researchers to apply. The applicants should 
have a strong background in at least one of the following fields: 
theoretical computer science, universal algebra, or model theory. For 
the PhD positions the requirements are a Master's degree or equivalent 
in mathematics or computer science. For the Postdoc positions the 
requirements are a PhD or equivalent in mathematics or computer science. 
Successful candidates will be based at TU Wien or TU Dresden, but 
collaborate with the other two groups intensively.

For full consideration, we encourage applicants to express their 
interest by the 31st of December 2025. The duration of the positions 
will be up to 3 years. The positions come with a very good salary, are 
fully funded from the ERC grant and carry no teaching load; however, if 
desired participation in teaching might be arranged. There is sufficient 
funding for conference and research exchange trips.

Applicants should send a motivation letter, CV, a statement of research 
experience and interests, and a list of publications (if applicable) in 
a single PDF file to jobs at pococop.eu. The application may also include a 
short annotation of at most three of their best papers; in the case of 
the PhD positions, a copy of the Master's thesis should be included. 
Applicants should moreover arrange for at least two recommendation 
letters to be sent directly to the same email address. Informal 
inquiries are very welcome.

------------

Abstract of POCOCOP:

The class P of polynomial-time computable computational problems is the 
most important and robust complexity class for the study of efficient 
computation. Answering what problems belong to P will lead to 
groundbreaking applications in science and modern society where 
computation is omnipresent. Moreover, P is a relatively recent 
mathematical object and radically different from classical notions 
studied for centuries; thus, capturing it promises the discovery of new 
fundamental theorems in mathematics.

Our current understanding of P is limited; for instance, the P=NP 
millennium problem is wide open. There neither exists a uniform 
reduction technique, nor a single algorithmic scheme capturing the power 
of P, nor a description of P in purely logical terms. We intend to 
provide these in a context which is so rich and vast that it requires 
the unification of some of the most important techniques, and will 
enhance our general understanding of P.

Within the microcosm of finite-domain constraint satisfaction problems 
(CSPs), the recent resolution of the Feder-Vardi conjecture by Bulatov 
and by Zhuk provides a satisfactory picture of P. Our goal is a vast and 
uniform generalisation of this result in three directions: towards 
approximation via Promise CSPs, towards optimisation via Valued CSPs, 
and towards infinite domains via omega-categorical CSPs and CSPs over 
numeric domains. In particular, our setting includes the linear 
programming problem as a numeric Valued CSP, the approximate graph 
coloring problem as a Promise CSP, and many problems from qualitative 
reasoning as infinite-domain CSPs. Our methods range from universal 
algebra, model theory, Ramsey theory, to complexity theory. Building on 
cross-connections between these extensions, we will provide a uniform 
description of P within this diverse and applicable universe, thus 
making a revolutionary leap in the resolution of the general problem.