2 papers
cs.DS2022
A Nearly Tight Lower Bound for the -Dimensional Cow-Path Problem
Nikhil Bansal, John Kuszmaul, William Kuszmaul
In the -dimensional cow-path problem, a cow living in must locate a -dimensional hyperplane whose location is unknown. The only way that the cow can…
cs.DS2021
On the Optimal Time/Space Tradeoff for Hash Tables
Michael A. Bender, Martín Farach-Colton, John Kuszmaul +2
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 h…