Yi-Jun Chang

I am a junior fellow (postdoctoral position) at the ETH Institute for Theoretical Studies (ETH-​ITS).

I am also in the Discrete and Distributed Algorithms Group led by Mohsen Ghaffari.


Google ScholarDBLP

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)

My doctoral dissertation received the 2020 Principles of Distributed Computing Doctoral Dissertation Award.

Contact

yi-jun.chang@eth-its.ethz.ch (current)

cyijun@umich.edu (permanent)

Conference Papers

Strong-diameter network decomposition

with Mohsen GhaffariPODC 2021ArXiv version

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

with Ran Duan and Shunhua JiangSPAA 2021ArXiv version

Distributed graph problems through an automata-theoretic lens

with Jan Studený and Jukka SuomelaSIROCCO 2021ArXiv 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 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 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

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