86 citations · 243 across the 39 of their papers we have counts for
29 papers · 1 filter
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 …
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…
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…
Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks
Varsha Dani, Aayush Gupta, Thomas P. Hayes +1
We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for suc…
The Structure of Minimum Vertex Cuts
Seth Pettie, Longhui Yin
In this paper we continue a long line of work on representing the cut structure of graphs. We classify the types minimum vertex cuts, and the possible relationships between multipl…
Non-Mergeable Sketching for Cardinality Estimation
Seth Pettie, Dingyu Wang, Longhui Yin
Cardinality estimation is perhaps the simplest non-trivial statistical problem that can be solved via sketching. Industrially-deployed sketches like HyperLogLog, MinHash, and PCSA…
The Energy Complexity of BFS in Radio Networks
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes +1
We consider a model of energy complexity in Radio Networks in which transmitting or listening on the channel costs one unit of energy and computation is free. This simplified model…
Planar Distance Oracles with Better Time-Space Tradeoffs
Yaowei Long, Seth Pettie
In a recent breakthrough, Charalampopoulos, Gawrychowski, Mozes, and Weimann (STOC 2019) showed that exact distance queries on planar graphs could be answered in time by…
Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
Seth Pettie, Dingyu Wang
Estimating the cardinality (number of distinct elements) of a large multiset is a classic problem in streaming and sketching. In this paper we study the intrinsic tradeoff between…
Contention Resolution Without Collision Detection
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul +1
This paper focuses on the contention resolution problem on a shared communication channel that does not support collision detection. A shared communication channel is a multiple ac…
Distributed Triangle Detection via Expander Decomposition
Yi-Jun Chang, Seth Pettie, Hengjie Zhang
We present improved distributed algorithms for triangle detection and its variants in the CONGEST model. We show that Triangle Detection, Counting, and Enumeration can be solved in…
Improved bounds for multipass pairing heaps and path-balanced binary search trees
Dani Dorfman, Haim Kaplan, László Kozma +2
We revisit multipass pairing heaps and path-balanced binary search trees (BSTs), two classical algorithms for data structure maintenance. The pairing heap is a simple and efficient…
Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts
Shang-En Huang, Seth Pettie
We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for undirected graphs, as well as lower bounds on shortcut sets, which reduce t…
Approximate Generalized Matching: -Factors and -Edge Covers
Dawei Huang, Seth Pettie
In this paper we present linear time approximation schemes for several generalized matching problems on nonbipartite graphs. Our results include -time algorithms for $(1-ε)…
Thorup-Zwick Emulators are Universally Optimal Hopsets
Shang-En Huang, Seth Pettie
A - is, informally, a weighted edge set that, when added to a graph, allows one to get from point to point using a path with at most edges ("hop…
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\…
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 …
Connectivity Oracles for Graphs Subject to Vertex Failures
Ran Duan, Seth Pettie
We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. A deterministic structure processes a batch of f…
Faster Worst Case Deterministic Dynamic Connectivity
Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie +1
We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time and constant…
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
Michael Elkin, Seth Pettie
In 2001 Thorup and Zwick devised a distance oracle, which given an -vertex undirected graph and a parameter , has size . Upon a query their oracle con…
Mind the Gap
Amihood Amir, Tsvi Kopelowitz, Avivit Levy +3
We examine the complexity of the online Dictionary Matching with One Gap Problem (DMOG) which is the following. Preprocess a dictionary of patterns, where each pattern cont…
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…
Higher Lower Bounds from the 3SUM Conjecture
Tsvi Kopelowitz, Seth Pettie, Ely Porat
The 3SUM conjecture has proven to be a valuable tool for proving conditional lower bounds on dynamic data structures and graph problems. This line of work was initiated by Pǎtraşcu…