6 papers
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 to find an open slot in the table. As special cases this subsumes li…
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…
The Greedy Binary Search Tree is Non-trivially Competitive
Yuhao Guo, Seth Pettie, Daniel Skora +1
We prove that the binary search tree is -competitive. It is widely conjectured that is -competitive, but before…
Contention Resolution, With and Without a Global Clock
Zixi Cai, Kuowen Chen, Shengquan Du +3
In the Contention Resolution problem parties each wish to have exclusive use of a shared resource for one unit of time. The problem has been studied since the early 1970s, unde…
The Squishy Grid Problem
Zixi Cai, Kuowen Chen, Shengquan Du +3
In this paper we consider the problem of approximating Euclidean distances by the infinite integer grid graph. Although the topology of the graph is fixed, we have control over the…
A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem
Seth Pettie, Dingyu Wang
In the -dimensional turnstile streaming model, a frequency vector is updated entry-wisely over a stream. We…