86 citations · 243 across the 39 of their papers we have counts for
4 papers · 1 filter
Simpler and Better Cardinality Estimators for HyperLogLog and PCSA
Seth Pettie, Dingyu Wang
\emph{Cardinality Estimation} (aka \emph{Distinct Elements}) is a classic problem in sketching with many industrial applications. Although sketching \emph{algorithms} are fairly si…
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 […
Space Complexity of Vertex Connectivity Oracles
Seth Pettie, Thatchaphol Saranurak, Longhui Yin
A -vertex connectivity oracle for undirected is a data structure that, given , reports , where is the pairwise vertex connectivity be…