Ran Duan
Assistant Professor
Institute for Interdisciplinary Information Sciences

Address: FIT 1-208, Tsinghua University, 100084, Beijing, China


 

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, Algorithmic Game Theory



Awards


2011 Humboldt fellowship
2015 China’s Youth 1000-Talent Program


Teaching


IIIS, Tsinghua University:

Spring 2017, Theory of Computation (Undergraduate level)

Fall 2016, Design and Analysis of Algorithms (Graduate level)

Summer 2016, Theory and Practice of Computer Science (Undergraduate level)

Spring 2016, Theory of Computation (Undergraduate level)

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

Spring 2015, Theory of Computation (Undergraduate level)

 

Universität des Saarlandes:

Summer 2012, Advanced Graph Algorithms (Graduate level), co-lecturer with Jens M. Schmidt and  Magnus Wahlström

 

Manuscripts/In Submission


Improved Algorithms for Maintaining DFS Tree in Undirected Graphs
Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang
In Submission

arXiv

 

Journal Articles


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

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

 

Conference Papers


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 24th ACM-SIAM Symposium on Discrete Algorithms (SODA '17)

arXiv

Connectivity Oracles for Graphs Subject to Vertex Failures
Ran Duan, Seth Pettie
In Proceedings of the 24th 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 24th 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)

 


Talks and Slides