Yonggang Jiang (姜勇刚)

Research Interests

I work broadly on algorithms and optimization. My goal is to design algorithms that are theoretically efficient and draw the insights to fast implementation in practice. I am particularly interested in:

Graph algorithms
Parallel computing
Algorithm engineering
AI for mathematics and optimization

I am currently developing LLM harnesses for mathematical research. I lead the development of TCS-prover and contribute to ProofCouncil.

Education & Experience

Experience

ETH Institute for Theoretical Studies (ETH-ITS)

2026.10 – Present

Junior Fellow

Education

Max Planck Institute for Informatics

2021.10 - 2026.9

PhD in Computer Science

Thanks to my wonderful advisor, Danupon Nanongkai, for his guidance and support. My PhD thesis is available here.

Education

Nanjing University

2017.9 - 2021.7

Bachelor of Science in Computer Science and Technology

GPA: 94.4/100; rank: 1/31.

Thanks to Yitong Yin and Chaodong Zheng for supervising my undergraduate research, and to Binkai Lin for supervising my undergraduate thesis.

I spent some wonderful years at the theory group, doing research and having fun with my peers and seniors. Thanks to all of them.

(2020.1 - 2020.5) Exchange student at University of California, Berkeley.

Honors & Awards

2025 Google PhD Fellowship
2025 Distinguished Paper Award, SPAA 2025
2021 Outstanding Graduate, Nanjing University
2018, 2019, 2020 National Elite Program Scholarship, Outstanding Prize (top 1)
2018 China Collegiate Programming Contest (CCPC), Gold Medal
2015 National Olympiad in Informatics in Provinces (NOIP), First Prize

Publications

Following the convention in mathematics, authors are listed alphabetically with equal contribution unless marked †. † indicates authors ordered by contribution.

Papers marked with AI have an AI-generated solution as their main contribution. For unmarked papers, the main ideas are entirely human-generated. See my principles on AI results.

2027

26.
Almost Optimal Streaming and Cut-Query Algorithms for Undirected Max-Flow
Yonggang Jiang, Tatsuya Terao.
SODA 2027: ACM-SIAM Symposium on Discrete Algorithms.

2026

25.
Quantum Submodular Maximization arXiv AI
Yonggang Jiang, Xiaoming Sun, Penghui Yao, Zekun Ye, Jialin Zhang, Zhijie Zhang.
24.
The Complexity of Distributed Minimum Weight Cycle Approximation arXiv
Yi-Jun Chang, Yanyu Chen, Dipan Dey, Yonggang Jiang, Gopinath Mishra, Hung Thuan Nguyen, Mingyang Yang.
23.
Breaking the Barrier: Practical Cascade-Based Parallel Push-Relabel for Maximum Flow
Xiaojun Dong, Matei Chiriac, Yonggang Jiang.^†
22.
Meta-Harness Adaptation for Evolving Fast Graph Algorithms
Amirhossein Abedi, Yonggang Jiang, Xiaojun Dong.^†
NeurIPS 2026 Workshop: Neural Information Processing Systems, Meta-Agents Workshop.
21.
Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak.
FOCS 2026: IEEE Symposium on Foundations of Computer Science.
20.
Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth arXiv
Yonggang Jiang, Changki Yun.
FOCS 2026: IEEE Symposium on Foundations of Computer Science.
19.
Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers arXiv
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak.
STOC 2026: ACM Symposium on Theory of Computing.
18.
DAG Projections: Reducing Distance and Flow Problems to DAGs arXiv
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak.
STOC 2026: ACM Symposium on Theory of Computing.
17.
Reviving Thorup’s Shortcut Conjecture arXiv
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, Leon Schiller.
STOC 2026: ACM Symposium on Theory of Computing.
16.
Perfect Simulation of Las Vegas Algorithms via Local Computation arXiv
Xinyu Fu, Yonggang Jiang, Yitong Yin.
ITCS 2026: Innovations in Theoretical Computer Science.
15.
Reducing Shortcut and Hopset Constructions to Shallow Graphs arXiv
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak.
SOSA 2026: SIAM Symposium on Simplicity in Algorithms.
14.
Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs arXiv
Olivier Fischer, Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai.
SOSA 2026: SIAM Symposium on Simplicity in Algorithms.
13.
Minimum s–t Cuts with Fewer Cut Queries arXiv
Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya.
SODA 2026: ACM-SIAM Symposium on Discrete Algorithms.
12.
Shortcuts and Transitive-Closure Spanners Approximation arXiv
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai.
SODA 2026: ACM-SIAM Symposium on Discrete Algorithms.
11.
New Oracles and Labeling Schemes for Vertex Cut Queries arXiv
Yonggang Jiang, Merav Parter, Asaf Petruschka.
SODA 2026: ACM-SIAM Symposium on Discrete Algorithms.

2025

10.
Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies arXiv
Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, Benyu Wang.
9.
A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow arXiv
Hossein Gholizadeh, Yonggang Jiang.
8.
Parallel $(1+\epsilon)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work arXiv
Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang.
FOCS 2025: IEEE Symposium on Foundations of Computer Science.
7.
Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances arXiv
Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang, Tijn de Vos.
SPAA 2025: ACM Symposium on Parallelism in Algorithms and Architectures.
Distinguished Paper Award
Invited to TOPC Special Issue
6.
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness arXiv
Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai.
STOC 2025: ACM Symposium on Theory of Computing.
5.
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations arXiv
Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai.
STOC 2025: ACM Symposium on Theory of Computing.

2024

4.
Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights arXiv
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin Hao Su.
ESA 2024: European Symposium on Algorithms.

2023

3.
Finding a Small Vertex Cut on Distributed Networks arXiv
Yonggang Jiang, Sagnik Mukhopadhyay.
STOC 2023: ACM Symposium on Theory of Computing.

2022

2.
Robust and Optimal Contention Resolution without Collision Detection arXiv
Yonggang Jiang, Chaodong Zheng.
SPAA 2022: ACM Symposium on Parallelism in Algorithms and Architectures.

2021

1.
Tight Trade-off in Contention Resolution without Collision Detection arXiv
Haimin Chen, Yonggang Jiang, Chaodong Zheng.
PODC 2021: ACM Symposium on Principles of Distributed Computing.

My personal opinions on papers with AI-generated results

I distinguish two kinds of contribution in theoretical papers:

Introducing a new concept, problem, model, or conjecture, and explaining why it is useful or important.
Finding a new solution to an established open problem on which progress has been difficult.

Traditionally, progress on open problems was usually scarce, so 2 was often a paper’s main contribution.

Recently, AI has become powerful at 2 (see OpenAI’s report, as one of the examples). However, many recent theoretical papers still follow the traditional framing: they present 2 as their main contribution, even when the solution is produced by AI and the paper contributes nothing of 1. I mark such papers with AI . Note that I do not use this marker for papers whose main contribution is a new human-developed concept, problem, model, or conjecture, even if their proofs are generated by AI and they are extracted from AI proofs.

Personally, I see papers with this marker primarily as communicating what is now known about existing open problems. This is important: sharing these results helps others avoid duplicating effort and allows the community to move forward. I also count polishing the writing and making the results understandable to humans as a contribution. However, I do not claim intellectual credit for these papers; that credit goes to AI. I would rather see more intellectual effort spent on 1, where we can make real contributions.