5 papers
Energy-Efficient Aggregation and Minimum-Degree Spanning Trees in Radio Networks
Yi-Jun Chang, Yang Ze Guan
We study the aggregation problem in synchronous multi-hop radio networks with -bit messages and no collision detection. Each node initially holds a value, and the goal i…
Efficient Counting and Simulation in Content-Oblivious Rings
Jérémie Chalopin, Yi-Jun Chang, Giuseppe Antonio Di Luna +1
In the content-oblivious (CO) model (proposed by Censor-Hillel et al.), processes inhabit an asynchronous network and communicate only by exchanging pulses. A series of works has c…
The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees
Yi-Jun Chang
We consider locally checkable labeling LCL problems in the LOCAL model of distributed computing. Since 2016, there has been a substantial body of work examining the possible comple…
Deterministic Distributed Algorithms and Measurable Combinatorics on -Regular Forests
Sebastian Brandt, Yi-Jun Chang, Jan Grebík +3
We investigate the connections between the fields of distributed computing and measurable combinatorics by considering complexity classes of locally checkable labeling problems on…
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
Sebastian Brandt, Yi-Jun Chang, Jan Grebík +3
We study connections between distributed local algorithms, finitary factors of iid processes, and descriptive combinatorics in the context of regular trees. We extend the Borel det…