Apologies for the spam – the previous email contained an incorrect link. Below is the correct one.

Best wishes, Szymon –––––––––––––––––––––––

Dear colleague,

Please find below a job announcement for the ERC Consolidator Grant BUKA. I would be grateful if you could forward it to anyone interested.

With best wishes for the holidays, and a happy new year,

Szymon Toruńczyk

––––––––––––––––––––––––––

The ERC Consolidator Grant BUKA (Limits of Structural Tractability) is 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 logic and structural graph theory. 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, but applications will be considered until the positions are filled. For full consideration, we encourage applicants to express their interest by May 31st, 2024.

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. See https://sites.google.com/view/buka-project/ for more details.