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. Dušan Knop.
Fixed-parameter tractability and approximation algorithms are nowadays standard tools for design of algorithms for hard problems in the area of Computational Social Choice. Surprisingly, kernelization, a prominent technique in FPT algorithmics, is not used as often to tackle social choice problems. Kernelization is a formalism of safe data reduction which we believe does have its place in all research disciplines dealing with large and complex datasets. The most recent approach is the so-called lossy kernelization which on the one hand cooperates with approximation algorithms (unlike kernelization which can only be pipelined with exact algorithms) and on the other hand, allows circumventing hardness results (in exchange for introducing a possible loss in the quality of the solution).
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.