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@pococop.eu (mailto:jobs@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.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
