86 citations · 243 across the 39 of their papers we have counts for
46 papers
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai
We consider the problem of comparison-sorting an -permutation that avoids some -permutation . Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak prove that when …
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices
Seth Pettie, Gábor Tardos
The extremal theory of forbidden 0-1 matrices studies the asymptotic growth of the function , which is the maximum weight of a matrix wh…
Connectivity Labeling and Routing with Multiple Vertex Failures
Merav Parter, Asaf Petruschka, Seth Pettie
We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An -vertex/edge fault tolerant (-V/EFT) co…
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 […