PhD positions in TCS at KTH Royal Institute of Technology, Stockholm (Sweden)

The Theory Group at KTH Royal Institute of Technology invites applications for up to four PhD positions in theoretical computer science.

The PhD positions are in the area of computational complexity theory, focusing on questions at the intersection of approximation algorithms, subexponential algorithms, and proof complexity. Examples of topics of particular interest are the use of linear and semidefinite programming to solve hard combinatorial problems, or of proof complexity to prove that the problems are beyond the reach of such methods. Exciting recent developments have identified the so-called sums of squares hierarchy as a unifying theme for these questions, and one aim of our research is to build and expand on this theme. However, we will also freely explore whatever other methods turn out to be helpful for attacking these and other topics of interest in algorithms and complexity theory. The overarching goal is to understand fundamental properties of efficient computation by proving mathematical theorems about the power and limitations of different computational models.

This research project is led by Johan Håstad, Per Austrin, and Jakob Nordström, and is financed by grants from the Knut and Alice Wallenberg Foundation, the European Research Council, and the Swedish Research Council.

In addition to the PIs and the announced PhD positions, the research project will also involve 2-3 existing PhD students and 3-4 postdocs. Thus, this will be a unique opportunity to explore new connections between different subareas of complexity theory within a vibrant and growing research environment.