offering 2 Postdoc and 2 PhD positions at the University of Warsaw. The
goal of the project is to systematically explore the tractability limit of
computational problems related to structural graph theory and logic. The
project is led by Szymon Toruńczyk. The project website is
https://sites.google.com/view/buka-project/ (see below for a description).
We are looking for highly motivated and creative candidates. The applicants
should have a strong background in at least one of the following fields:
structural graph theory, algorithms and complexity, finite model theory, or
model theory.
The starting date of the grant is the 1st of October 2024. We encourage
applicants to express their interest by *June 27nd, 2024 *(see
https://euraxess.ec.europa.eu/jobs/238633 for a job announcement).
The duration of the PhD positions will be 4 years, and the duration of the
Postdoc position will be up to 2 years. The positions come with a very good
salary and carry no teaching load; however, if desired participation in
teaching might be arranged. There is a generous travel budget.
Feel free to contact me for more details: szymtor@mimuw.edu.pl.
–––––––––––––––
Description of BUKA
The area of the project lies at the interface of algorithmic and finite
model theory, structural graph theory, and model theory.
The goal is systematically explore fixed-parameter tractability of the
model checking problem for first-order logic for restricted classes of
graphs.
On the one hand, this topic is closely related to concepts studied in
structural graph theory – such as classes of bounded treewidth,
cliquewidth, twin-width, or nowhere dense classes – and in combinatorics –
such as the Erdős-Hajnal property, χ-boundedness, VC-dimension, regularity.
On the other hand, it is closely related to concepts studied in model
theory – such as monadically stable and NIP theories – and in finite model
theory – such as locality of first-order logic and query enumeration in
database theory. Finally, it is closely related to parameterized complexity
theory and algorithms.
The project will develop the structure theory for the considered graphs or
structures, and will seek efficient algorithms leveraging this structure.
One of the main goals of the project is to characterize those hereditary
graph classes, for which the model checking problem for first-order logic
is fixed-parameter tractable. More information at
https://sites.google.com/view/buka-project/.
**********************************************************
*
* 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
