10 citations · 26 across the 8 of their papers we have counts for
8 papers · 1 filter
The Energy Complexity of Las Vegas Leader Election
Yi-Jun Chang, Shunhua Jiang
We consider the time and energy complexities of randomized leader election in a multiple-access channel, where the number of devices is unknown. It is well-known that for…
Strong-Diameter Network Decomposition
Yi-Jun Chang, Mohsen Ghaffari
Network decomposition is a central concept in the study of distributed graph algorithms. We present the first polylogarithmic-round deterministic distributed algorithm with small m…
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
Yi-Jun Chang, Thatchaphol Saranurak
There is a recent exciting line of work in distributed graph algorithms in the model that exploit expanders. All these algorithms so far are based on two tools:…
The Energy Complexity of BFS in Radio Networks
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes +1
We consider a model of energy complexity in Radio Networks in which transmitting or listening on the channel costs one unit of energy and computation is free. This simplified model…
Streaming Complexity of Spanning Tree Computation
Yi-Jun Chang, Martin Farach-Colton, Tsan-Sheng Hsu +1
The semi-streaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an -node input graph to be read sequen…
Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
Yi-Jun Chang, Thatchaphol Saranurak
An -expander decomposition of a graph is a clustering of the vertices such that (1) each cluster induces subgraph with conduc…