4 citations · 7 across the 8 of their papers we have counts for
9 papers
When Shall We Meet Again? Tight Algorithms for Diameter and Radius under the Meet Distance
Yael Kirkpatrick, John Kuszmaul, Merey Temirzinova +1
Finding an optimal meeting point for a collection of agents on a directed graph is a classical problem studied in the context of network analysis, operations research and computati…
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…
The Semi-Oblivious Cup Game: an Imperfect Information Setting
Kalina Jasińska, John Kuszmaul, Gyudong Lee
In the cup game, an adversary distributes unit of water among initially empty cups during each time step. The player then selects a single cup from which to remove up to $1…
Preprocessed 3SUM for Unknown Universes with Subquadratic Space
Yael Kirkpatrick, John Kuszmaul, Surya Mathialagan +1
We consider the classic 3SUM problem: given sets of integers , determine whether there is a tuple satisfying . The 3SUM…
Fully Energy-Efficient Randomized Backoff: Slow Feedback Loops Yield Fast Contention Resolution
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert +2
Contention resolution addresses the problem of coordinating access to a shared channel. Time proceeds in slots, and a packet transmission can be made in any slot. A packet is succe…
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…
Contention Resolution for Coded Radio Networks
Michael A. Bender, Seth Gilbert, Fabian Kuhn +2
Randomized backoff protocols, such as exponential backoff, are a powerful tool for managing access to a shared resource, often a wireless communication channel (e.g., [1]). For a w…
Bamboo Trimming Revisited: Simple Algorithms Can Do Well Too
John Kuszmaul
The bamboo trimming problem considers bamboo with growth rates satisfying . During a given unit of time, each bamboo grows by , and…
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…