
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
We study connections between distributed local algorithms, finitary fact...
read it

NearOptimal TimeEnergy TradeOffs for Deterministic Leader Election
We consider the energy complexity of the leader election problem in the ...
read it

StrongDiameter Network Decomposition
Network decomposition is a central concept in the study of distributed g...
read it

Tight Distributed Listing of Cliques
Much progress has recently been made in understanding the complexity lan...
read it

The Complexity Landscape of Distributed Locally Checkable Problems on Trees
Recent research revealed the existence of gaps in the complexity landsca...
read it

Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
There is a recent exciting line of work in distributed graph algorithms ...
read it

The Energy Complexity of BFS in Radio Networks
We consider a model of energy complexity in Radio Networks in which tran...
read it

Distributed graph problems through an automatatheoretic lens
We study the following algorithm synthesis question: given the descripti...
read it

Streaming Complexity of Spanning Tree Computation
The semistreaming model is a variant of the streaming model frequently ...
read it

Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
An (ϵ,ϕ)expander decomposition of a graph G=(V,E) is a clustering of th...
read it

The distributed complexity of locally checkable problems on paths is decidable
Consider a computer network that consists of a path with n nodes. The no...
read it

Distributed Triangle Detection via Expander Decomposition
We present improved distributed algorithms for triangle detection and it...
read it

Energy Complexity of Distance Computation in Multihop Networks
Energy efficiency is a critical issue for wireless devices operated unde...
read it

An Optimal Distributed (Δ+1)Coloring Algorithm?
Vertex coloring is one of the classic symmetry breaking problems studied...
read it
YiJun Chang
is this you? claim profile