William Kuszmaul

collaborators

3 papers

cs.DS2022

A Nearly Tight Lower Bound for the $d$ -Dimensional Cow-Path Problem

Nikhil Bansal, John Kuszmaul, William Kuszmaul

In the $d$ -dimensional cow-path problem, a cow living in $R^{d}$ must locate a $(d - 1)$ -dimensional hyperplane $H$ whose location is unknown. The only way that the cow can…

cs.DS2022

A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits

William Kuszmaul

This paper considers the basic question of how strong of a probabilistic guarantee can a hash table, storing $n$ $(1 + Θ (1)) lo g n$ -bit key/value pairs, offer? Past work on this q…

cs.DS2022

Balanced Allocations: The Heavily Loaded Case with Deletions

Nikhil Bansal, William Kuszmaul

In the 2-choice allocation problem, $m$ balls are placed into $n$ bins, and each ball must choose between two random bins $i, j \in [n]$ that it has been assigned to. It has been k…

A Nearly Tight Lower Bound for the d-Dimensional Cow-Path Problem

A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits

Balanced Allocations: The Heavily Loaded Case with Deletions

A Nearly Tight Lower Bound for the $d$ -Dimensional Cow-Path Problem