86 citations · 243 across the 39 of their papers we have counts for
9 papers · 1 filter
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
Shang-En Huang, Seth Pettie, Leqi Zhu
Since the mid-1980s it has been known that Byzantine Agreement can be solved with probability 1 asynchronously, even against an omniscient, computationally unbounded adversary that…
Byzantine Agreement in Polynomial Time with Near-Optimal Resilience
Shang-En Huang, Seth Pettie, Leqi Zhu
It has been known since the early 1980s that Byzantine Agreement in the full information, asynchronous model is impossible to solve deterministically against even one crash fault […
An Optimal Distributed -Coloring Algorithm?
Yi-Jun Chang, Wenzheng Li, Seth Pettie
Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for -list coloring in the randomi…
The Energy Complexity of Broadcast
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes +3
Energy is often the most constrained resource in networks of battery-powered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (…
Distributed Edge Coloring with Small Palettes and a Special Case of the Constructive Lovász Local Lemma
Yi-Jun Chang, Qizheng He, Wenzheng Li +2
We explore the complexity of edge coloring in the LOCAL model in different palette size regimes. 1. Lower Bounds: First, we simplify the round elimination technique of Brandt et al…
A Time Hierarchy Theorem for the LOCAL Model
Yi-Jun Chang, Seth Pettie
The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem ho…
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…
A Resource-Competitive Jamming Defense
Valerie King, Seth Pettie, Jared Saia +1
Consider a scenario where Alice wishes to send a message to Bob in a time-slotted wireless network. However, there exists an adversary, Carol, who aims to prevent the transmiss…
The Locality of Distributed Symmetry Breaking
Leonid Barenboim, Michael Elkin, Seth Pettie +1
Symmetry breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this…