86 citations · 243 across the 39 of their papers we have counts for
6 papers · 1 filter
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…
Joins on Samples: A Theoretical Guide for Practitioners
Dawei Huang, Dong Young Yoon, Seth Pettie +1
Despite decades of research on approximate query processing (AQP), our understanding of sample-based joins has remained limited and, to some extent, even superficial. The common be…