1 postdoctoral position in the scientific project “BOBR: Decomposition methods for discrete problems” financed by the European Commission (grant agreement no 948057)

12 Sep 2023
Job Information

Organisation/Company

University of Warsaw: Faculty of Mathematics, Informatics and Mechanics

Research Field

Computer science » Other

Researcher Profile

Recognised Researcher (R2)

Country

Poland

Application Deadline

13 Oct 2023 - 23:59 (Europe/Warsaw)

Type of Contract

Temporary

Job Status

Full-time

Hours Per Week

36

Offer Starting Date

1 Nov 2023

Is the job funded through the EU Research Framework Programme?

H2020 / ERC

Reference Number

SOB/D110/2023/1/PA/60-0936216

Is the Job related to staff position within a Research Infrastructure?

No

Offer Description

1 postdoctoral position in the scientific project
“BOBR: Decomposition methods for discrete problems”
financed by the European Commission (grant agreement no 948057)
Principal Investigator: Michał Pilipczuk

The ERC project „BOBR: Decomposition methods for discrete problems”, led by dr hab. Michał
Pilipczuk, is offering one postdoctoral position in the Institute of Informatics at the Faculty of
Mathematics, Informatics and Mechanics of the University of Warsaw.

Terms of employment
Selected candidate will be employed as full-time researcher (pol. adiunkt). The duration of
employment is for one year, with possible extension for another 12 months. The starting date can be
set between 1st of November 2023 and 1st of March 2024, up to an agreement between the candidate
and the principal investigator. The offered salary combined (basic salary approx. 7 500 PLN
gross/month plus project bonus) is around 10 000 PLN per month pre-tax (around 2 225 EUR), which
is more than enough for a comfortable life in Warsaw. The position comes with no teaching
obligations and travel budget. Selected candidate will work on problems in the intersection of the
fields of structural graph theory, algorithm design and logic in computer science.
 

Description of the project
Project BOBR focuses on studying graph decompositions and their applications in designing efficient
algorithms, in particular for graph problems and problems originating from finite model theory. The
work within the project will concentrate on the following four directions:
 Beyond Sparsity. We will study the abstract notions of sparsity in graphs (bounded expansion
and nowhere denseness) in order to understand the structure implied by these notions and to
use this structure for designing efficient algorithms. We will also try to build a theory of wellstructured
dense graphs, based on advances in the theory of sparse graphs and inspired by the
theory of stability.
 Dynamic parameterized data structures. We will use the idea of parameterization to perform a
systematic exploration of data structures for dynamic parameterized problems in graphs.
 Algorithms in planar graphs. We will design new parameterized and approximation algorithms
for problems in planar graphs, while focusing on combining techniques from both these areas.
 Algorithms in hereditary classes of graphs: We will study structural properties in classes of
graphs defined by forbidding induced subgraphs, in order to design efficient parameterized,
approximation, and exact algorithms working on graphs from such classes.

Requirements
We expect that candidate at the moment of employment holds a PhD degree in either mathematics or
computer science and has an excellent background in both of these disciplines, in particular in one or
more of the following fields:
 structural graph theory;
 algorithm design;
 automata and logic.
Research experience in any of the following areas will be an advantage:
 parameterized algorithms;
 approximation schemes in planar graphs;
 algorithms on graph classes;
 dynamic data structures;
 model-checking algorithms;
 graph minors theory;
 model theory, in particular finite model theory or stability theory;
 structural theory of sparse graphs (notions of bounded expansion and nowhere denseness);
 decompositions of graphs, in particular treewidth and cliquewidth.

The competition may be entered by candidates who meet the conditions set out in art. 113 of the Law
on Higher Education and Science of July 20, 2018 (Journal of Laws of 2023, item 742, as amended).
 

Applications

An application should include Curriculum Vitae that:
 presents an overview of the background and scientific achievements of the candidate;
 lists all the candidate’s research works (including not yet published manuscripts);
 gives a list of three experienced researchers that may serve as references for the candidate.
In addition, there should be a signed cover letter addressed to the Dean of the Faculty of
Mathematics, Informatics and Mechanics, University of Warsaw together with the personal data
clause (attached).
No research statements are required.
On the day of submitting the application, the candidate does not have to hold a PhD degree.
Applications, as well as further questions on both the scientific topic of the project and formal details
of the call procedure should be directed to dr hab. Michał Pilipczuk:
michal.pilipczuk@mimuw.edu.pl
In order to apply for the position, candidates should send an e-mail and submit the documents as
attached .pdf files.
 

Application deadline: 13 October 2023

Applications which do not satisfy the above requirements or are submitted after the deadline will not
be considered for the position.
The applications will be evaluated by a selection committee appointed by the Dean of the Faculty of
Mathematics, Informatics and Mechanics, University of Warsaw. The committee may invite candidate
to a meeting, which will be conducted remotely. The results of the competition will be sent to
candidates electronically on 23 October 2023 at the latest. The competition is the first stage of the
recruitment process as described in the Statute of the University of Warsaw, the recommendation by
the selection committee being a basis for its subsequent stages.

Requirements

Research Field

Computer science » Other

Education Level

PhD or equivalent

Languages

ENGLISH

Level

Good

Internal Application form(s) needed
bobr-postdoc-0823_eng.pdf
English
(140.56 KB - PDF)
Download
Additional Information
Work Location(s)

Number of offers available

1

Company/Institute

Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw

Country

Poland

Geofield

Where to apply

E-mail

michal.pilipczuk@mimuw.edu.pl

Contact

State/Province

Mazovia Province

City

Warsaw

Website

http://www.mimuw.edu.pl

Street

Krakowskie Przedmieście 26/28

Postal Code

02-097

STATUS: EXPIRED