[Proof Complexity] PhD positions in computational complexity at KTH Royal Institute of Technology

[Jakob Nordström]

Dear colleagues,

We would be very grateful for your assistance in spreading the information that the Theory Group at KTH Royal Institute of Technology is looking for PhD students in computational complexity (including proof complexity).

The positions are within a research project led by Johan Hastad, Per Austrin, and Jakob Nordstrom 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.

In addition to the PIs, the research project is planned to involve a total of 4-5 postdocs and 5-7 PhD students. Thus, this will be a unique opportunity to explore new connections between different subareas of complexity theory within a vibrant and growing research environment.

The application deadline is March 31, 2017. See http://apc.csc.kth.se/D-2017-0117-Eng.php for the full announcement with more information and instructions how to apply. Informal enquiries are welcome and may be sent to apc at csc.kth.se . Please note that this is an additional announcement on top of the earlier PhD positions in D-2016-0832 due to additional research funding. Candidates who already applied for the positions D-2016-0832 should not apply again --- all applicants for both announcements are evaluated in parallel.

With best regards,
Jakob Nordstrom

Jakob Nordström, Associate Professor
KTH Royal Institute of Technology
Phone: +46 8 790 69 19 (office), +46 70 742 21 98 (cell)
http://www.csc.kth.se/~jakobn/