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

[Pekka Orponen]

-------- Forwarded Message --------

Subject: 	[DMANET] 9 PhD positions and 6 Postdoc positions in 
theoretical computer science, algebra, and logic (Barto, Bodirsky, 
Pinsker)​
Date: 	Wed, 23 Nov 2022 13:45:53 +0000
From: 	ERC SyG POCOCOP <jobs at pococop.eu>
To: 	dmanet at zpr.uni-koeln.de



Dear colleague,

Please find below a job announcement of our ERC Synergy Grant POCOCOP. 
We would be grateful if you could forward it to anyone interested.

Best wishes,

Michael Pinsker, Libor Barto, Manuel Bodirsky
The ERC Synergy Grant POCOCOP (Polynomial-time computation: opening the 
black boxes in constraint problems) is offering 9 PhD and 6 Postdoc 
positions at TU Vienna, Charles University Prague, 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).

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, model theory, or universal algebra. 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 one of the three sites (Prague, 
Dresden, Vienna), but collaborate with the other two groups intensively.

The starting date of the grant is the 1st of March 2023, but 
applications will be considered until the positions are filled. For full 
consideration, we encourage applicants to express their interest by the 
15th of December 2022. The duration of the PhD positions will be 3-4 
years, and the duration of the Postdoc 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 via other sources of funding. There is 
sufficient funding for conference and research exchange trips.

Applicants should send a 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 (mailto: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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://list.aalto.fi/pipermail/job-offers-cs/attachments/20221126/66875ddb/attachment-0001.htm