18 citations · 79 across the 27 of their papers we have counts for
3 papers · 1 filter
Exponential Separations in the Energy Complexity of Leader Election
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie +2
Energy is often the most constrained resource for battery-powered wireless devices and the lion's share of energy is often spent on transceiver usage (sending/receiving packets), n…
Fully Dynamic Connectivity in Amortized Expected Time
Shang-En Huang, Dawei Huang, Tsvi Kopelowitz +2
Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a randomized Las Vegas dynamic connectivity data structure with $O(\log n(\log\…
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie
Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring.…