3 papers
cs.DS2026
Strengths and Limitations of Greedy in Cup Games
Kalina JasiÅska, John Kuszmaul, Gyudong Lee
In the cup game, an adversary distributes 1 unit of water among cups every time step. The player then selects a single cup from which to remove 1 unit of water. In the bamboo t…
cs.DS2026
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…
cs.DC2025
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…