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 ScholarDBLPORCID: 0000-0002-0109-2432

Program committees: 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 Award

M.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 119391

Email:

cyijun@nus.edu.sgcyijun@umich.edu   

Conference papers

The distributed complexity of locally checkable labeling problems beyond paths and trees

ITCS 2024ArXiv versionConference version

Fully scalable massively parallel algorithms for embedded planar graphs

with Da Wei ZhengSODA 2024ArXiv versionConference version

Ortho-radial drawing in near-linear time

ICALP 2023ArXiv versionConference version

Efficient distributed decomposition and routing algorithms in minor-free networks and their applications

PODC 2023ArXiv versionConference version

The complexity of distributed approximation of packing and covering integer linear programs

with Zeyong LiPODC 2023ArXiv versionConference version

The energy complexity of diameter and minimum cut computation in bounded-genus networks

SIROCCO 2023ArXiv versionConference versionJournal version 

Efficient classification of locally checkable problems in regular trees

with Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený and Jukka SuomelaDISC 2022ArXiv versionConference version

Narrowing the LOCAL–CONGEST gaps in sparse networks via expander decompositions

with Hsin-Hao SuPODC 2022ArXiv versionConference version

The energy complexity of Las Vegas leader election

with Shunhua JiangSPAA 2022ArXiv versionConference version

Local 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 2022ArXiv versionConference version

Strong-diameter network decomposition

with Mohsen GhaffariPODC 2021ArXiv versionConference version

Near-optimal time-energy trade-offs for deterministic leader election

with Ran Duan and Shunhua JiangSPAA 2021ArXiv versionConference versionJournal version

Distributed graph problems through an automata-theoretic lens

with Jan Studený and Jukka SuomelaSIROCCO 2021ArXiv versionConference versionJournal version

Tight distributed listing of cliques

with Keren Censor-Hillel, François Le Gall and Dean LeitersdorfSODA 2021ArXiv versionConference version

Deterministic distributed expander decomposition and routing with applications in distributed derandomization

with Thatchaphol SaranurakFOCS 2020  ArXiv version Conference version

The complexity landscape of distributed locally checkable problems on trees

DISC 2020ArXiv version Conference version

The energy complexity of BFS in radio networks 

with Varsha Dani, Thomas P. Hayes and Seth PettiePODC 2020ArXiv version Conference version

Streaming complexity of spanning tree computation

with Martín Farach-Colton, Tsan-Sheng Hsu and Meng-Tsung TsaiSTACS 2020ArXiv version Conference version 

Improved distributed expander decomposition and nearly optimal triangle enumeration

with Thatchaphol SaranurakPODC 2019 Best Paper AwardArXiv version Conference versionJournal version 

The 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 AwardArXiv version  Conference version

The distributed complexity of locally checkable problems on paths is decidable 

with Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Mikaël Rabie and Jukka SuomelaPODC 2019ArXiv version Conference version

Simple contention resolution via multiplicative weight updates

with Wenyu Jin and Seth Pettie SOSA 2019Conference version 

Distributed triangle detection via expander decomposition

with Seth Pettie and Hengjie ZhangSODA 2019ArXiv version Conference versionJournal version 

The energy complexity of broadcast

with Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li and Seth PettiePODC 2018ArXiv version Conference version

An optimal distributed (Δ+1)-coloring algorithm?

with Wenzheng Li and Seth PettieSTOC 2018ArXiv versionConference versionJournal version 

The complexity of distributed edge coloring with small palettes

with Qizheng He, Wenzheng Li, Seth Pettie and Jara UittoSODA 2018ArXiv version Conference versionJournal version 

A time hierarchy theorem for the LOCAL model

with Seth PettieFOCS 2017Arxiv versionConference version Journal version 

Unfolding some classes of orthogonal polyhedra of arbitrary genus

with Kuan-Yi Ho and Hsu-Chun YenCOCOON 2017Conference version Journal version 

On bend-minimized orthogonal drawings of planar 3-graphs

with Hsu-Chun YenSoCG 2017Conference version

Exponential separations in the energy complexity of leader election

with Tsvi Kopelowitz, Seth Pettie, Ruosong Wang and Wei ZhanSTOC 2017ArXiv versionConference version Journal version 

An exponential separation between randomized and deterministic complexity in the LOCAL model

with Tsvi Kopelowitz and Seth PettieFOCS 2016Arxiv versionConference version Journal version 

Hardness of RNA folding problem with four symbols

CPM 2016Arxiv versionConference version Journal version 

Unfolding orthogonal polyhedra with linear refinement

with Hsu-Chun YenISAAC 2015Conference version Journal version 

A new approach for contact graph representations and its applications

with Hsu-Chun YenWADS 2015Conference version 

Rectilinear duals using monotone staircase polygons

with Hsu-Chun YenCOCOA 2014Conference version Journal version 

On orthogonally convex drawings of plane graphs

with Hsu-Chun YenGD 2013Conference version Journal version 

Journal papers

The energy complexity of diameter and minimum cut computation in bounded-genus networks

Theoretical Computer Science 2024Link 

Near-optimal time-energy trade-offs for deterministic leader election

with Ran Duan and Shunhua JiangACM Transactions on Algorithms 2023Link

Locally checkable problems in rooted trees

with Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela and Aleksandr TereshchenkoDistributed Computing 2023Link

Distributed graph problems through an automata-theoretic lens

with  Jan Studený and Jukka SuomelaTheoretical Computer Science 2023Link

Near-optimal distributed triangle enumeration via expander decompositions

with Seth Pettie, Thatchaphol Saranurak and Hengjie ZhangJournal of the ACM 2021Link 

Distributed (Δ+1)-coloring via ultrafast graph shattering

with Wenzheng Li and Seth PettieSIAM Journal on Computing 2020Link 

A time hierarchy theorem for the LOCAL model

with Seth PettieSIAM Journal on Computing 2019Link 

An exponential separation between randomized and deterministic complexity in the LOCAL model

with Tsvi Kopelowitz and Seth PettieSIAM Journal on Computing 2019Link 

Distributed 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 2019Link 

Exponential separations in the energy complexity of leader election

with Tsvi Kopelowitz, Seth Pettie, Ruosong Wang and Wei ZhanACM Transactions on Algorithms 2019Link 

Hardness of RNA folding problem with four symbols

Theoretical Computer Science 2019Link

Unfolding some classes of orthogonal polyhedra of arbitrary genus

with Kuan-Yi Ho and Hsu-Chun YenJournal of Combinatorial Optimization 2019Link 

Area-universal drawings of biconnected outerplane graphs

with Hsu-Chun YenInformation Processing Letters 2017Link 

Improved algorithms for grid-unfolding orthogonal polyhedra

with Hsu-Chun YenInternational Journal of Computational Geometry and Applications 2017Link 

On orthogonally convex drawings of plane graphs

with Hsu-Chun YenComputational Geometry 2017Link 

Constrained floorplans in 2D and 3D

with Hsu-Chun YenTheoretical Computer Science 2015Link