KTH  

Approximability and Proof Complexity

 
   
(See here for Swedish version of announcement.)

Postdoc Positions in Theoretical Computer Science

The application deadline has passed, but if you are a very strong candidate you can still submit your application. Applications will be reviewed until the positions have been filled.

The Theoretical Computer Science Group at KTH Royal Institute of Technology invites applications for up to four postdoc positions in theoretical computer science.

Job Description

The Theoretical Computer Science Group at KTH (www.csc.kth.se/tcs) offers a strong research environment spanning a wide range of research topics such as complexity theory and approximation algorithms, computer and network security, cryptography, formal methods and natural language processing. We have one of Europe's most prominent groups in algorithms and complexity theory, and the research conducted here has attracted numerous international awards and grants in recent years.

The postdoc 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.

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, 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.

Within the overall framework sketched above, the postdoc will be expected and encouraged to contribute to and influence the research agenda. Taking part in teaching graduate seminar courses is encouraged but not required. Travel funding is included, and the group also receives short-term and long-term visitors on a regular basis.

These postdoc positions are full-time employed positions for one year with a possible one-year extension. The expected starting date is in August-September 2017, although this is to some extent negotiable.

Qualifications

Applicants should have or be about to receive a PhD degree in a subject relevant for the research area, and should have a passionate interest in research. The successful candidate is expected to have a solid background in theoretical computer science and mathematics, and should have a strong research record as witnessed by publications in conferences such as STOC, FOCS, SODA, CCC, or similar, or in journals of a comparable quality.

The working language of the TCS group is English, and knowledge of English is also fully sufficient to navigate life in Sweden in general. It might also be worth mentioning that Sweden routinely scores at the absolute top in rankings of quality of life such as, e.g., the OECD Better Life Index.

Workplace

KTH Royal Institute of Technology in Stockholm has grown to become one of Europe's leading technical and engineering universities, as well as a key centre of intellectual talent and innovation. We are Sweden's largest technical research and learning institution and home to students, researchers and faculty from around the world. Our research and education covers a wide area including natural sciences and all branches of engineering, as well as in architecture, industrial management, urban planning, history and philosophy.

The School of Computer Science and Communication at KTH (KTH CSC) is a premier research and education institution in information technology, with activities at both KTH and Stockholm University. We conduct education and research in both theoretical and applied computer science. Our activities in theoretical computer science range from theory building and analysis of mathematical models to algorithm construction, implementation and simulation. Applied computer science covers a wide spectrum including computer vision, robotics, machine learning, high performance computing, visualization, computational biology, neuroinformatics and neural networks, and speech and music communication. We also conduct applied research and training in media technology, human-computer interaction, interaction design and sustainable development. For more information, see www.kth.se/en/csc.

Employment

Form of employment: One year temporary position with a possible one-year extension
Work time: Full time
Start date: By agreement, but preferably no later than August-September 2017
Number of positions: 4

Application

Application deadline: January 15, 2017
Employer's reference: D-2016-0871

Applications are submitted via the KTH recruitment system at kth.mynetworkglobal.com/en/what:login/jobID:127451/type:job/where:4/apply:1/. Note that applicants are responsible that applications are complete as per the instructions below. Complete applications must be received by KTH by midnight CET at the date of the application deadline.

The application should include the following documents:

  1. Curriculum vitae.
  2. List of publications.
  3. Brief research statement with description of research so far and future research goals and interests.
  4. Copy of PhD diploma (if applicable).
  5. Names and addresses of three or more individuals who will provide letters of recommendation.

Please observe that all the documents above should be in English (or for official documents possibly in Swedish).

Writers of recommendation letters should submit their letters directly to apc@csc.kth.se by the application deadline. Please state the reference number D-2016-0871 in the subject line.

Further Information and Contact Details

Enquiries about the research project can be made via e-mail to apc@csc.kth.se or by phone to the numbers below:

Johan Håstad, Professor
Phone: +46 8 790 62 89

Jakob Nordström, Associate Professor
Phone: +46 8 790 69 19

Per Austrin, Associate Professor
Phone: +46 8 790 62 86

For enquiries about PhD studies and employment conditions, please contact:

Maria Widlund, HR Manager
Phone: +46 8 790 97 54
E-mail: mwidlund@kth.se

Last modified: December 20, 2018