Researcher profile
Martı́n Farach-Colton
3 papers in the PaperMetrix corpus
Publications
Papers by this author
-
Write-Optimized Skip Lists
2017
The skip list is an elegant dictionary data structure that is commonly deployed in RAM. A skip list with N elements supports searches, inserts, and deletes in O(log N) operations with high probability (w.h.p.) and …
-
All-Purpose Hashing
2021 · arXiv (Cornell University)
Despite being one of the oldest data structures in computer science, hash tables continue to be the focus of a great deal of both theoretical and empirical research. A central reason for this is that …
-
On the Optimal Time/Space Tradeoff for Hash Tables
2021 · arXiv (Cornell University)
For nearly six decades, the central open question in the study of hash tables has been to determine the optimal achievable tradeoff curve between time and space. State-of-the-art hash tables offer the following guarantee: If …