We consider the classic 3SUM problem: given sets of integers A, B, C, determine whether there is a tuple (a, b, c) ∈ A × B × C satisfying a + b = c. The 3SUM Hypothesis, central in fine-grained complexity, states that there does not exist a truly subquadratic time 3SUM algorithm. Given this long-standing barrier, recent work over the past decade has explored 3SUM from a data structural perspective. Specifically, in the 3SUM in preprocessed universes regime, we are tasked with preprocessing sets A, B of size n, to create a space-efficient data structure that can quickly answer queries, each of which is a 3SUM problem of the form A', B', C', where A' ⊆ A and B' ⊆ B. A series of results have achieved Õ(n²) preprocessing time, Õ(n²) space, and query time improving progressively from Õ(n^{1.9}) [Timothy M. Chan and Moshe Lewenstein, 2015] to Õ(n^{11/6}) [Timothy M. Chan et al., 2023] to Õ(n^{1.5}) [Kasliwal et al., 2025]. Given these series of works improving query time, a natural open question has emerged: can one achieve both truly subquadratic space and truly subquadratic query time for 3SUM in preprocessed universes? We resolve this question affirmatively, presenting a tradeoff curve between query and space complexity. Specifically, we present a simple randomized algorithm achieving Õ(n^{1.5 + ε}) query time and Õ(n^{2 - 2ε/3}) space complexity. Furthermore, our algorithm has Õ(n²) preprocessing time, matching past work. Notably, quadratic preprocessing is likely necessary for our tradeoff as either the preprocessing or the query time must be at least n^{2-o(1)} under the 3SUM Hypothesis.

Abstract. Contention resolution addresses the problem of coordinating access to a shared communication channel. Time is discretized into synchronized slots, and a packet transmission can be made in any slot. A packet succeeds if it is the only packet transmitted during that slot. If two or more packets are sent in the same slot, then these packets collide and fail. Listening on the channel during a slot provides ternary feedback, indicating whether that slot had (0) silence, (1) a successful transmission, or (2+) noise. No other feedback or exchange of information is available to packets. Packets are (adversarially) injected into the system over time. A packet departs the system once it succeeds. The goal is to ensure all packets succeed, while optimizing throughput, which entails optimizing the fraction of successful slots. Most prior contention resolution algorithms with constant throughput require a short feedback loop, in the sense that a packet’s sending probability in slot [Formula: see text] is fully determined by its internal state at slot [Formula: see text] and the channel feedback at slot [Formula: see text]. This paper answers the question of whether these short feedback loops are necessary; that is, how often must listening and updating occur in order to achieve constant throughput? A shared channel can also suffer random or adversarial noise (modeled as jamming), even when no packets are actually sent. How does noise affect our goal of long feedback loops/energy efficiency? Tying these questions together, we ask the following: What does a contention-resolution algorithm have to sacrifice to reduce channel accesses? Must we give up on constant throughput? What about robustness to noise? Here, we show that we need not concede anything by presenting an algorithm with the following guarantees. Suppose there are [Formula: see text] packets arriving over time and [Formula: see text] jammed slots, where the input is determined by an adaptive adversary. With high probability in [Formula: see text], our algorithm guarantees [Formula: see text] throughput and [Formula: see text] channel accesses (sends or listens) per packet. We also have analogous guarantees when the input stream is infinite—we prove implicit throughput bounds of [Formula: see text] for all time slots [Formula: see text], and this translates to [Formula: see text] guaranteed throughput for any slot [Formula: see text] where the implicit throughput is sufficiently small in [Formula: see text]. As a special case, these throughput results give rise to adversarial-queuing theory guarantees.

Contention resolution addresses the problem of coordinating access to a shared communication channel. Time is discretized into synchronized slots, and a packet transmission can be made in any slot. A packet is successfully sent if no other packet is also transmitted during that slot. If two or more packets are sent in the same slot, then these packets collide and fail. Listening on the channel during a slot provides ternary feedback, indicating whether that slot had (0) silence, (1) a successful transmission, or (2+) noise. No other feedback or exchange of information is available to packets. Packets are (adversarially) injected into the system over time. A packet departs the system once it is successfully sent. The goal is to send all packets while optimizing throughput, which is roughly the fraction of successful slots.

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 wireless device to transmit successfully, it uses a backoff protocol to ensure exclusive access to the channel. Modern radios, however, do not need exclusive access to the channel to communicate; in particular, they have the ability to receive useful information even when more than one device transmits at the same time. These capabilities have now been exploited for many years by systems that rely on interference cancellation, physical layer network coding and analog network coding to improve efficiency. For example, Zigzag decoding [56] demonstrated how a base station can decode messages sent by multiple devices simultaneously.

The bamboo trimming problem considers n bamboo with growth rates h1, 2, . . . , satisfying Σihi = 1. During a given unit of time, each bamboo grows by hi , and then the bamboo-trimming algorithm gets to trim one of the bamboo back down to height zero. The goal is to minimize the height of the tallest bamboo, also known as the backlog. The bamboo trimming problem is closely related to many scheduling problems, and can be viewed as a variation of the widely-studied fixed-rate cup game, but with constant-factor resource augmentation.

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 hash tables offer the following guarantee: If keys/values are Θ(logn) bits each, then it is possible to achieve constant-time insertions/deletions/queries while wasting only O(loglogn) bits of space per key when compared to the information-theoretic optimum—this bound has been proven to be optimal for a number of closely related problems (e.g., stable hashing, dynamic retrieval, and dynamically-resized filters).