Vacancies


          


Want to learn European cultures and lives, while having fun proving theorems in a world-class theoretical computer science group? Join KTH! 


We are constantly looking for postdocs with strong research record (e.g. with FOCS/STOC papers). 

There is no available PhD position at the moment. But if you have a strong interest in one of the research areas described below or in my research page, please feel free to contact me. Please mention the area(s). Pinpointing a specific paper or problem will be a big plus.

Short Summary
We are constantly looking for people who are interested in graph algorithms and complexity in general, and in particular want to work on one or more aspects of “Distributed and Dynamic Graph Algorithms and Complexity”. Candidates who have strong interests in exploring the impact of the following techniques in the fields of distributed and dynamic graph algorithms are especially desired: (i) algebraic techniques (e.g. fast algorithms for matrix multiplication and computing ranks), (ii) spectral techniques (e.g. fast algorithms for computing maximum flow, sparsest cut, and tree embedding), (iii) communication complexity, and (iv) fine-grained complexity.  

Work environment
You will be part of the Theoretical Computer Science department in the School of Computer Science and Communication, KTH Royal Institute of Technology, Stockholm, Sweden. Our department hosts one of the strongest groups in Europe in theoretical computer science, especially in complexity theory. We have a strong presence in FOCS and STOC, the flagship conferences in the area. The group is highly international. English is the default language spoken at work and most people in Sweden are fluent in English, even young kids.

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 center 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. No less than one-third of Sweden’s technical research and engineering education capacity at university level is provided by KTH.
 
Descriptions
Our project aims to resolve challenging problems in distributed and dynamic environments, with a focus on fundamental graph problems such as computing edge connectivity and shortest paths. The goal is to prove upper bounds by designing and analyzing algorithms and to prove lower bounds through information-theoretic and complexity-theoretic arguments, by taking advantage of and contributing to the developments in many young fields in theoretical computer science, such as fine-grained complexitysublinear algorithms, and spectral graph theory. Below are some examples of our goals:
  1. Develop an efficient dynamic algorithm for maintaining k-edge connectivity for any k>2 (extending Holm et al.’01 and improving Thorup’07), or prove that this cannot be done in a way similar to Patrascu’10Abboud and Vassilevska Williams’14 and Henzinger et al.’15.
  2. Develop an efficient distributed algorithm for computing k-edge connectivity for any k>3 (extending Pritchard and Thurimella’11), or prove that this cannot be done in a way similar to Das Sarma et al’12.
  3. Develop an efficient dynamic algorithm for maintaining directed single-source shortest paths (improving Henzinger et al.’14), or prove that this cannot be done in a way similar to Patrascu’10Abboud and Vassilevska Williams’14 and Henzinger et al.’15.
  4. Develop an efficient distributed algorithm for computing directed single-source shortest paths for any k>3 (extending Nanongkai’14 and Henzinger et al.’16), or prove that this cannot be done in a way similar to Das Sarma et al’12.
Working on these problems is an exciting opportunity to learn latest techniques from many subfields in TCS, and to collaborate with top researchers around the world. There is a generous travel support for attending conferences, workshops, summer schools, and collaborative research.  Our team members regularly attend and publish in top TCS conferences (FOCS, STOC, SODA, PODC, etc.) and are regularly invited to only-by-invitation workshops (e.g. DagstuhlBIRSShonanCageseChina theory weekADS).  They will also get to attend (and sometimes choose the topics for) our wonderful Swedish Summer School in Computer Science. We also host short-term and long-term visitors on a regular basis. For some of our activities, see here.

Qualifications
Postdoc: A strong candidate should have experiences in publishing in top conferences in his/her fields of research (e.g. FOCS/STOC/SODA/PODC for Theoretical Computer Science) and should have a strong interest in graph algorithms in general.  
PhD student: A strong candidate should have
  • a solid background in theoretical computer science and/or related fields (e.g. optimization and mathematics),
  • a strong interest in one of the above problems or some other related problems (the candidate should feel free to propose a problem of interest),
  • the will to spend years to focus on studying these problems and techniques needed to solve them (such as those in the papers listed above), and
  • an ambition to be a top researcher in TCS.
Previous experiences in shortest paths and connectivity problems (in any setting), and a familiarity with advanced techniques (such as spectral graph theory, linear sketches, property testing, fine-grained complexity and algebraic algorithms) are a big plus. Especially desired are candidates who have strong interests in exploring the impact of the following techniques in the fields of distributed and dynamic graph algorithms:
The preference is for a candidate with a Master’s degree, but an excellent candidate with a Bachelor’s degree could be possible.

Comments