Seth Pettie

activity

20242026

collaborators

Showing cs.DSShow all

4 papers · 1 filter

cs.DS2026

A Sharp Analysis of Fixed Offset Hash Tables

Yuhao Guo, Seth Pettie, Chengzhang Wan

We consider the class of open addressing hash tables that uses a fixed offset sequence $r_{0}, r_{1}, \dots, r_{n - 1}$ to find an open slot in the table. As special cases this subsumes li…

cs.DS2026

A Simple Analysis of Quadratic Probing and Other Open Addressing Schemes

Yuhao Guo, Seth Pettie, Chengzhang Wan

In open addressed hashing, quadratic probing is attractive for striking a nice balance between having a high locality of reference and a low number of probes per search. However, t…

cs.DS2026

The Greedy Binary Search Tree is Non-trivially Competitive

Yuhao Guo, Seth Pettie, Daniel Skora +1

We prove that the $Greedy$ binary search tree is $2^{O (l o g l o g n)}$ -competitive. It is widely conjectured that $Greedy$ is $O (1)$ -competitive, but before…

cs.DS2024

A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem

Seth Pettie, Dingyu Wang

In the $d$ -dimensional turnstile streaming model, a frequency vector $x = (x (1), \dots, x (n)) \in (R^{d})^{n}$ is updated entry-wisely over a stream. We…