7 papers
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…
Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven
Ran Ben-Basat, William Kuszmaul, Michael Mitzenmacher +2
Uniform random rotations (URRs) are a common preprocessing step in modern quantization approaches used for gradient compression, inference acceleration, KV-cache compression, model…
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…
Signed Enumeration of Upper-Right Corners in Path Shuffles
William Kuszmaul
We resolve a conjecture of Albert and Bousquet-Melou enumerating quarter-plane walks with fixed horizontal and vertical projections according to their upper-right-corner count modu…