[Job-offers-cs] CfA: 1 Postdoc & 2 PhDs in a ERC Project POCOCOP (Polynomial-time computation: opening the black boxes in constraint problems) , Charles University (Prague, Czech Republic), deadline: 15 December 2023

[Pekka Orponen]

The ERC Synergy Grant POCOCOP (Polynomial-time computation: opening the 
black boxes in constraint problems) is offering 1 Postdoc and 2 PhD 
positions at Charles University, Prague.
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 ishttps://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 position the 
requirements are a PhD or equivalent in mathematics or computer science. 
Successful candidates will be based at Prague, but collaborate with the 
other two groups intensively.

For full consideration, we encourage applicants to express their 
interest by the 15th of December 2023. The duration of the PhD positions 
will be 4 years, and the duration of the Postdoc position 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 tojobs 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.