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: 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 (Fall 2022 and Fall 2023)
CS5330 Randomized Algorithms (Spring 2022, Spring 2023 and Spring 2024)
Open positions
I have openings for Ph.D. students and postdoctoral researchers.
Postdoctoral researchers receive a monthly salary of 8000 SGD without any teaching duties.
Current and former postdoctoral researchers:
Gopinath Mishra (9/2023–current)Dean Leitersdorf (11/2022–5/2023)Contact
Office:
▸COM3-02-24, 11 Research Link, Singapore 119391Email:
▸cyijun@nus.edu.sg▸cyijun@umich.eduConference papers
A 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▸ ArXiv version▸ Conference versionUniversally optimal information dissemination and shortest paths in the HYBRID distributed model
with Oren Hecht, Dean Leitersdorf and Philipp SchneiderPODC 2024▸ 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 versionEfficient distributed decomposition and routing algorithms in minor-free networks and their applications
PODC 2023▸ ArXiv version▸ Conference 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 2023▸ 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 2022▸ ArXiv version▸ Conference 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 2021▸ 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 Award▸ 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 Award▸ 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 2017▸ ArXiv version▸ Conference version ▸ Journal versionUnfolding some classes of orthogonal polyhedra of arbitrary genus
with Kuan-Yi Ho and Hsu-Chun YenCOCOON 2017▸ 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 2015▸ 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 2014▸ Conference version ▸ Journal versionOn orthogonally convex drawings of plane graphs
with Hsu-Chun YenGD 2013▸ Conference version ▸ Journal versionJournal papers
On 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