We show how to construct a dynamic ordered dictionary, supporting insert/delete/rank/select on a set of \(n\) elements from a universe of size \(U\), that achieves the optimal amortized expected time complexity of \(O(1 + \log n / \log \log U)\), while achieving a nearly optimal space consumption of \(\log \binom{U}{n} + n / 2^{(\log n)^{\Omega(1)}} + \operatorname{polylog} U\) bits in the regime where \(U = \operatorname{poly}(n)\). This resolves an open question by Pibiri and Venturini as to whether a redundancy (a.k.a. space overhead) of \(o(n)\) bits is possible, and is the first dynamic solution to bypass the so-called tree-structure bottleneck, in which the bits needed to encode some dynamic tree structure are themselves enough to force a redundancy of \(\tilde{\Omega}(n)\) bits. Our main technical building block is a dynamic balanced binary search tree, which we call the compressed tabulation-weighted treap, that itself achieves a surprising time/space tradeoff. The tree supports polylog-\(n\)-time operations and requires a static lookup table of size \(\operatorname{poly}(n)+\operatorname{polylog} U\unicode{x2014}\)but, in exchange for these, the tree is able to achieve a remarkable space guarantee. Its total space redundancy is \(O(\log U)\) bits. In fact, if the tree is given \(n\) and \(U\) for free, then the redundancy further drops to \(O(1)\) bits.

In recent decades, cloud computing as a service has emerged as a major computing paradigm. These services (e.g., Amazon EC2, Google Compute Engine, Azure Virtual Machines) all offer variations of the following basic model for how storage works: a compute instance can choose between placing data on something that resembles a local disk (e.g., Amazon EBS, Google Block Store, Azure Managed Disks) versus what we will refer to as a global disk (e.g., Amazon S3, Google GCS, Azure Blob Storage). The disks are distinguished by two features:

We study the problem of constructing concurrent objects in a setting where $P$ processes run in parallel and interact through a shared memory that is subject to write contention. Our goal is to transform hardware primitives that are subject to write contention into ones that handle contention gracefully. We give contention-resolution algorithms for several basic primitives, and analyze them under a relaxed, roughly-synchronous stochastic scheduler, where processes run at roughly the same rate up to a constant factor with high probability. Specifically, we construct read/write registers and CAS registers that have latency $O(\log P)$ w.h.p. under our scheduler model, using $O(1)$ hardware read/write registers and, in the case of our CAS construction, one hardware CAS register. Our algorithms guarantee performance even when their operations are invoked by an adaptive adversary that is able to see the entire history of operations so far, including their timing and return values. This allows them to be used as building blocks inside larger programs; using this compositionality property, we obtain several other constructions (LL/SC, fetch-and-increment, bounded max registers, and counters). To complement our constructions, we give a trade-off showing that even under a perfectly synchronous schedule and even if each process only executes one operation, any algorithm that implements any of the primitives that we consider, uses space $M$, and has latency at most $L$ with high probability must have expected latency at least $Ω(\log_{ML} P)$.

In the static retrieval problem, a data structure must answer retrieval queries mapping a set of n keys in a universe $[U]$ to v-bit values. Information-theoretically, retrieval data structures can use as little as nv bits of space. For small value sizes v, it is possible to achieve $O(1)$ query time while using space $n v+o(n)$ bits-whether or not such a result is possible for larger values of v (e.g., $v=\Theta(\log n)$) has remained open.In this paper, we obtain a tight lower bound (as well as matching upper bounds) for the static retrieval problem. In the case where values are large, we show that there is actually a significant tension between time and space. It is not possible, for example, to get $O(1)$ query time using $n v+o(n)$ bits of space, when $v=\Theta(\log n)$ (and assuming the word RAM model with $O(\log n)$-bit words)At first glance, our lower bound would seem to render retrieval unusable in many settings that aim to achieve very low redundancy. However, our second result offers a way around this: We show that, whenever a retrieval data structure $D_{1}$ is stored along with another data structure $D_{2}$ (whose size is similar to or larger than the size of $D_{1}$), it is possible to implement the combined data structure $D_{1} \cup D_{2}$ so that queries to $D_{1}$ take $O(1)$ time, operations on $D_{2}$ take the same asymptotic time as if $D_{2}$ were stored on its own, and the total space is $n v+\operatorname{Space}\left(D_{2}\right)+n^{0.67}$ bits.

Dynamic filters are data structures supporting approximate membership queries to a dynamic set S of n keys, allowing a small false-positive error rate $\varepsilon$, under insertions and deletions to the set S. Essentially all known constructions for dynamic filters use a technique known as fingerprinting. This technique, which was first introduced by Carter et al. in 1978, inherently requires $\log \binom{n \varepsilon^{-1}}{n}=n \log \varepsilon^{-1}+n \log e-o(n)$ bits of space when $\varepsilon=o(1)$. Whether or not this bound is optimal for all dynamic filters (rather than just for fingerprint filters) has remained for decades as one of the central open questions in the area. We resolve this question by proving a sharp lower bound of $n \log \varepsilon^{-1}+n \log e-o(n)$ bits for $\varepsilon=o(1)$, regardless of operation time.

Fully indexable dictionaries (FID) store sets of integer keys while supporting rank/select queries. They serve as basic building blocks in many succinct data structures. Despite the great importance of FIDs, no known FID is succinct with efficient query time when the universe size U is a large polynomial in the number of keys n, which is the conventional parameter regime for dictionary problems. In this paper, we design an FID that uses log binom(U,n) + n/((log U/t)^{Ω(t)}) bits of space, and answers rank/select queries in O(t + log log n) time in the worst case, for any parameter 1 ≤ t ≤ log n / log log n, provided U = n^{1 + Θ(1)}. This time-space trade-off matches known lower bounds for FIDs [Pǎtraşcu and Thorup, 2006; Pǎtraşcu and Viola, 2010; Viola, 2023] when t ≤ log^{0.99} n. Our techniques also lead to efficient succinct data structures for the fundamental problem of maintaining n integers each of 𝓁 = Θ(log n) bits and supporting partial-sum queries, with a trade-off between O(t) query time and n𝓁 + n / (log n / t)^{Ω(t)} bits of space. Prior to this work, no known data structure for the partial-sum problem achieves constant query time with n 𝓁 + o(n) bits of space usage.

We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 2023] and [Vassilevska Williams, Xu, Xu, Zhou SODA 2024]. Surprisingly the new improvement is achieved by incorporating more asymmetry in the analysis, circumventing a fundamental tool of prior work that requires two of the three dimensions to be treated identically. The method yields a new bound on the square matrix multiplication exponent ω < 2.371339, improved from the previous bound of ω < 2.371552. We also improve the bounds of the exponents for multiplying rectangular matrices of various shapes.

Retrieval data structures are data structures that answer key-value queries without paying the space overhead of explicitly storing keys. The problem can be formulated in four settings (static, value-dynamic, incremental, or dynamic), each of which offers different levels of dynamism to the user. In this paper, we establish optimal bounds for the final two settings (incremental and dynamic) in the case of a polynomial universe. Our results complete a line of work that has spanned more than two decades, and also come with a surprise: the incremental setting, which has long been viewed as essentially equivalent to the dynamic one, actually has a phase transition, in which, as the value size v approaches log n, the optimal space redundancy actually begins to shrink, going from roughly n log log n (which has long been thought to be optimal) all the way down to Θ(n ) (which is the optimal bound even for the seemingly much-easier value-dynamic setting).

We introduce a classical open-addressed hash table, called rainbow hashing, that supports a load factor of up to 1$-\varepsilon$, while also supporting$O(1)$expected-time queries, and$O\left({\log \,\log {\varepsilon ^{ - 1}}} \right)$expected-time insertions and deletions. We further prove that this tradeoff curve is optimal: any classical open-addressed hash table that supports load factor$1-\varepsilon$must incur$\Omega \left({\log \,log{\varepsilon ^{ - 1}}} \right)$expected time per operation. Finally, we extend rainbow hashing to the setting where the hash table is dynamically resized over time. Surprisingly, the addition of dynamic resizing does not come at any time cost-even while maintaining a load factor of$\geq 1-\varepsilon$at all times, we can support$O(1)$queries and$O\left({\log \,\log {\varepsilon ^{ - 1}}} \right)$updates. Prior to our work, achieving any time bounds of the form$o(\varepsilon^{-1})$for all of insertions, deletions, and queries simultaneously remained an open Question.

Dictionaries have been one of the central questions in data structures. A dictionary data structure maintains a set of key-value pairs under insertions and deletions such that given a query key, the data structure efficiently returns its value. The state-of-the-art dictionaries [4] store n key-value pairs with only O(n log(k) n) bits of redundancy, and support all operations in O(k) time, for k ≤ log* n. It was recently shown to be optimal [16].

The main contribution of this paper is a new improved variant of the laser method for designing matrix multiplication algorithms. Building upon the recent techniques of [Duan, Wu, Zhou, FOCS 2023], the new method introduces several new ingredients that not only yield an improved bound on the matrix multiplication exponent ω, but also improve the known bounds on rectangular matrix multiplication by [Le Gall and Urrutia, SODA 2018].

In the Bidder Selection Problem (BSP) there is a large pool of n potential advertisers competing for ad slots on the user's web page. Due to strict computational restrictions, the advertising platform can run a proper auction only for a fraction k

Ranking and Balance are arguably the two most important algorithms in the online matching literature. They achieve the same optimal competitive ratio of 1-1/e for the integral version and fractional version of online bipartite matching by Karp, Vazirani, and Vazirani (STOC 1990) respectively. The two algorithms have been generalized to weighted online bipartite matching problems, including vertex-weighted online bipartite matching and AdWords, by utilizing a perturbation function. The canonical choice of the perturbation function is f(x) = 1-e^{x-1} as it leads to the optimal competitive ratio of 1-1/e in both settings. We advance the understanding of the weighted generalizations of Ranking and Balance in this paper, with a focus on studying the effect of different perturbation functions. First, we prove that the canonical perturbation function is the unique optimal perturbation function for vertex-weighted online bipartite matching. In stark contrast, all perturbation functions achieve the optimal competitive ratio of 1-1/e in the unweighted setting. Second, we prove that the generalization of Ranking to AdWords with unknown budgets using the canonical perturbation function is at most 0.624 competitive, refuting a conjecture of Vazirani (2021). More generally, as an application of the first result, we prove that no perturbation function leads to the prominent competitive ratio of 1-1/e by establishing an upper bound of 1-1/e-0.0003. Finally, we propose the online budget-additive welfare maximization problem that is intermediate between AdWords and AdWords with unknown budgets, and we design an optimal 1-1/e competitive algorithm by generalizing Balance.

Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by $\omega$. This paper discusses new ideas for improving the laser method for fast matrix multiplication. We observe that the analysis of higher powers of the Coppersmith-Winograd tensor [Coppersmith & Winograd 1990] incurs a “combination loss”, and we partially compensate for it using an asymmetric version of CW’s hashing method. By analyzing the eighth power of the CW tensor, we give a new bound of $\omega/\lt2.371866$, which improves the previous best bound of $\omega/\lt2.372860$ [Alman & Vassilevska Williams 2020]. Our result breaks the lower bound of 2.3725 in [Ambainis, Filmus & Le Gall 2015] because of the new method for analyzing component (constituent) tensors.

Augmented B-trees (aB-trees) are a broad class of data structures. The seminal work “succincter” by Pǎtraşcu [1] showed that any aB-tree can be stored using only two bits of redundancy, while supporting queries to the tree in time proportional to its depth. It has been a versatile building block for constructing succinct data structures, including rank/select data structures, dictionaries, locally decodable arithmetic coding, storing balanced parenthesis, etc.In this paper, we show how to “dynamize” an aB-tree. Our main result is the design of dynamic aB-trees (daB-trees) with branching factor two using only three bits of redundancy (with the help of lookup tables that are of negligible size in applications), while supporting updates and queries in time polynomial in its depth. As an application, we present a dynamic rank/select data structure for n-bit arrays, also known as a dynamic fully indexable dictionary (FID) [2]. It supports updates and queries in $O(\log n / \log \log n)$ time, and when the array has m ones, the \begin{equation*}\log \begin{pmatrix}n \\m\end{pmatrix}+On / 2^{\log 0.199} n\end{equation*}bits. Note that the update and query times are optimal even without space constraints due to a lower bound by Fredman and Saks [3]. Prior to our work, no dynamic FID with near-optimal update and query times and redundancy $o(n / \log n)$ was known. We further show that a dynamic sequence supporting insertions, deletions and rank/select queries can be maintained in (optimal) $O(\log n / \log \log n)$ time and with $O\left(n \cdot \operatorname{poly} \log \log n / \log ^{2} n\right)$ bits of redundancy.

A dictionary data structure maintains a set of at most n keys from the universe $[U]$ under key insertions and deletions, such that given a query $x \in[U]$, it returns if x is in the set. Some variants also store values associated to the keys such that given a query x, the value associated to x is returned when x is in the set.This fundamental data structure problem has been studied for six decades since the introduction of hash tables in 1953. A hash table occupies $O(n \log U)$ bits of space with constant time per operation in expectation. There has been a vast literature on improving its time and space usage. The state-of-the-art dictionary by Bender, Farach-Colton, Kuszmaul, Kuszmaul and Liu [1] has space consumption close to the information-theoretic optimum, using a total of \begin{equation*}\log \begin{pmatrix} U \\ n \end{pmatrix}+On\log ^{\left(k\right)} n\end{equation*} bits, while supporting all operations in $O(k)$ time, for any parameter $k \leq \log ^{*} n$. The term $O\left(\log ^{(k)} n\right)=O(\underbrace{\log \cdots \log n})$ is referred to as the wasted bits per key.In this paper, we prove a matching cell-probe lower bound: For $U=n^{1+\Theta(1)}$, any dictionary with $O\left(\log ^{(k)} n\right)$ wasted bits per key must have expected operational time $\Omega(k)$, in the cell-probe model with word-size $w=\Theta(\log U)$. Furthermore, if a dictionary stores values of $\Theta(\log U)$ bits, we show that regardless of the query time, it must have $\Omega(k)$ expected update time. It is worth noting that this is the first cell-probe lower bound on the trade-off between space and update time for general data structures.