Pith. sign in

REVIEW 2 major objections 5 minor 41 references

Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper constructs a dynamic dictionary whose space tracks the gap entropy of a key set and whose query time is O(log(1/ε)/log log(1/ε)), and proves a matching lower bound even for static dictionaries.

desk verdict A substantial upper-bound paper whose 'fully settled' claim is stronger than the proven tradeoff: the lower bound only bites in the regime where the additive O(n log(gap/n)) term is absorbed by ε·gap(S). read the letter →

arxiv 2608.06077 v1 pith:MIVHI72C submitted 2026-08-06 cs.DS

Guy E. Blelloch , Yang Hu , William Kuszmaul , Jingxun Liang , Renfei Zhou This is my paper · ORCID
classification cs.DS MSC 68P0568P2068Q1768W40
keywords dynamicdictionarygapentropydifferenceencodingtime-spacetradeoffcell-probelowerboundtriebinarysearchtreeretrievaldatastructure
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper resolves the space–time tradeoff for difference-encoded dictionaries, which store a sorted key set by encoding the gaps between consecutive keys. For any tunable parameter ε < 1/4, it builds a dynamic dictionary supporting insertions, deletions, and membership in O(log(1/ε)/log log(1/ε)) expected amortized time, using gap(S)(1+O(ε)) bits plus lower-order terms, where gap(S) is the gap entropy of the stored set. It also proves a matching cell-probe lower bound that applies even to static dictionaries, so no data structure can use this space and answer membership faster. This matters on clustered real-world data, where gap(S) is often far below the information-theoretic minimum, because it shows space-optimal difference-encoded dictionaries need not sacrifice speed.

What carries the argument

The load-bearing mechanism is the random-shift trie-entropy bound, which says that after adding a uniformly random offset to the keys, the expected number of edges in the binary trie differs from the gap entropy by only O(|S|) bits. This matters because the internal B-tree-and-trie representation is charged by trie edges rather than by key gaps, and the random shift lets the data structure pay gap(S) instead of the larger unshifted trie entropy. The second central piece is the difference-encoded biased B-tree: each trie component is stored with keys encoded relative to the bounding separator, using gap entropy plus O(|S| log log U) bits, with weights that make the access time telescope to O(log(1/ε)/log log(1/ε)) over the B levels. The lower bound is carried by a reduction to the path verification problem, where k trees of depth d with l-bit edge labels are stored in (1+O(1/2^d))·OPT bits, and round elimination forces Ω(d/log d) probes.

What would settle it

A static dictionary on a set S with small gap entropy that stores (1+O(ε))gap(S) bits and answers the hardest membership query in o(log(1/ε)/log log(1/ε)) expected cell probes would refute the lower bound; for the upper bound, an adversarial update sequence on clustered keys that exceeds the claimed amortized time or space would refute the construction.

Watch

Extended reading notes

Core claim

The central discovery is that a dictionary can simultaneously have space (1+O(ε))gap(S) plus O(|S| log(gap(S)/|S|)) + O(U^δ) bits and operation time O(log(1/ε)/log log(1/ε)), and that this tradeoff is exactly optimal, even for static sets. The construction partitions keys into small chunks, uses a space-efficient distributor to map keys to chunks, and stores each chunk with difference-encoded B-trees over tries; a random shift of the keys makes the trie entropy, which is what the tree structure naturally pays for, close to the gap entropy. On the lower-bound side, the dictionary problem is reduced to a path verification problem on labeled trees, and round elimination is applied using the correlation between positive membership answers when the gap entropy is small.

Load-bearing premise

The upper bound falls apart if the existing dynamic retrieval structure it assumes as a black box—one that stores per-key values in linear space with constant-time updates—cannot deliver those guarantees, and it also leans on the cited random-shift trie-entropy inequality.

Editorial extensions

If this is right

  • The previously posed open question about whether O(gap(S))-space dictionaries must incur ω(1) membership time is resolved in the negative: (1+O(ε))gap(S) space is achievable with very fast membership queries.
  • Any future dictionary that matches this space bound must have query time Ω(log(1/ε)/log log(1/ε)), even when the key set is fixed in advance, so the tradeoff is tight.
  • The accompanying corollaries give dynamic predecessor/successor and rank/select dictionaries with the same near-gap-entropy space and near-optimal time bounds.
  • Any rotation-based binary search tree can be stored in gap(S) + O(|S| log log U) bits without changing its asymptotic operation time, giving a reusable encoding for ordered tree structures.
  • On clustered real-world datasets, dictionary implementations can now aim for both near-gap-entropy space and nearly constant-time operations, closing the gap that previously separated practice-oriented difference encoding from succinct hashing.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The path-verification reformulation suggests that the round-elimination technique may transfer to other data-aware measures, such as dictionaries charged by run-length or LZ-style entropy of the key set.
  • The variable-length word RAM model combined with a dynamic retrieval data structure could become a general recipe for compressing pointer-based structures: replace explicit pointers by a retrieval lookup and pay one retrieval overhead instead.
  • On real clustered data, an implementation of this approach should show space close to gap(S) and flat operation times as ε varies; the O(U^δ) term may dominate storage for very large universes with small n, which the theory permits but practice might need to tune.
  • If the random-shift coupling between gap entropy and trie entropy is applied to other trie-based structures, such as Patricia tries or range filters, the same technique may yield new space–time tradeoffs for those structures.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies dynamic dictionaries under the gap-entropy measure gap(S), presenting a data structure (Theorem 1.1) that supports insertions, deletions, and membership in O(log(1/epsilon)/log log(1/epsilon)) expected amortized time using gap(S) + O(epsilon gap(S)) + O(|S| log(gap(S)/|S|)) + O(U^delta) bits. The construction proceeds through chunking, an improved distributor, difference-encoded binary search trees and B-trees, and a variable-length word RAM model. The paper also proves a cell-probe lower bound (Theorem 9.1) for static dictionaries using (1+O(epsilon)) gap(S) bits, claiming this settles the optimal time-space tradeoff for difference-encoded dictionaries.

Significance. If the upper bound is correct, it is a substantial advance: it gives the first dynamic dictionary with space tied to gap entropy and time o(log n), resolving an open question of Gupta, Hon, Shah, and Vitter. The modular structure is clear, and the paper contains many detailed proofs of intermediate lemmas, with careful attention to the variable-length word RAM simulation and to space accounting. The lower-bound framework, adapting round elimination to exploit correlations among positive queries, is also interesting. However, as discussed below, the claimed matching optimality is not fully supported by the stated theorems in one parameter regime, and one load-bearing lemma of the main upper bound is asserted without proof.

major comments (2)
  1. [Abstract, Theorem 1.1, Theorem 9.1, and Section 9] The claimed matching optimality is not established by the stated theorems. Theorem 9.1 assumes a static dictionary using (1+O(epsilon)) gap(S) bits, while the upper bound in Theorem 1.1 uses gap(S) + O(epsilon gap(S)) + O(|S| log(gap(S)/|S|)) + O(U^delta) bits. In the regime epsilon gap(S) = o(|S| log(gap(S)/|S|)), Section 9 itself says the lower bound is vacuous because the additive term is information-theoretically necessary. A dictionary that uses the full space budget of Eq. (4) and answers membership faster than Omega(log(1/epsilon)/log log(1/epsilon)) is therefore not ruled out. The abstract's statement that the paper "fully settles" the optimal time-space tradeoff is stronger than what the proof establishes. The authors should either extend the lower bound to the full space budget of Eq. (4), or restate the optimality claim with an explicit condition such as epsilon gap(S) = Omega(|S| log(gap(S)/|S|)), and accordingly qualify the title and abstract.
  2. [Section 8.1, Lemma 8.1] The main upper bound depends essentially on Lemma 8.1, but its proof is omitted with the sentence "The formal proof of Lemma 8.1 is omitted, as it is the same as in Section 4.2." The lemma is not identical to Lemma 4.2: it changes the time bound from O(1/epsilon) to O(log(1/epsilon)/log log(1/epsilon)), changes the space guarantee from worst case to expectation, and replaces Lemma 4.5 with Lemma 6.1. The reductions in Section 4.2 involving groups, blocks, and Lemma 4.8 must be re-verified under these changes, particularly the amortization argument for block creation and destruction and the expected-space accounting. A proof sketch or a precise statement of how the Section 4.2 reductions compose with Lemma 6.1 is needed before the main upper bound is fully verifiable.
minor comments (5)
  1. [Section 4.2.3, Eq. (8)] The equality O(epsilon t log U) = O(epsilon gap(S)) relies on the fact that each block has Theta(log U) gap entropy; this should be stated explicitly near Eq. (8) to avoid a gap in the derivation.
  2. [Section 4.2, Lemma 4.8] The lookup table supporting the short-encoding operations is asserted with the words "can be constructed using standard techniques. We omit the details." Since Lemma 4.8 is used in the proof of Lemma 4.2 and hence in the main upper bound, the construction and its O(1) time bounds should be described, or a precise reference should be given.
  3. [Section 3.2, Theorem 3.1 and Remark 3.2] The upper bound inherits all conditions and randomness guarantees of the dynamic retrieval theorem cited from [KPX+26], including its "with high probability" space and time bounds and its resizability. Because this theorem is load-bearing and is cited as an unpublished manuscript, the authors should ensure that the full statement, including the extension in Remark 3.2, is available to the reader or is included in the appendix.
  4. [Section 6.3, Eq. (15)] The random-shift bound E[trie_{3U}(S+Delta)] <= gap(S) + O(log U) + O(|S|) is cited from [GHSV07] without proof. Since this bound is used to convert trie entropy into gap entropy in Lemma 6.1, a short proof or a specific theorem number in [GHSV07] would improve verification.
  5. [Section 7.2, time efficiency paragraph] The phrase "blows up by an O(log log(1/epsilon)) factor" should be made precise: the warm-up already has O(1) time per level, and the final theorem requires O(log log(1/epsilon)) time for a Pivot operation, but the amortized argument across the k thresholds is not fully spelled out.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the tradeoff is derived from new constructions and independent cited building blocks, with a lower-bound scope caveat that is not circular.

full rationale

The upper bound (Theorem 1.1) is derived through the paper's own construction: chunks, distributors (Theorems 4.4 and 7.1), small dictionaries (Lemmas 4.2, 5.1, 6.1, 8.1), and the variable-length word RAM simulation (Lemma A.2). These components are proved in the paper from more basic lemmas (e.g., Lemmas 4.7, 5.3, 5.4, 6.2) and combine to give the stated gap(S)+O(epsilon gap(S))+O(|S| log(gap(S)/|S|)) space bound. No parameter is fitted to the target result and then renamed a prediction. The main black-box dependencies are Theorem 3.1 from [KPX+26] (resizable dynamic retrieval) and Eq. (15) from [GHSV07] (shifted trie entropy). Although [KPX+26] shares authors with this paper, it is a separate construction with its own stated assumptions (poly log U <= |S| <= U/2, values in [V]) that do not include the dictionary tradeoff; it is used as a building block for storing values and simulating variable-length words, not as a restatement of Theorem 1.1. The lower bound (Theorem 9.1, Lemma 9.2, and the reduction Lemma 9.3) is an independent cell-probe argument adapting [PV10] round elimination, and Lemma 9.3 explicitly constructs a dictionary instance from path-verification inputs while verifying gap({x_i,s}) <= (1+O(1/2^d)) OPT, so it does not assume the conclusion. One caveat, distinct from circularity, is that Theorem 9.1's hypothesis is space (1+O(epsilon)) gap(S), while Theorem 1.1 also spends O(|S| log(gap(S)/|S|)) bits; in the regime where that additive term dominates, the paper itself says the lower bound is vacuous, making the abstract's 'fully settle' wording stronger than the proved statement. That is a scope/correctness issue, not a self-referential derivation.

Assumptions & free parameters 3 free parameters · 6 assumptions · 2 invented entities

The central claim rests on standard word-RAM assumptions, a cited dynamic retrieval theorem, a cited trie-entropy inequality, and its own new model definitions. No parameters are fitted to data; epsilon and delta are tradeoff and small-error parameters chosen by the authors.

free parameters (3)
  • epsilon
    Tradeoff parameter in Theorem 1.1; user-selectable, determines time-space tradeoff, not fitted to data.
  • delta
    Small constant controlling the negligible U^delta space term; chosen by the authors.
  • C_chunk
    Sufficiently large constant for chunk size (poly log U keys per chunk); analysis requires it large enough.
assumptions (6)
  • standard math Word RAM model with word size w = Theta(log U)
    Standard model in algorithms; all bounds stated in it.
  • domain assumption Theorem 3.1 dynamic retrieval data structure exists with stated space/time
    Cited from [KPX+26]; used to implement distributor and variable-length word RAM simulation.
  • domain assumption Eq. (15): E[trie_{3U}(S+Delta)] <= gap(S)+log U+O(|S|)
    Random-shift trie entropy bound cited from GHSV07, needed for space proof of Lemma 6.1.
  • standard math AVL tree invariants; rotations preserve BST order
    Used in Lemma 5.1 and Corollary 5.2.
  • standard math Round elimination framework of Patrascu-Viola [PV10]
    Framework adapted for lower bound; inner lemma Lemma 9.4 is proved in the paper.
  • ad hoc to paper Variable-length word RAM model definition (Definition 3.3)
    New model introduced by authors to simplify pointer-free encoding; simulation in Claim A.2.
invented entities (2)
  • variable-length word RAM model
    purpose: Level of indirection that avoids explicit pointer storage and simplifies space accounting
    New computational model defined in the paper; no external falsifiable handle.
  • path verification problem
    purpose: Intermediate problem for the cell-probe lower bound; captures correlation between positive queries
    Introduced in Section 9.1 as a reformulation tool; mathematical construct.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries." pith.science (2026). https://pith.science/paper/MIVHI72C

@misc{pith2026260806077,
  author       = {Pith},
  title        = {Pith review of: Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MIVHI72C}},
  note         = {Machine review of arXiv:2608.06077}
}
abstract

The dynamic dictionary is a fundamental data structure that maintains a set $S\subset [U]$ of size $n$ (we assume $n=U^{1-\Theta(1)}$), supporting insertions, deletions and membership queries. Previous works mostly focused on constructing dictionaries that support operations in $O(1)$ time and use space as close to the \emph{information-theoretic bound} of $\log\binom{U}{n}$ bits as possible. In this paper, we study \emph{difference-encoded} dictionaries, which are dictionaries that use space close to the gap entropy $\text{gap}(S):=\sum_{i=2}^{|S|}\left(\lceil\log(x_i-x_{i-1}+1)\rceil+1\right)$ bits to store the set $S=\{x_1<\dots<x_n\}$. On many real-world datasets where the keys are clustered, we have $\text{gap}(S)\ll \log\binom{U}{n}$, making difference-encoded dictionaries more favorable than standard dictionaries in practice. Prior to this work, the best dynamic difference-encoded dictionary is by Blandford and Blelloch [SODA'04], whose construction supports operations in $O(\log n)$ time and uses $O(\text{gap}(S))$ bits of space. In the static case, Gupta, Hon, Shah and Vitter [DCC'06] presented a dictionary that uses $$ \text{gap}(S)+O(n\log\log U) $$ bits of space and supports membership queries in $O(\log\log n)$ time. In this work, we go beyond these bounds and fully settle the optimal time-space tradeoff for difference-encoded dictionaries. For an arbitrary parameter $0<\varepsilon<1/4$, we construct a dynamic dictionary that supports operations in $O(\log\varepsilon^{-1}/\log\log\varepsilon^{-1})$ expected amortized time and uses $$ \text{gap}(S)\cdot(1+O(\varepsilon))+O\left(n\log\frac{\text{gap}(S)}{n}\right) $$ bits of space. We also prove a matching lower bound, showing that our time-space tradeoff is optimal even in the \emph{static} case.

Figures

Figures reproduced from arXiv: 2608.06077 by the authors.

Figure 1
Figure 1. Left rotation in a binary search tree: y becomes the new root of the subtree, the middle subtree B moves from the left child of y to the right child of x. Subtrees A, B, and C keep their internal structure. A rotation can change the set of ancestors of many nodes. However, for all nodes but x, y, these changes do not affect their L, R values. Indeed, after performing the left rotation, nodes in A gain y as a new anc… view at source ↗
Figure 2
Figure 2. Cutting a trie into components when log U = 6 and B = 3. 6.4.2 The Data Structure We use biased B-trees to store the information of the components. Formally, for each non-degenerate com￾ponent, we apply Lemma 6.2 to maintain its set of reduced keys, where the weight of each reduced key is simply the weight of its corresponding leaf (as a node in T). As an example, the biased B-tree of the top component in [PITH_FUL… view at source ↗
Figure 3
Figure 3. Illustration of an input of the path verification problem for [PITH_FULL_IMAGE:figures/full_fig_p040_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Binary trie of the k · 2 d keys stored in the reduction from Lemma 9.3, illustrated for d = 2 and k = 4 (so ⌈log k⌉ = 2 bits for a). Edge labels 0 and 1 denote single bits of a or of the path s; each Yi,s marks an edge of length l bits in the key (cf [PITH_FULL_IMAGE:…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    A lower bound for finding predecessors in yao's call probe model

    Mikl \' o s Ajtai. A lower bound for finding predecessors in yao's call probe model. Comb. , 8(3):235--247, 1988

    work page 1988

  2. [2]

    Backyard cuckoo hashing: constant worst-case operations with a succinct representation

    Yuriy Arbitman, Moni Naor, and Gil Segev. Backyard cuckoo hashing: constant worst-case operations with a succinct representation. In Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS) , pages 787--796, 2010

    work page 2010

  3. [3]

    G. M. Adelson-Velsky and E. M. Landis. An algorithm for the organization of information. Soviet Mathematics Doklady , 3:1259--1263, 1962. English translation of Dokl. Akad. Nauk SSSR 146(2):263--266 (1962)

    work page 1962

  4. [4]

    Blandford and Guy E

    Daniel K. Blandford and Guy E. Blelloch. Compact representations of ordered sets. In Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 11--19, 2004

    work page 2004

  5. [5]

    Blandford and Guy E

    Daniel K. Blandford and Guy E. Blelloch. Compact dictionaries for variable-length keys and data with applications. ACM Transactions on Algorithms , 4(2):17:1--17:25, May 2008

    work page 2008

  6. [6]

    Monotone minimal perfect hashing: searching a sorted table with O (1) accesses

    Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. Monotone minimal perfect hashing: searching a sorted table with O (1) accesses. In Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 785--794, 2009

    work page 2009

  7. [7]

    Bender, Alex Conway, Mart \'i n Farach-Colton , William Kuszmaul, and Guido Tagliavini

    Michael A. Bender, Alex Conway, Mart \'i n Farach-Colton , William Kuszmaul, and Guido Tagliavini. Iceberg hashing: optimizing many hash-table criteria at once. Journal of the ACM , 70(6), November 2023

    work page 2023

  8. [8]

    Paul Beame and Faith E. Fich. Optimal bounds for the predecessor problem. In Proc. 31st ACM SIGACT Symposium on Theory of Computing (STOC) , pages 295--304, 1999

    work page 1999

Show all 41 references
  1. [9]

    Bender, Mart \'i n Farach-Colton , John Kuszmaul, William Kuszmaul, and Mingmou Liu

    Michael A. Bender, Mart \'i n Farach-Colton , John Kuszmaul, William Kuszmaul, and Mingmou Liu. On the optimal time/space tradeoff for hash tables. In Proc. 54th ACM SIGACT Symposium on Theory of Computing (STOC) , pages 1284--1297, 2022

    2022

  2. [10]

    Tight bounds for classical open addressing

    Michael A Bender, William Kuszmaul, and Renfei Zhou. Tight bounds for classical open addressing. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 636--657. IEEE, 2024

    2024

  3. [11]

    Optimal non-oblivious open addressing

    Michael A Bender, William Kuszmaul, and Renfei Zhou. Optimal non-oblivious open addressing. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 268--277, 2025

    2025

  4. [12]

    Minimal and monotone minimal perfect hash functions

    Paolo Boldi. Minimal and monotone minimal perfect hash functions. In Proc. 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), Part I , volume 9234 of Lecture Notes in Computer Science , pages 3--17, 2015

    2015

  5. [13]

    Reducing the retrieval time of scatter storage techniques

    Richard P Brent. Reducing the retrieval time of scatter storage techniques. Communications of the ACM , 16(2):105--109, 1973

    1973

  6. [14]

    Cell-probe lower bound for accessible interval graphs

    Sankardeep Chakraborty, Christian Engels, Seungbum Jo, and Mingmou Liu. Cell-probe lower bound for accessible interval graphs. Preprint arXiv:2311.02839, 2023

    2023 arXiv

  7. [15]

    Robin hood hashing

    Pedro Celis, Per-Ake Larson, and J Ian Munro. Robin hood hashing. In 26th annual symposium on foundations of computer science (sfcs 1985) , pages 281--288. IEEE, 1985

    1985

  8. [16]

    Demaine, Friedhelm Meyer auf der Heide , Rasmus Pagh, and Mihai P a tra s cu

    Erik D. Demaine, Friedhelm Meyer auf der Heide , Rasmus Pagh, and Mihai P a tra s cu. De dictionariis dynamicis pauco spatio utentibus. In Proc. 7th Latin American Conference on Theoretical Informatics (LATIN) , pages 349--361, 2006

    2006

  9. [17]

    Optimal bounds for open addressing without reordering

    Mart \' n Farach-Colton, Andrew Krapivin, and William Kuszmaul. Optimal bounds for open addressing without reordering. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 594--605. IEEE, 2024

    2024

  10. [18]

    Non-oblivious hashing

    Amos Fiat, Moni Naor, Jeanette Schmidt, and Alan Siegel. Non-oblivious hashing. In Proc. 20th ACM Symposium on Theory of Computing (STOC) , pages 367--376, 1988

    1988

  11. [19]

    Joan Feigenbaum and Robert E. Tarjan. Two new kinds of biased search trees. Bell System Technical Journal , 62:3139--3158, 1983

    1983

  12. [20]

    Fredman and Dan E

    Michael L. Fredman and Dan E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In Proc. 31st IEEE Symposium on Foundations of Computer Science (FOCS) , pages 719--725 vol.2, 1990

    1990

  13. [21]

    Fredman and Dan E

    Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences , 47(3):424--436, December 1993

    1993

  14. [22]

    Compressed data structures: Dictionaries and data-aware measures

    Ankur Gupta, Wing-Kai Hon, Rahul Shah, and Jeffrey Scott Vitter. Compressed data structures: Dictionaries and data-aware measures. Theoretical Computer Science , 387(3):313--331, 2007

    2007

  15. [23]

    Squeezing succinct data structures into entropy bounds

    Roberto Grossi and Kunihiko Sadakane. Squeezing succinct data structures into entropy bounds. In Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1230--1239, 2006

    2006

  16. [24]

    Optimal static dictionary with worst-case constant query time

    Yang Hu, Jingxun Liang, Huacheng Yu, Junkai Zhang, and Renfei Zhou. Optimal static dictionary with worst-case constant query time. In Michal Kouck \' y and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, ...

    2025

  17. [25]

    Succinct dynamic rank/select: Bypassing the tree-structure bottleneck

    William Kuszmaul, Jingxun Liang, and Renfei Zhou. Succinct dynamic rank/select: Bypassing the tree-structure bottleneck. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, ...

    2026

  18. [26]

    Tight bounds and phase transitions for incremental and dynamic retrieval

    William Kuszmaul, Aaron Putterman, Tingqiang Xu, Hangrui Zhou, and Renfei Zhou. Tight bounds and phase transitions for incremental and dynamic retrieval. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3974--3997. SIAM, 2025

    2025

  19. [27]

    Resizable retrieval

    William Kuszmaul, Aaron Putterman, Tingqiang Xu, Hangrui Zhou, and Renfei Zhou. Resizable retrieval. 2026

    2026

  20. [28]

    A hash table without hash functions, and how to get the most out of your random bits

    William Kuszmaul. A hash table without hash functions, and how to get the most out of your random bits. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 991--1001. IEEE, 2022

    2022

  21. [29]

    Nearly tight lower bounds for succinct range minimum query

    Mingmou Liu, Yi Li, and Huacheng Yu. Nearly tight lower bounds for succinct range minimum query. Preprint arXiv:2111.02318, 2021

    2021 arXiv

  22. [30]

    Tight cell-probe lower bounds for dynamic succinct dictionaries

    Tianxiao Li, Jingxun Liang, Huacheng Yu, and Renfei Zhou. Tight cell-probe lower bounds for dynamic succinct dictionaries. In Proc. 64th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 1842--1862, 2023

    2023

  23. [31]

    Dynamic dictionary with subconstant wasted bits per key

    Tianxiao Li, Jingxun Liang, Huacheng Yu, and Renfei Zhou. Dynamic dictionary with subconstant wasted bits per key. In Proc. 35th ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 171--207, 2024

    2024

  24. [32]

    Lower bound for succinct range minimum query

    Mingmou Liu and Huacheng Yu. Lower bound for succinct range minimum query. In Proc. 52nd ACM SIGACT Symposium on Theory of Computing (STOC) , pages 1402--1415, 2020

    2020

  25. [33]

    Techniques for collision resolution in hash tables with open addressing

    J Ian Munro and Pedro Celis. Techniques for collision resolution in hash tables with open addressing. In FJCC , pages 601--610, 1986

    1986

  26. [34]

    Low redundancy in static dictionaries with o (1) worst case lookup time

    Rasmus Pagh. Low redundancy in static dictionaries with o (1) worst case lookup time. In Proceedings of the 26th International Colloquium on Automata, Languages and Programming , pages 595--604, 1999

    1999

  27. [35]

    Addressing for random-access storage

    W Wesley Peterson. Addressing for random-access storage. IBM journal of Research and Development , 1(2):130--146, 1957

    1957

  28. [36]

    Dynamic integer sets with optimal rank, select, and predecessor search

    Mihai P a tra s cu and Mikkel Thorup. Dynamic integer sets with optimal rank, select, and predecessor search. In Proc. 55th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 166--175, 2014

    2014

  29. [37]

    Cell-probe lower bounds for succinct partial sums

    Mihai P a tra s cu and Emanuele Viola. Cell-probe lower bounds for succinct partial sums. In Proc. 21st ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 117--122, 2010

    2010

  30. [38]

    Succinct dynamic dictionaries and trees

    Rajeev Raman and Srinivasa Rao Satti. Succinct dynamic dictionaries and trees. In Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP) , pages 357--368, 2003

    2003

  31. [39]

    Information sorting in the application of electronic digital computers to business operations

    Harold Herbert Seward. Information sorting in the application of electronic digital computers to business operations . PhD thesis, Massachusetts Institute of Technology. Department of Electrical Engineering, 1954

    1954

  32. [40]

    Kaas, and E

    Peter van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Math. Syst. Theory , 10:99--127, 1977

    1977

  33. [41]

    Dan E. Willard. Log-logarithmic worst-case range queries are possible in space theta(n). Inf. Process. Lett. , 17(2):81--84, 1983

    1983

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.