Notice：
Ran Duan
Graph Algorithms, Data Structures, Computational Theory
Education Background
2002.9~2006.7 B.E. Computer Science and Technology, Tsinghua University, Beijing
2006.8~2011.8 Ph.D. Computer Science and Engineering, University of Michigan, Ann Arbor
2011.9~2014.8 Postdoctoral Researcher, Max-Planck-Institut für Informatik, Saarbrücken
Research Interests
Graph Algorithms, Data Structures, Approximate and Randomized Algorithms, Computational Complexity
Awards
Teaching
IIIS, Tsinghua University:
Theory of Computation (Undergraduate level), Spring 2015~2024
Design and Analysis of Algorithms (Graduate level), Fall 2015~2024
Theory and Practice of Computer Science (Undergraduate level), Summer 2016, Summer 2017
Introduction to Computer Science (Undergraduate level), Fall 2020, Fall 2021
Universität des Saarlandes:
Summer 2012, Advanced Graph Algorithms (Graduate level), co-lecturer with Jens M. Schmidt and Magnus Wahlström
Professional Service
PC Member of FAW 2018, FAW 2019, ISAAC 2019, FAW 2020, ICALP 2021, ESA 2021, SOSA 2023, SODA 2024, ITCS 2024
Journal Articles
Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election
Yi-Jun Chang, Ran Duan, Shunhua Jiang
ACM Transactions on Algorithms, 19(4), Article 33
Connectivity Oracles for Graphs Subject to Vertex Failures
Ran Duan, Seth Pettie
SIAM J. Comput., 49(6), 1363–1396
Scaling Algorithms for Weighted Matching in General Graphs
Ran Duan, Seth Pettie, Hsin-Hao Su
ACM Transactions on Algorithms 14(1), Article 8, 2018
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
Ran Duan, Kurt Mehlhorn
Journal version: Information and Computation, Volume 243, 112-132, 2015
Linear-Time Approximation for Maximum Weight Matching
Ran Duan, Seth Pettie
Journal of the ACM, 61(1):1-23, 2014
Conference Papers
Undirected 3-Fault Replacement Path in Nearly Cubic Time
Shucheng Chi, Ran Duan, Benyu Wang, Tianle Xie
To appear in the 52nd International Colloquium on Automata, Languages, and Programming (ICALP '25)
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin
To appear in Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC '25)
More Asymmetry Yields Faster Matrix Multiplication
Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou
In Proceedings of the 36th ACM-SIAM Symposium on Discrete Algorithms (SODA '25)
A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
Ran Duan, Jiayi Mao, Xinkai Shu, Longhui Yin
In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS '23)
Faster Matrix Multiplication via Asymmetric Hashing
Ran Duan, Hongxun Wu, Renfei Zhou
In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS '23)
Maintaining Exact Distances under Multiple Edge Failures
Ran Duan, Hanlin Ren
In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC '22)
Faster Min-Plus Product for Monotone Instances
Shucheng Chi, Ran Duan, Tianle Xie, Tianyi Zhang
In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC '22)
Faster Algorithms for Bounded-Difference Min-Plus Product
Shucheng Chi, Ran Duan, Tianle Xie
In Proceedings of the 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA '22)
Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election
Yi-Jun Chang, Ran Duan, Shunhua Jiang
In the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '21)
Approximate Distance Oracles Subject to Multiple Vertex Failures
Ran Duan, Yong Gu, Hanlin Ren
In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA '21)
A Scaling Algorithm for Weighted f-Factors in General Graphs
Ran Duan, Haoqing He, Tianyi Zhang
In the 47th International Colloquium on Automata, Languages, and Programming (ICALP '20)
Roundtrip Spanners with (2k-1) Stretch
Ruoxu Cen, Ran Duan, Yong Gu
In the 47th International Colloquium on Automata, Languages, and Programming (ICALP '20)
Near-linear Time Algorithms for Approximate Minimum Degree Spanning Trees
Ran Duan, Haoqing He, Tianyi Zhang
In the 14th Latin American Theoretical Informatics Symposium (LATIN '20)
Faster Algorithms for All Pairs Non-decreasing Paths Problem
Ran Duan, Ce Jin, Hongxun Wu
In the 46th International Colloquium on Automata, Languages, and Programming (ICALP '19)
Dynamic Edge Coloring with Improved Approximation
Ran Duan, Haoqing He, Tianyi Zhang
In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA '19)
Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time
Ran Duan, Hanlin Ren
In the 45th International Colloquium on Automata, Languages, and Programming (ICALP '18)
Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs
Ran Duan, Kaifeng Lyu, Yuanhang Xie
In the 45th International Colloquium on Automata, Languages, and Programming (ICALP '18)
arXiv version with slightly better bound by Hongxun Wu
Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs
Ran Duan, Yong Gu, Le Zhang
In the 45th International Colloquium on Automata, Languages, and Programming (ICALP '18)
Improved Algorithms for Maintaining DFS Tree in Undirected Graphs
Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang
In the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '18)
Improved Distance Sensitivity Oracles via Tree Partitioning
Ran Duan, Tianyi Zhang
In the Algorithms and Data Structures Symposium (WADS '17)
Faster Worst-Case Update Time for Dynamic Subgraph Connectivity
Ran Duan, Le Zhang
In the Algorithms and Data Structures Symposium (WADS '17)
Scaling Algorithms for Weighted Matching in General Graphs
Ran Duan, Seth Pettie, Hsin-Hao Su
In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA '17)
Connectivity Oracles for Graphs Subject to Vertex Failures
Ran Duan, Seth Pettie
In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA '17)
An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
Ran Duan, Jugal Garg, Kurt Mehlhorn
In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA '16)
Approximation Algorithms for the Gromov Hyperbolicity of Discrete Metric Spaces
Ran Duan
In proceedings of the 11th Latin American Theoretical Informatics Symposium (LATIN '14)
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
Ran Duan, Kurt Mehlhorn
In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP '13)
Breaking the $O(n^{2.5})$ Deterministic Time Barrier for Undirected Unit-Capacity Maximum Flow
Ran Duan
In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA '13)
A Scaling Algorithm for Maximum Weight Matching in Bipartite Graphs
Ran Duan, Hsin-Hao Su
In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA '12)
Approximating Maximum Weight Matching in Near-linear Time
Ran Duan, Seth Pettie
In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science (FOCS '10)
New Data Structures for Subgraph Connectivity
Ran Duan
In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP '10)
Connectivity Oracles for Failure Prone Graphs
Ran Duan, Seth Pettie
In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC '10)
Dual-Failure Distance and Connectivity Oracles
Ran Duan, Seth Pettie
In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09)
Fast Algorithms for (Max,Min)-Matrix Multiplication and Bottleneck Shortest Paths
Ran Duan, Seth Pettie
In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09)
Bounded-leg Distance and Reachability Oracles
Ran Duan, Seth Pettie
In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA '08)
