I'm interested in people who have a broad interest in algorithms, complexity, and computability theory. I'm also looking for people who would like to implement algorithms with provable guarantees in various hardware. The papers below should represent my current interest:
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 related papers, Danupon and the team's publication pages, and the outdated project descriptions below.
Communication/Distributed/Query/Quantum
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan: The query complexity of certification. STOC 2022: 623-636
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, Isadora Veeren, Distributed Quantum Advantage for Local Problems
Mika Göös, Toniann Pitassi, Thomas Watson: Deterministic Communication vs. Partition Number. SIAM J. Comput. 47(6): 2435-2450 (2018)
Andris Ambainis, Martins Kokainis, Robin Kothari: Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. CCC 2016: 4:1-4:14
Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang: On the Cut Dimension of a Graph. CCC 2021: 15:1-15:35
Simon Apers, Troy Lee: Quantum Complexity of Minimum Cut. CCC 2021: 28:1-28:33
Sepehr Assadi, Gillat Kol, Zhijun Zhang: Optimal Multi-pass Lower Bounds for MST in Dynamic Streams. STOC 2024: 835-846
Pierre Botteron, Moritz Weber: Communication Complexity of Graph Isomorphism, Coloring, and Distance Games
Dynamic Algorithms, Fast Algorithms
Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen: Decremental strongly-connected components and single-source reachability in near-linear time. STOC 2019: 365-376
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva: Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality. FOCS 2024: 2010-2032
Finegrained/Classic Complexity
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka: New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. STOC 2024: 935-943
Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber: A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity. SIAM J. Comput. 27(5): 1273-1282 (1998)
Mitali Bafna, Dor Minzer, Nikhil Vyas, Quasi-Linear Size PCPs with Small Soundness from HDX, STOC 2025
James Cook and Ian Mertz. Tree evaluation is in space o(log n · log log n). STOC 2024
Neural Networks/Machine Learning
Christoph Hertrich, Leon Sering: ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation. IPCO 2023: 187-202
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe: Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. AAAI 2019: 4602-4609
Michael Hahn: Theoretical Limitations of Self-Attention in Neural Sequence Models. Trans. Assoc. Comput. Linguistics 8: 156-171 (2020)
Linear Program and Extension Complexity
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer: Approximate Constraint Satisfaction Requires Large LP Relaxations. J. ACM 63(4): 34:1-34:22 (2016)
Hans Raj Tiwary: Extension Complexity of Formal Languages. Theory Comput. Syst. 64(5): 735-753 (2020)
Yael Tauman Kalai, Ran Raz, Oded Regev: On the Space Complexity of Linear Programming with Preprocessing. ITCS 2016: 293-300
Beyond Worst-Case Analysis
Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek: Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps. FOCS 2024
Bernhard Haeupler, Richard Hladík, Vaclav Rozhon, Robert E. Tarjan, Jakub Tětek, Bidirectional Dijkstra's Algorithm is Instance-Optimal. SOSA 2025
Mohsen Ghaffari, Goran Zuzic: Universally-Optimal Distributed Exact Min-Cut. PODC 2022: 281-291
Computability
Cristian S. Calude, Monica Dumitrescu: A statistical anytime algorithm for the Halting Problem. Comput. 9(2): 155-166 (2020)
Cristian S. Calude, Michael A. Stay: Most programs stop quickly or never halt. Adv. Appl. Math. 40(3): 295-308 (2008)
Laurent Bienvenu, Damien Desfontaines, Alexander Shen: Generic algorithms for halting problem and optimal machines revisited. Log. Methods Comput. Sci. 12(2) (2016)
Continuous optimization
Haotian Jiang: Minimizing Convex Functions with Integral Minimizers. SODA 2021: 976-985
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
Parameterized algorithms
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Torunczyk: Twin-Width IV: Ordered Graphs and Matrices. J. ACM 71(3): 21 (2024)
Algorithm engineering
Quinten De Man, Laxman Dhulipala, Adam Karczmarz, Jakub Łącki, Julian Shun, Zhongqi Wang, Towards Scalable and Practical Batch-Dynamic Connectivity
Lars Gottesbüren, Laxman Dhulipala, Rajesh Jayaram, Jakub Lacki: Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search. CoRR abs/2403.01797 (2024)
Laxman Dhulipala, David Eisenstat, Jakub Lacki, Vahab Mirrokni, Jessica Shi: Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth. NeurIPS 2022
Older list (This list is a bit outdated but is still relevant)
Papers on submodular functions and matroids
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
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, FOCS 2019
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
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)
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)
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
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
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
Online Matching with General Arrivals, FOCS 2019
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.
Faster All-Pairs Shortest Paths via Circuit Complexity. SIAM J. Comput. 47(5): 1965-1985 (2018)
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
Arun Jambulapati, Yang P. Liu, Aaron Sidford:
Parallel Reachability in Almost Linear Work and Square Root Depth. FOCS 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:
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
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
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
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
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
Our projects (some are outdated)
Disclaimer: The information below is a bit outdated. In particular, some open problems were solved already.
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.
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.
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:
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’10, Abboud and Vassilevska Williams’14 and Henzinger et al.’15.
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.
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’10, Abboud and Vassilevska Williams’14 and Henzinger et al.’15.
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. 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.
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:
algebraic techniques such as fast algorithms for matrix multiplication and computing ranks (see, e.g. Cheung et al., Sankowski’07, and Sankowski’04]),
spectral techniques such as fast algorithms for computing maximum flow, sparsest cut, and tree embedding (see, e.g., Patrascu-Thorup and Abraham et al.), and/or
communication complexity (see, e.g. Das Sarma et al’12 and Chattopadhyay et al.’12).
The preference is for a candidate with a Master’s degree, but an excellent candidate with a Bachelor’s degree could be possible.