Yi-Jun Chang
I am an NUS Presidential Young Professor in the Department of Computer Science at the National University of Singapore. I am broadly interested in theoretical computer science, focusing on the design and analysis of distributed, parallel, and sublinear graph algorithms.
▸ Google Scholar▸ DBLP▸ ORCID: 0000-0002-0109-2432
Program committees: SPAA 2027, STOC 2027, SIROCCO 2027, SPAA 2026, PODC 2026, COCOON 2026, STOC 2026, OPODIS 2025, ISAAC 2025, PODC 2025, OPODIS 2024, ISAAC 2024, DISC 2024, ESA 2024, IWOCA 2024, SPAA 2024, SPAA 2023, SIROCCO 2023, SODA 2023, ICDCN 2023.
Education and employment
Assistant Professor @ Department of Computer Science, National University of Singapore (2021–current)
Junior Fellow @ Institute for Theoretical Studies, ETH Zurich (2019–2021, mentor: Mohsen Ghaffari)
Ph.D. @ Computer Science and Engineering, University of Michigan (2015–2019, mentor: Seth Pettie)
▸ Dissertation 2020 PODC Doctoral Dissertation AwardM.S. @ Electrical Engineering, National Taiwan University (2013–2015, mentor: Hsu-Chun Yen)
B.S. @ Electrical Engineering, National Taiwan University (2009–2013)
Teaching
CS6234 Advanced Algorithms
▸ Semester 1, AY2023/2024▸ Semester 1, AY2022/2023CS5275 The Algorithm Designer's Toolkit
▸ Semester 2, AY2026/2027▸ Semester 2, AY2025/2026CS5330 Randomized Algorithms
▸ Semester 2, AY2024/2025▸ Semester 2, AY2023/2024▸ Semester 2, AY2022/2023▸ Semester 2, AY2021/2022CS3230 Design and Analysis of Algorithms
▸ Semester 1, AY2026/2027▸ Semester 1, AY2025/2026▸ Semester 1, AY2024/2025Team members
Ph.D. students:
Hung Thuan Nguyen (8/2024–current)Haoran Zhou (1/2024–current)Postdoctoral researchers:
Gopinath Mishra (9/2023–11/2025)Dean Leitersdorf (11/2022–5/2023)Contact
Office:
▸COM3-02-24, 11 Research Link, Singapore 119391Email:
▸cyijun@nus.edu.sg▸cyijun@umich.eduConference papers
Energy-efficient aggregation and minimum-degree spanning trees in radio networks
with Yang Ze GuanSPAA 2026Outstanding Paper Award ▸ ArXiv version▸ Conference versionNon-uniform content-oblivious leader election on oriented asynchronous rings
with Jérémie Chalopin, Lyuting Chen, Giuseppe A. Di Luna and Haoran ZhouSPAA 2026▸ ArXiv version▸ Conference versionEfficient counting and simulation in content-oblivious rings
with Jérémie Chalopin, Giuseppe A. Di Luna and Haoran ZhouPODC 2026Best Student Paper Award ▸ ArXiv version▸ Conference versionBeyond 2-edge-connectivity: algorithms and impossibility for content-oblivious leader election
with Lyuting Chen and Haoran ZhouITCS 2026▸ ArXiv version▸ Conference versionOverlay network construction: improved overall and node-wise message complexity
with Yanyu Chen and Gopinath MishraFSTTCS 2025▸ ArXiv version▸ Conference versionContent-oblivious leader election in 2-edge-connected networks
with Jérémie Chalopin, Lyuting Chen, Giuseppe A. Di Luna and Haoran ZhouDISC 2025Best Student Paper Award Invited to the special issue of Distributed Computing▸ ArXiv version▸ Conference version▸ Journal versionThe complexity landscape of dynamic distributed subgraph finding
with Lyuting Chen, Yanyu Chen, Gopinath Mishra and Mingyang YangDISC 2025▸ ArXiv version▸ Conference versionBounded memory in distributed networks
with Ran Ben Basat, Keren Censor-Hillel, Wenchen Han, Dean Leitersdorf and Gregory SchwartzmanSPAA 2025▸ ArXiv version▸ Conference versionOptimal distributed replacement paths
with Yanyu Chen, Dipan Dey, Gopinath Mishra, Hung Thuan Nguyen and Bryce SanchezPODC 2025▸ ArXiv version▸ Conference versionOptimal local certification on graphs of bounded pathwidth
with Dan Alden BaterisnaPODC 2025▸ ArXiv version▸ Conference versionRound and communication efficient graph coloring
with Gopinath Mishra, Hung Thuan Nguyen and Farrel D. SalimPODC 2025▸ ArXiv version▸ Conference versionLow-distortion clustering in bounded growth graphs
with Varsha Dani and Thomas P. HayesSIROCCO 2025▸ ArXiv version ▸ Conference versionA tight lower bound for 3-coloring grids in the online-LOCAL model
with Gopinath Mishra, Hung Thuan Nguyen, Mingyang Yang and Yu-Cheng YehPODC 2024▸ ArXiv version▸ Conference versionDeterministic expander routing: faster and more versatile
with Shang-En Huang and Hsin-Hao SuPODC 2024▸ ArXiv version▸ Conference versionImproved all-pairs approximate shortest paths in congested clique
with Hong Duc Bui, Shashwat Chandra, Michal Dory and Dean LeitersdorfPODC 2024 Best Student Paper Award Invited to the special issue of Distributed Computing▸ ArXiv version▸ Conference version▸ Journal versionUniversally optimal information dissemination and shortest paths in the HYBRID distributed model
with Oren Hecht, Dean Leitersdorf and Philipp SchneiderPODC 2024 Invited to the special issue of Distributed Computing▸ ArXiv version▸ Conference versionFast broadcast in highly connected networks
with Shashwat Chandra, Michal Dory, Mohsen Ghaffari and Dean LeitersdorfSPAA 2024▸ ArXiv version▸ Conference versionThe distributed complexity of locally checkable labeling problems beyond paths and trees
ITCS 2024▸ ArXiv version▸ Conference versionFully scalable massively parallel algorithms for embedded planar graphs
with Da Wei ZhengSODA 2024▸ ArXiv version▸ Conference versionOrtho-radial drawing in near-linear time
ICALP 2023▸ ArXiv version▸ Conference version▸ Journal versionEfficient distributed decomposition and routing algorithms in minor-free networks and their applications
PODC 2023▸ ArXiv version▸ Conference version▸ Journal versionThe complexity of distributed approximation of packing and covering integer linear programs
with Zeyong LiPODC 2023▸ ArXiv version▸ Conference versionThe energy complexity of diameter and minimum cut computation in bounded-genus networks
SIROCCO 2023Invited to the special issue of Theoretical Computer Science▸ ArXiv version▸ Conference version▸ Journal versionEfficient classification of locally checkable problems in regular trees
with Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený and Jukka SuomelaDISC 2022▸ ArXiv version▸ Conference versionNarrowing the LOCAL–CONGEST gaps in sparse networks via expander decompositions
with Hsin-Hao SuPODC 2022Invited to the special issue of Distributed Computing▸ ArXiv version▸ Conference version▸ Journal versionThe energy complexity of Las Vegas leader election
with Shunhua JiangSPAA 2022▸ ArXiv version▸ Conference versionLocal problems on trees from the perspectives of distributed algorithms, finitary factors, and descriptive combinatorics
with Sebastian Brandt, Jan Grebík, Christoph Grunau, Václav Rozhoň and Zoltán VidnyánszkyITCS 2022▸ ArXiv version▸ Conference versionStrong-diameter network decomposition
with Mohsen GhaffariPODC 2021▸ ArXiv version▸ Conference versionNear-optimal time-energy trade-offs for deterministic leader election
with Ran Duan and Shunhua JiangSPAA 2021▸ ArXiv version▸ Conference version▸ Journal versionDistributed graph problems through an automata-theoretic lens
with Jan Studený and Jukka SuomelaSIROCCO 2021Invited to the special issue of Theoretical Computer Science▸ ArXiv version▸ Conference version▸ Journal versionTight distributed listing of cliques
with Keren Censor-Hillel, François Le Gall and Dean LeitersdorfSODA 2021▸ ArXiv version▸ Conference versionDeterministic distributed expander decomposition and routing with applications in distributed derandomization
with Thatchaphol SaranurakFOCS 2020 ▸ ArXiv version ▸ Conference versionThe complexity landscape of distributed locally checkable problems on trees
DISC 2020▸ ArXiv version ▸ Conference versionThe energy complexity of BFS in radio networks
with Varsha Dani, Thomas P. Hayes and Seth PettiePODC 2020▸ ArXiv version ▸ Conference versionStreaming complexity of spanning tree computation
with Martín Farach-Colton, Tsan-Sheng Hsu and Meng-Tsung TsaiSTACS 2020▸ ArXiv version ▸ Conference versionImproved distributed expander decomposition and nearly optimal triangle enumeration
with Thatchaphol SaranurakPODC 2019 Best Paper AwardInvited to the special issue of Journal of the ACMInvited to Highlights of Algorithms 2020▸ ArXiv version ▸ Conference version▸ Journal versionThe complexity of (Δ+1) coloring in congested clique, massively parallel computation, and centralized local computation
with Manuela Fischer, Mohsen Ghaffari, Jara Uitto and Yufan ZhengPODC 2019 Best Student Paper AwardInvited to the special issue of Distributed Computing▸ ArXiv version ▸ Conference versionThe distributed complexity of locally checkable problems on paths is decidable
with Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Mikaël Rabie and Jukka SuomelaPODC 2019▸ ArXiv version ▸ Conference versionSimple contention resolution via multiplicative weight updates
with Wenyu Jin and Seth Pettie SOSA 2019▸ Conference versionDistributed triangle detection via expander decomposition
with Seth Pettie and Hengjie ZhangSODA 2019▸ ArXiv version ▸ Conference version▸ Journal versionThe energy complexity of broadcast
with Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li and Seth PettiePODC 2018▸ ArXiv version ▸ Conference versionAn optimal distributed (Δ+1)-coloring algorithm?
with Wenzheng Li and Seth PettieSTOC 2018▸ ArXiv version▸ Conference version▸ Journal versionThe complexity of distributed edge coloring with small palettes
with Qizheng He, Wenzheng Li, Seth Pettie and Jara UittoSODA 2018▸ ArXiv version ▸ Conference version▸ Journal versionA time hierarchy theorem for the LOCAL model
with Seth PettieFOCS 2017Invited to Highlights of Algorithms 2018▸ ArXiv version▸ Conference version ▸ Journal versionUnfolding some classes of orthogonal polyhedra of arbitrary genus
with Kuan-Yi Ho and Hsu-Chun YenCOCOON 2017Invited to the special issue of Journal of Combinatorial Optimization▸ Conference version ▸ Journal versionOn bend-minimized orthogonal drawings of planar 3-graphs
with Hsu-Chun YenSoCG 2017▸ Conference versionExponential separations in the energy complexity of leader election
with Tsvi Kopelowitz, Seth Pettie, Ruosong Wang and Wei ZhanSTOC 2017▸ ArXiv version▸ Conference version ▸ Journal versionAn exponential separation between randomized and deterministic complexity in the LOCAL model
with Tsvi Kopelowitz and Seth PettieFOCS 2016▸ ArXiv version▸ Conference version ▸ Journal versionHardness of RNA folding problem with four symbols
CPM 2016▸ ArXiv version▸ Conference version ▸ Journal versionUnfolding orthogonal polyhedra with linear refinement
with Hsu-Chun YenISAAC 2015Invited to the special issue of International Journal of Computational Geometry and Applications▸ Conference version ▸ Journal versionA new approach for contact graph representations and its applications
with Hsu-Chun YenWADS 2015▸ Conference versionRectilinear duals using monotone staircase polygons
with Hsu-Chun YenCOCOA 2014Invited to the special issue of Theoretical Computer Science▸ Conference version ▸ Journal versionOn orthogonally convex drawings of plane graphs
with Hsu-Chun YenGD 2013▸ Conference version ▸ Journal versionJournal papers
Efficient distributed decomposition and routing algorithms in minor-free networks and their applications
ACM Transactions on Algorithms 2026▸ LinkNon-uniform content-oblivious leader election in 2-edge-connected networks
with Jérémie Chalopin, Lyuting Chen, Giuseppe A. Di Luna and Haoran ZhouDistributed Computing 2026▸ LinkImproved all-pairs approximate shortest paths in congested clique
with Hong Duc Bui, Shashwat Chandra, Michal Dory and Dean LeitersdorfDistributed Computing 2026▸ LinkNarrowing the LOCAL–CONGEST gaps in sparse networks via expander decompositions
with Hsin-Hao SuDistributed Computing 2026▸ LinkOrtho-radial drawing in near-linear time
TheoretiCS 2025▸ LinkOn homomorphism graphs
with Sebastian Brandt, Jan Grebík, Christoph Grunau, Václav Rozhoň and Zoltán VidnyánszkyForum of Mathematics, Pi 2024▸ LinkThe energy complexity of diameter and minimum cut computation in bounded-genus networks
Theoretical Computer Science 2024▸ LinkNear-optimal time–energy tradeoffs for deterministic leader election
with Ran Duan and Shunhua JiangACM Transactions on Algorithms 2023▸ LinkLocally checkable problems in rooted trees
with Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela and Aleksandr TereshchenkoDistributed Computing 2023▸ LinkDistributed graph problems through an automata-theoretic lens
with Jan Studený and Jukka SuomelaTheoretical Computer Science 2023▸ LinkNear-optimal distributed triangle enumeration via expander decompositions
with Seth Pettie, Thatchaphol Saranurak and Hengjie ZhangJournal of the ACM 2021▸ LinkDistributed (Δ+1)-coloring via ultrafast graph shattering
with Wenzheng Li and Seth PettieSIAM Journal on Computing 2020▸ LinkA time hierarchy theorem for the LOCAL model
with Seth PettieSIAM Journal on Computing 2019▸ LinkAn exponential separation between randomized and deterministic complexity in the LOCAL model
with Tsvi Kopelowitz and Seth PettieSIAM Journal on Computing 2019▸ LinkDistributed edge coloring and a special case of the constructive Lovász local lemma
with Qizheng He, Wenzheng Li, Seth Pettie and Jara UittoACM Transactions on Algorithms 2019▸ LinkExponential separations in the energy complexity of leader election
with Tsvi Kopelowitz, Seth Pettie, Ruosong Wang and Wei ZhanACM Transactions on Algorithms 2019▸ LinkHardness of RNA folding problem with four symbols
Theoretical Computer Science 2019▸ LinkUnfolding some classes of orthogonal polyhedra of arbitrary genus
with Kuan-Yi Ho and Hsu-Chun YenJournal of Combinatorial Optimization 2019▸ LinkArea-universal drawings of biconnected outerplane graphs
with Hsu-Chun YenInformation Processing Letters 2017▸ LinkImproved algorithms for grid-unfolding orthogonal polyhedra
with Hsu-Chun YenInternational Journal of Computational Geometry and Applications 2017▸ LinkOn orthogonally convex drawings of plane graphs
with Hsu-Chun YenComputational Geometry 2017▸ LinkConstrained floorplans in 2D and 3D
with Hsu-Chun YenTheoretical Computer Science 2015▸ Link