1 citations · 2 across the 6 of their papers we have counts for
6 papers
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…
Lower Bounds on Davenport-Schinzel Sequences via Rectangular Zarankiewicz Matrices
Julian Wellman, Seth Pettie
An order- Davenport-Schinzel sequence over an -letter alphabet is one avoiding immediate repetitions and alternating subsequences with length . The main problem is to de…
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
Amir Abboud, Greg Bodwin, Seth Pettie
Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say …
Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
Seth Pettie
We present a deterministic algorithm for computing the sensitivity of a minimum spanning tree (MST) or shortest path tree in time, where is the inverse-Ackerma…
Dynamic Set Intersection
Tsvi Kopelowitz, Seth Pettie, Ely Porat
Consider the problem of maintaining a family of dynamic sets subject to insertions, deletions, and set-intersection reporting queries: given , report every member of…
Connectivity Oracles for Planar Graphs
Glencora Borradaile, Seth Pettie, Christian Wulff-Nilsen
We consider dynamic subgraph connectivity problems for planar graphs. In this model there is a fixed underlying planar graph, where each edge and vertex is either "off" (failed) or…