5 papers · 1 filter
With Leverage, the Gambler is Not the One Who Gets Ruined
William Kuszmaul
In this note we explore the following simple question: How does the classic \emph{gambler's ruin} phenomenon change if we allow the gambler \emph{financial leverage}? We show that,…
Dynamic and Optimal Function Inversion in the Small-Time Regime
John Kuszmaul, William Kuszmaul
The classic function-inversion problem considers the task of constructing a data structure which, given access to a constant-time oracle for a function , s…
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…
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 -bit key/value pairs, offer? Past work on this q…
Balanced Allocations: The Heavily Loaded Case with Deletions
Nikhil Bansal, William Kuszmaul
In the 2-choice allocation problem, balls are placed into bins, and each ball must choose between two random bins that it has been assigned to. It has been k…