Yi-Jun Chang


I am an assistant professor in the Department of Computer Science at the National University of Singapore. I received the NUS Presidential Young Professorship. Previously, I was a junior fellow in the Institute for Theoretical Studies at ETH Zurich, where I was also in the research group of Mohsen Ghaffari. I received my Ph.D. in Computer Science and Engineering from the University of Michigan in 2019 under the guidance of Seth Pettie.

I am broadly interested in theoretical computer science, with a focus on the design and analysis of distributed, parallel, and sublinear graph algorithms. I received the best paper award and the best student paper award at PODC 2019. My doctoral dissertation received the 2020 ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award.

I have open positions for Ph.D. students and postdoctoral researchers.


Google ScholarDBLPORCID: 0000-0002-0109-2432

Education

Ph.D., University of Michigan (2015-2019) Advisor: Seth Pettie

M.S., National Taiwan University (2013-2015) Advisor: Hsu-Chun Yen

B.S., National Taiwan University (2009-2013)

Teaching

CS6234 Advanced Algorithms (Fall 2022)

CS5330 Randomized Algorithms (Spring 2022)

Contact

Office:

COM3-02-24, 11 Research Link, Singapore 119391

Email:

cyijun@nus.edu.sgcyijun@umich.edu

Conference Papers

Efficient classification of locally checkable problems in regular trees

with Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený and Jukka SuomelaDISC 2022ArXiv 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 version

Distributed graph problems through an automata-theoretic lens

with Jan Studený and Jukka SuomelaSIROCCO 2021ArXiv versionConference 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 2019ArXiv version Conference 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 2019ArXiv 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 versionJournal 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

Locally checkable problems in rooted trees

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

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