Project & Job Opportunities

Under construction!


I'm moving to MPI in Germany in July 2022. Please see here for our offers. The information below is a bit outdated, but not irrelevant. 


We are looking for people who want to work on one or more aspects of graph algorithms and complexity. Candidates who have strong interests in exploring the impact of the following techniques in the fields of graph algorithms are especially desired: 


* optimization (e.g. submodular minimization, matroid theory, LP solvers), 

* spectral algorithms (e.g. fast algorithms for computing maximum flow, sparsest cut, and tree embedding)

* traditional, fine-grained, and communication complexity, 

* dynamic data structures (graph and algebraic techniques), and

* parallel, distributed, and streaming algorithms.


See below to get an idea of what we are interested in. 


Postdocs: Candidates with strong research records (e.g. with FOCS/STOC papers) are encouraged to contact me.


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.


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 continuous optimization, graph Laplacians

Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

PDF: https://arxiv.org/abs/2203.00671


Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, Aaron Sidford

Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers. STOC 2022

PDF: https://arxiv.org/abs/2112.00722


Yu Gao, Yang P. Liu, Richard Peng: 

Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao. FOCS 2021

PDF: https://arxiv.org/abs/2101.07233 


Jan van den Brand

A Deterministic Linear Program Solver in Current Matrix Multiplication Time SODA 2020

PDF


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  

PDF:  https://arxiv.org/abs/1605.01717  


Yang P. Liu, Aaron Sidford

Faster Energy Maximization for Faster Maximum Flow. STOC 2020

PDF: https://arxiv.org/abs/1910.14276



Papers on submodular functions and matroids


Haotian Jiang: 

Minimizing Convex Functions with Integral Minimizers. SODA 2021: 976-985

PDF: https://arxiv.org/abs/2007.01445 


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

PDF:  https://dl-acm-org.focus.lib.kth.se/citation.cfm?id=1347142 


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

Faster Matroid Intersection, FOCS 2019

PDF: https://arxiv.org/abs/1911.10765


Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong: 

Subquadratic submodular function minimization. STOC 2017: 1220-1231

PDF: https://arxiv.org/abs/1610.09800 


Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang: 

On the cut dimension of a graph. CoRR abs/2011.05085 (2020)

PDF: https://arxiv.org/abs/2011.05085


Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, S. Matthew Weinberg: 

New Query Lower Bounds for Submodular Function Minimization. ITCS 2020: 64:1-64:16

PDF: https://arxiv.org/abs/1911.06889


Rohit Gurjar, Thomas Thierauf: 

Linear Matroid Intersection is in Quasi-NC. Comput. Complex. 29(2): 9 (2020)

PDF: https://link.springer.com/article/10.1007/s00037-020-00200-z

Papers on cut

Jason Li:

Deterministic Mincut in Almost-Linear Time. STOC 2021.

PDF: http://www.cs.cmu.edu/~jmli/papers/deterministic-mincut-in-almost-linear.pdf 


Jason Li, Debmalya Panigrahi: 

Deterministic Min-cut in Poly-logarithmic Max-flows. FOCS 2020: 85-92

PDF: http://www.cs.cmu.edu/~jmli/papers/deterministic-mincut-in-polylogarithmic-conf.pdf


Chandra Chekuri, Chao Xu: 

Minimum Cuts and Sparsification in Hypergraphs. SIAM J. Comput. 47(6): 2118-2156 (2018)


Yu Chen, Sanjeev Khanna, Ansh Nagda: 

Near-linear Size Hypergraph Cut Sparsifiers. FOCS 2020: 61-72

PDF: https://arxiv.org/abs/2009.04992


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)  

PDF: https://arxiv.org/abs/1910.08025


Sagnik Mukhopadhyay, Danupon Nanongkai: 

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

PDF: https://arxiv.org/abs/1911.01651


Ken-ichi Kawarabayashi, Mikkel Thorup: 

Deterministic Edge Connectivity in Near-Linear Time, JACM (2019)

PDF: https://arxiv.org/abs/1411.5123


Mohsen Ghaffari, Krzysztof Nowicki, Mikkel Thorup: 

Faster Algorithms for Edge Connectivity via Random 2-Out Contractions. SODA 2020 

PDF: https://arxiv.org/abs/1909.00844


Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn

A New Perspective on Vertex Connectivity 

PDF https://arxiv.org/abs/1304.4553


S. Apers and T. Lee

Quantum complexity of minimum cut.

PDF: https://arxiv.org/abs/2011.09823


Christoph Durr, Mark Heiligman, Peter Hoyer, Mehdi Mhalla

Quantum query complexity of some graph problems

PDF: https://arxiv.org/pdf/quant-ph/0401091.pdf

 

Papers on Matching


Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, Morteza Zadimoghaddam: 

Edge-Weighted Online Bipartite Matching. FOCS 2020: 412-423

PDF: https://arxiv.org/abs/2005.01929


Manoj Gupta, Richard Peng: 

Fully Dynamic (1+ e)-Approximate Matchings. FOCS 2013: 548-557

PDF: https://arxiv.org/abs/1304.0378



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.

PDF: https://arxiv.org/abs/1810.07903



Papers on Shortest Paths


R. Ryan Williams:

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

PDF: https://epubs.siam.org/doi/10.1137/15M1024524



Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak: 

Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. CoRR abs/2101.07149 (2021)

PDF: https://arxiv.org/abs/2101.07149 


Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen: Near-Optimal Decremental SSSP in Dense Weighted Digraphs. FOCS 2020: 1112-1122

PDF: https://arxiv.org/abs/2004.04496


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  

PDF:  https://arxiv.org/abs/1605.01717  


Arun Jambulapati, Yang P. Liu, Aaron Sidford: 

Parallel Reachability in Almost Linear Work and Square Root Depth. FOCS 2019

PDF: https://arxiv.org/abs/1905.08841


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)

PDF: http://people.csail.mit.edu/virgi/eccentri.pdf


C. S. Karthik & Pasin Manurangsi

On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

PDF: https://link.springer.com/article/10.1007/s00493-019-4113-1


Amir Abboud, Aviad Rubinstein, Ryan Williams

Distributed PCP Theorems for Hardness of Approximation in P

PDF: https://arxiv.org/abs/1706.06407


Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, Nicole Wein: 

Algorithms and Hardness for Diameter in Dynamic Graphs. ICALP 2019: 13:1-13:14


Kasper Green Larsen, R. Ryan Williams:

Faster Online Matrix-Vector Multiplication. SODA 2017: 2182-2189

PDF:  https://arxiv.org/abs/1605.01695  





Papers on communication and query complexity


Noam Nisan: The Demand Query Model for Bipartite Matching: SODA 2021: 592-599 


Stephen Ponzio, Jaikumar Radhakrishnan, S. Venkatesh: The Communication Complexity of Pointer Chasing: JCSS 62: 323-355 (2001) 


Xiaoming Sun, Chengu Wang: Randomized Communication Complexity for Linear Algebra Problems over Finite Fields: STACS 2012: 477-488.


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)



Paper on distributed computing


Bernhard Haeupler, David Wajc, Goran Zuzic, Universally-Optimal Distributed Algorithms for Known Topologies. STOC 2021. PDF: https://arxiv.org/abs/2104.03932


Yi-Jun Chang, Thatchaphol Saranurak: Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization. FOCS 2020: 377-388


Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, Mingquan Ye: Minor Sparsifiers and the Distributed Laplacian Paradigm. CoRR abs/2012.15675 (2020) https://arxiv.org/abs/2012.15675 


François Le Gall, Frédéric Magniez: Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. PODC 2018: 337-346 https://arxiv.org/abs/1804.02917 


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


Other Papers 


Jesper Nederlof, Céline M. F. Swennenhuis, Karol Wegrzycki: A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints. CoRR abs/2312.03495 (2023) https://arxiv.org/abs/2312.03495 


Aaron Bernstein, Shiri Chechik: Incremental Topological Sort and Cycle Detection in Expected Total Time. SODA 2018: 21-34


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





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 complexity, sublinear algorithms, and spectral graph theory. Below are some examples of our goals:

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. Dagstuhl, BIRS, Shonan, Cagese, China theory week, ADS).  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

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.