Project & Job Opportunities


          


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


News: There is a postdoc/PhD student position available. Please read below. 

Master Projects: If you're a student at KTH and are interested in algorithms/complexity-related projects/theses, please contact me to get a list of possible projects or to propose your ideas.

PhD (apply here Dec 5, 2019 - Jan 6, 2020): 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. For an outstanding candidate, something can be worked out. 

Postdocs: Candidates with a strong research record (e.g. with FOCS/STOC papers) are encouraged to contact me. Please stay tuned for a formal application process.


Papers relevant to our interests

If you feel that some of the papers below are of your interest, you might fit well in our group. Disclaimer: Below is not an exhaustive list. Please also check Danupon and the team's publication pages and the outdated project descriptions below.

Papers on interior-point method, max-flow 

Jan van den Brand
A Deterministic Linear Program Solver in Current Matrix Multiplication Time SODA 2020

Yin Tat Lee, Aaron Sidford:
Solving Linear Programs with Sqrt(rank) Linear System Solves.  PDF

Michael B. Cohen, Yin Tat Lee, Zhao Song:
Solving linear programs in the current matrix multiplication time. STOC 2019: 938-942 PDF

Aleksander Madry:
Computing Maximum Flow with Augmenting Electrical Flows. FOCS 2016: 593-602
PDF:  https://arxiv.org/abs/1608.06016  

Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu:
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time. SODA 2017: 752-771  

Papers on submodular function minimization

Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong:
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization. FOCS 2015: 1049-1065
PDF:  https://arxiv.org/abs/1508.04874  (Part 3 in particular)


Nicholas J. A. Harvey:
Matroid intersection, pointer chasing, and Young's seminormal representation of Sn. SODA 2008: 542-549



Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong
Faster Matroid Intersection

Papers on mincut

Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak:
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. CoRR abs/1910.08025 (2019)  

Sagnik Mukhopadhyay, Danupon Nanongkai: Weighted Min-Cut: 
Sequential, Cut-Query and Streaming Algorithms. CoRR abs/1911.01651 (2019)

Ken-ichi Kawarabayashi, Mikkel Thorup: 
Deterministic Edge Connectivity in Near-Linear Time, JACM (2019)

Jason Li
Faster Minimum k-cut of a Simple Graph, FOCS 2019

Mohit Daga, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak: 
Distributed edge connectivity in sublinear time. STOC 2019: 343-354

Mohsen Ghaffari, Krzysztof Nowicki, Mikkel Thorup: 
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions. SODA 2020 

Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn
A New Perspective on Vertex Connectivity 
 
Papers on Matching
Manoj Gupta, Richard Peng: 
Fully Dynamic (1+ e)-Approximate Matchings. FOCS 2013: 548-557


Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, David Wajc
Online Matching with General Arrivals, FOCS 2019
PDF: https://arxiv.org/abs/1904.08255

Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu and Yuhao Zhang. 
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model, SODA 2019.


Papers on Shortest Paths
R. Ryan Williams:
Faster All-Pairs Shortest Paths via Circuit Complexity. SIAM J. Comput. 47(5): 1965-1985 (2018)


Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu:
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time. SODA 2017: 752-771  


Sebastian Forster, Danupon Nanongkai:
A Faster Distributed Single-Source Shortest Paths Algorithm. FOCS 2018: 686-697

Arun Jambulapati, Yang P. Liu, Aaron Sidford: 
Parallel Reachability in Almost Linear Work and Square Root Depth. CoRR abs/1905.08841 (2019)

M. P. Gutenberg and C. Wulff-Nilsen. Decremental SSSP in Weighted Digraphs: 
Faster and Against an Adaptive Adversary. To appear at SODA 2020.

Papers on fine-grained complexity:
Virginia Vassilevska Williams:
Some Open Problems in Fine-Grained Complexity. SIGACT News 49(4)29-35 (2018)

Kasper Green Larsen, R. Ryan Williams:
Faster Online Matrix-Vector Multiplication. SODA 2017: 2182-2189
PDF:  https://arxiv.org/abs/1605.01695  


Paper on communication complexity:
– Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi: A little advice can be very helpful. SODA 2012: 615-625
- Young Kun Ko, Omri Weinstein: An Adaptive Step Toward the Multiphase Conjecture: https://arxiv.org/abs/1910.13543
– Noam Nisan, Avi Wigderson: Rounds in Communication Complexity Revisited. SIAM J. Comput. 22(1): 211-219 (1993)


Other Papers: 
– Aaron Bernstein, Shiri Chechik: Incremental Topological Sort and Cycle Detection in Expected Total Time. SODA 2018: 21-34
– Yi-Jun Chang, Seth Pettie, Hengjie Zhang: Distributed Triangle Detection via Expander Decomposition. https://arxiv.org/abs/1807.06624
– Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer: Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput. 41(5): 1235-1265 (2012) http://epubs.siam.org/doi/abs/10.1137/11085178X
– Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time https://iuuk.mff.cuni.cz/~koucky/LBCAD/papers/approxEdit.pdf
– Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability https://arxiv.org/abs/1810.10982
– “Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering” https://arxiv.org/abs/1811.03195
– Vera Traub, Jens Vygen: Beating the Integrality Ratio for s-t-Tours in Graphs. FOCS 2018: 766-777



Our projects (some are outdated)

Disclaimer: The information below is a bit outdated. In particular, some open problems were solved already. 

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