1 Postdoc & 2 PhDs in Polynomial-time Computation:, Prague (Czech Republic)

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 Dres den), 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 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 a nd 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. More over, 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 (CSP s), 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.