A two-year full-time postdoc position is expected to be available (subject to approval of the support) in the G²OAT research group at the Czech Technical University in Prague (CTU), Czech Republic, with starting date January 2022. The prospective mentor of the position is Dr. Ondřej Suchý.
The work of the candidate should be related to Parameterized and Exact Algorithms. Parameterized or multivariate analysis became in the last two decades a standard approach for (NP-) hard computational problems. Here, in contrast to classical complexity, the efficiency of algorithms is not measured only with respect to the length of the input instance, but also with respect to a specified parameter. The outcome is a more fine grained complexity landscape which allows for a better prediction of the complexity of particular instances encountered. The goal is to design algorithms with running time that is polynomial in the input size and exponential only in the designated parameter. Fundamentally, the degree of the polynomial is required to be independent of the value of the parameter. Parameterized complexity provides a mathematical framework to analyze these algorithms and also to show that for some problems and parameters there is (probably) no such algorithm.
The research interests of the group range from graph algorithms, through classical and parameterized complexity and integer linear programming to combinatorial games. The research group Graphs, Games, Optimization, Algorithms and Theoretical Computer Science (G²OAT) is a part of the Department of Theoretical Computer Science at the Faculty of Information Technology at CTU. The department also includes Stringology and Arborology research groups. The G²OAT research group is rather small, comprising 1 associate professor, 2 assistant professors, 1 postdoc, and 4 Ph.D. students. A successful candidate will work at CTU's main campus which features a range of amenities such as the National Technical Library, and a laid-back atmosphere with cafes and other social hangout places.
Successful candidates will get a monthly salary of 65 thousand CZK (about 2500 EUR) (the Czech Republic cost of living is at 59% of the US price level by OECD statistics). There are no teaching duties associated with this position.
We are seeking highly motivated individuals holding a PhD in computer science, discrete mathematics, or related areas. The ideal candidate is familiar with several of the following areas: Parameterized complexity, integer linear programming, structural graph theory, game theory, computational social choice. Experience in optimization and in particular approximation algorithms or hardness of approximation is appreciated but not required. The candidate's high scientific potential should be witnessed by publications in the area of algorithms or discrete math in proceedings of highly ranked international conferences and/or journals.
The successful candidate must:
Information on how to apply will be available once the support for the position is actually approved.