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

2011 Humboldt fellowship


Teaching

IIIS, Tsinghua University:

Theory of Computation (Undergraduate level), Spring 2015~2023

Design and Analysis of Algorithms (Graduate level), Fall 2015~2023

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

Manuscripts/In Submission

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

arXiv

Connectivity Oracles for Graphs Subject to Vertex Failures
Ran Duan, Seth Pettie
SIAM J. Comput., 49(6), 1363–1396
arXiv
 

Scaling Algorithms for Weighted Matching in General Graphs
Ran Duan, Seth Pettie, Hsin-Hao Su
ACM Transactions on Algorithms 14(1), Article 8, 2018
arXiv

A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
Ran Duan, Kurt Mehlhorn
Journal version: Information and Computation, Volume 243, 112-132, 2015
arXiv

Linear-Time Approximation for Maximum Weight Matching
Ran Duan, Seth Pettie
Journal of the ACM, 61(1):1-23, 2014

Conference Papers

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)
arXiv

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)
arXiv

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)
arXiv

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)
arXiv

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)
arXiv

Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election
Yi-Jun Chang, Ran Duan, Shunhua Jiang
In the 33th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '21)
arXiv

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)
arXiv

Roundtrip Spanners with (2k-1) Stretch
Ruoxu Cen, Ran Duan, Yong Gu
In the 47th International Colloquium on Automata, Languages, and Programming (ICALP '20)
arXiv

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)
arXiv

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)
arXiv

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)
arXiv

Improved Distance Sensitivity Oracles via Tree Partitioning
Ran Duan, Tianyi Zhang
In the Algorithms and Data Structures Symposium (WADS '17)
arXiv

Faster Worst-Case Update Time for Dynamic Subgraph Connectivity
Ran Duan, Le Zhang
In the Algorithms and Data Structures Symposium (WADS '17)
arXiv

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)
arXiv

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)
arXiv

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)