Recent trends in kernelization: theory and experimental evaluation

Foundation for Polish Science grant under Homing programme

About the project

The project mainly focuses on experimental evaluation of the recent theoretical developments in kernelization - a rigorous framework to analyse preprocessing routines. The experiments will be conducted in three main directions:

Furthermore, the project includes theoretical research of selected aspects of Turing kernelization.

It is likely that a nonempty subset of the researchers involved in the project will participate in one of the next editions of Parameterized Algorithms and Computational Experiments Challenge.

The project is conducted with three international partners:

The project is funded in 100% from the European Union through the European Regional Development Fund, up to the amount of 597 866 PLN.


The project offers three positions for master students for the period March 2017 - September 2018. Two of the positions come with a monthly stipend of 2500 PLN, while the third position is a full-time employment at the University of Warsaw with ca. 2400 PLN net monthly salary (4000 PLN full renumeration costs, including all employer's costs).

A successful applicant is expected to conduct experiments on fixed-parameter and kernelization algorithm under the supervision of the PI, and to publish the results of the experiments in the form of scientific publications, technical reports, and - last but not least - in his/her master thesis. Involvement in theoretical research is also possible.

Participating in the project gets you in touch with the state-of-the-art research in parameterized complexity, a rapidly developing subarea of theoretical computer science. The group at University of Warsaw is one of the leading research groups in parameterized complexity.

We expect from an applicant a strong background in discrete mathematics and algorithm design and strong programming skills. Previous participation in mathematical or programming contests (e.g., Topcoder, ACM ICPC, Codeforces) is a strong advantage.

The positions are not restricted to students of University of Warsaw. On the contrary, we welcome students from other Polish universities as well as from abroad. However, please note that a successful applicant is expected to meet with the PI in person on a regular basis (at least once every two-three weeks).

The positions are primarily meant for students undertaking their M.Sc. programme this year (i.e., with expected graduation in September 2018), but exceptionally talented students from other years (e.g., one year junior or senior) are also welcome to apply. However, in such a case the employment/stipend period may be altered.


To apply for positions, please send to the PI by email (malcin at mimuw edu pl) the following documents by 20th November 2016:

  1. Cover letter.
    • Please specify whether you prefer a stipend or full-time employment.
    • Please include in your cover letter the following statement: "I hereby give consent for my personal data included in my application to be processed for the purposes of the recruitment process under the Personal Data Protection Act as of 29 August 1997, consolidated text: Journal of Laws 2016, item 922 as amended."
  2. CV of at most 3 pages. While we do not impose any particular format, you may want to include some of the following:
    • Participation in mathematical or programming competitions (including, e.g., a link to a TopCoder or Codeforces profile).
    • Participation in projects (e.g., a link to a github project).
  3. A transcript of grades.
  4. Two references (people that we can ask for recommendation letters if needed).

We will invite selected applicants to an interview that will take part on Thursday, 8th December, starting from 2pm. In exceptional circumstances, the interview can be conducted as a video conference.


Contact Marcin Pilipczuk (the PI) via email: malcin at mimuw edu pl.