Optimal Static Dictionary with Worst-Case Constant Query Time

Huacheng Yu; Jingxun Liang; Junkai Zhang; Renfei Zhou; Yang Hu

REVIEW 3 major objections 3 minor 36 references

Optimal Static Dictionary with Worst-Case Constant Query Time

T0 review · 3 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read A static dictionary now answers worst-case queries in optimal space plus n^ε bits.

desk verdict A serious and mostly well-built construction whose main theorem rests on an unproven and possibly false generalization of a bounded-independence permutation lemma—send it out, but the referee must check Appendix B. read the letter →

arxiv 2412.10655 v2 pith:AR6SNPWP submitted 2024-12-14 cs.DS

Yang Hu , Jingxun Liang , Huacheng Yu , Junkai Zhang , Renfei Zhou This is my paper · ORCID

classification cs.DS MSC 68P0568P2068Q25

keywords staticdictionarysuccinctdatastructuresworst-casequerytimeretrievalstructurewordRAMspilloverrepresentationhashfunctionsCauchymatrices

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 claims a static dictionary that answers every membership query in worst-case constant time while using essentially the information-theoretical minimum space. Concretely, for n keys from a universe of size $U \in [2n, \mathrm{poly}\, n]$, with word size $\Theta(\log n)$, the main structure uses $\log\binom{U}{n} + \mathrm{poly}\log n$ bits, and the only input-independent extras are a fixed lookup table of $n^\varepsilon$ bits and a hash function encoded in $n^\varepsilon$ bits. If this is right, the redundancy penalty for worst-case constant query time drops from the previous $n/\mathrm{poly}\log n$ to $n^\varepsilon$, matching the best known redundancy for expected-constant-time dictionaries. The construction works by storing the per-bucket dictionary words as values in a zero-redundancy augmented retrieval data structure, thereby sidestepping the partial-sum bottleneck that forced the earlier redundancy.

What carries the argument

The load-bearing object is the augmented retrieval data structure. It stores $n$ key-value pairs together with an array of $m$ elements, using exactly $n+m$ memory words and answering both kinds of queries in $O(1)$ worst-case time: each query is the inner product of a memory vector with a row of a sparse matrix that has only a constant number of non-zero entries. The construction that makes this possible is the sparsification trick, which first samples an intermediate matrix with $O(\log n)$ non-zero entries per row and then uses the always-valid augmented queries to move those entries onto augmented rows; the word RAM variant replaces free randomness with a tree-of-blocks matrix built from Cauchy submatrices, whose full-rank submatrix property is shown by induction.

What would settle it

One observation that would settle the central claim: compile the Appendix B permutation family for a concrete instance, say $U = 2^{20}$, $n = 2^{10}$, $B = \log^4 n$, run the bucketing over many random members of the family, and measure the worst bucket deviation from $B$; if the deviation exceeds $B^{2/3}$ with probability significantly above $1/n^2$, the family's balance guarantee fails. A second check is the independence step in the proof of Lemma B.1, where the paper asserts that a $O(2^{(L-s)\varepsilon^2/4})$-wise independent hash function behaves independently on any $k$-element subset when $L-s = O(\log B)$; verifying that assertion for these parameters would confirm or break the hash-bound chain.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that the partial sums obstacle vanishes if the per-bucket dictionaries are not stored as contiguous blocks at all. Each bucket's encoding is a spillover representation $(m_i, k_i)$; the words of each $m_i$ and each spill $k_i$ are treated as key-value pairs in a retrieval problem, and any word or spill is recovered in constant time by a sparse linear combination of memory words. The paper proves an augmented retrieval lemma: when a retrieval problem is packaged together with a large array of other data that is already stored, the extra rows make it possible to sparsify the retrieval matrix to $O(1)$ non-zero entries per row, so retrieval costs constant time with no redundancy. The word RAM version constructs the required sparse full-rank matrix from a tree of blocks filled with Cauchy submatrices, needing only $O(n^\varepsilon)$-bit randomness, and the same bucket machinery is shown to extend from membership to full key-value dictionaries, yielding the OPT-based theorem.

Load-bearing premise

The theorem collapses if the Appendix B claim is false: the bounded-independence permutation family must still give every bucket $B \pm B^{2/3}$ keys when the codomain slack is only $O(\log B)$, with an $O(n^\varepsilon)$-bit description, and the paper provides only a proof sketch for this step.

Editorial extensions

If this is right

If the main theorem is correct, membership of $n$ keys can be stored in $\log\binom{U}{n} + n^\varepsilon$ bits and answered in $O(1)$ worst-case time in the word RAM.
The cell-probe version of the same construction needs only $\mathrm{poly}\log n$ redundancy, because Newman's theorem lets the lookup table and $\mathrm{poly}\, n$ hash functions be hardwired with just an index stored.
Because the $n^\varepsilon$ lookup table and the hash function are input-independent, up to $\mathrm{poly}\, n$ dictionaries can share one copy, so the $n^\varepsilon$ overhead is effectively amortized.
The bucket-level spillover encoding from the membership proof carries over to key-value dictionaries, giving $\mathrm{OPT} + n^\varepsilon$ total bits for values from a $\mathrm{poly}\, n$-sized alphabet with worst-case constant queries.

Reading between the lines

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

If the construction is sound, the $n/\mathrm{poly}\log n$ cost of previous worst-case constant-time dictionaries is an artifact of storing per-bucket blocks contiguously and locating them by partial sums, not an inherent property of the dictionary problem.
The augmented-retrieval idea is likely to transfer to other succinct structures that embed a large fixed array; the paper itself defines augmented redundancy and asks whether it can be strictly below regular redundancy.
A natural next test is whether the tree-of-blocks matrix can be reused to build a static retrieval data structure with $\mathrm{poly}\log n$ redundancy and $O(\log n)$-bit values without the augmented array, something the paper leaves open.

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.

Desk Editor's Note

read the letter

Here's the thing: the paper's central result—OPT+poly log n space, worst-case constant time—is exactly the kind of step that would close the gap between Pătraşcu and Yu. If it's right, it's a major result. The new ingredients (augmented retrieval, tree-of-blocks, spillover reuse) are genuinely new and mostly well-worked-out. The entropy argument in Lemma 4.7 is elegant, and the sparsification in Section 5 is detailed, not hand-wavy. I think the reader's verdict is about right: the main proof structure is sound, but there are two spots that need referee scrutiny.

The big one is Lemma 4.6 / Appendix B. The LLYZ24 bounded-independence permutation is constructed for {0,1}^L, and the paper says the proof 'can be easily generalized' to L-s = O(log B). But the application needs a permutation on [U] with equal-size buckets, where U need not be a power of two. If you embed [U] into {0,1}^{ceil(log U)} and use prefix buckets, the bucket sizes in [U] are not equal—they can differ by far more than a factor of 2 (some subtrees are full, others have one element). The concentration guarantee from Lemma B.1 is for equal-size classes in the full space, not for the uneven intersections with [U]. The paper doesn't address this at all. This is not a minor gap; Lemma 4.6 is the only place where the n^epsilon-bit hash encoding comes from, and Theorem 1.1 stands or falls with it. An expert referee needs to demand a complete proof or a different construction.

The second soft spot is the key-value extension, which is asserted via a black-box citation to [Yu20]. That's probably repairable, and less concerning. The self-citations to Yu20 and LLYZ24 are not a problem in themselves; the problem is that the modified lemma needs real proof.

So: this paper deserves a serious referee, not a desk reject. But the referee needs to put their finger on Appendix B early. If the generalization is false, the main theorem collapses; if it's true, the paper is a strong accept.

Referee Report

3 major / 3 minor

Summary. The paper proposes a static dictionary on the word RAM that stores n key-value pairs from a universe [U] × [σ] in OPT + poly log n bits of main memory, assuming access to an n^ε-bit lookup table and an n^ε-bit-encodable hash function, with worst-case constant query time and high-probability construction. The construction hashes keys into n/B buckets via a bounded-independence permutation family, encodes each bucket with a spillover representation following Pǎtrașcu and Yu, and concatenates the per-bucket representations using a new augmented retrieval data structure. The cell-probe version (Section 4) uses fully random hashing, while the word-RAM version (Section 5) replaces this with a tree-of-blocks Cauchy-matrix construction based on limited-independence hashing. The paper also claims a value-bearing extension via a black-box citation to [Yu20].

Significance. If the result is correct, it resolves a natural open problem in succinct dictionaries: worst-case constant query time is achieved with n^ε redundancy, matching the best known redundancy of expected-constant-time dictionaries. The augmented retrieval framework — using a large fixed array as a resource to sparsify a retrieval matrix — is a novel and potentially reusable technique. The paper contains detailed proofs of the main cell-probe and word-RAM retrieval machinery, including a coherent entropy argument (Lemma 4.7) and a plausible full-rank induction (Lemma 5.5). However, the main theorem relies on several load-bearing black-box steps that are only sketched or asserted, and the correctness for arbitrary universe sizes is not established.

major comments (3)

[Appendix B / Lemma 4.6] Lemma 4.6 is not proved for the stated universe [U]. The proof reduces to Lemma B.1, which constructs bijections on {0,1}^L for integer parameters L and s. For an arbitrary U in [2n, poly n], neither L = log U nor s = log(n/B) need be integers, and a permutation on the padded space {0,1}^{ceil(log U)} does not partition [U] into n/B buckets of equal size U/(n/B): the preimage of a length-s prefix has size 2^{ceil(log U)}/2^s, which can be almost twice V = U/(n/B). Since the per-bucket code length in Lemma 4.2 is log(V choose s), replacing V by up to 2V adds Θ(B) bits per bucket and thus Θ(n) bits in total, contradicting the OPT + poly log n bound in Theorem 5.1. The statement of Lemma 4.6 itself also silently requires U to be divisible by n/B. This gap is load-bearing because Lemma 4.6 supplies the bucket hash in Section 4.3 and the n^ε-bit hash encoding required by Lemma 5.2 and Theorem 5.1.
[Appendix B / Lemma B.1] The claimed generalization of [LLYZ24, Lemma 5.1] to the regime L − s = O(log B) is justified only by the sentence 'their proof can be easily generalized' plus a paragraph stating that the only constraint is k = O(2^{(L−s)ε^2/4}). No proof is given that the O(2^{εL})-bit representation, O(1)-time evaluation, and independence analysis survive when ε = Ω(sqrt(log L/(L−s))) is nonconstant. In particular, the condition k = (10 ln 2)L = O(2^{(L−s)ε^2/4}) is asserted but not verified with the exact constants in [LLYZ24], and it is not the only place where the original proof might use s ≤ (1−Ω(1))L. Because this lemma is the only source of an n^ε-bit encodable permutation, the word-RAM theorem (Theorem 5.1) and the retrieval construction (Lemma 5.2) stand or fall with it. The authors should supply a complete proof with all parameter dependencies, or cite a version that explicitly covers L − s = O(log B).
[Section 5, 'Extending to key-value dictionaries'] Theorem 1.1 promises key-value dictionaries, but the entire paper up to this paragraph constructs membership data structures. The extension is asserted in one paragraph: the first part of the encoding 'again appl[ies] black-box tools from [Yu20]' to obtain 'a variant of Lemma 4.2 that also stores associated values.' No statement or proof of this variant is provided. To be usable with the rest of the construction, the variant must preserve all the properties on which Lemma 4.3 relies: a spillover representation (m, k) with M, K determined by s, first O(1) words of m encoding s, O(1) worst-case probes, and O(1/n^2) redundancy, now with n log σ value bits added. If the required tools appear in [Yu20], the authors should state the exact theorem they use; otherwise Theorem 1.1 exceeds what is proved.

minor comments (3)

[Section 4.3, proof of Claim 4.9] The inequality '(2n choose n) ≥ 2^{2n}/n' is false (e.g., n = 2 gives 6 < 8). The intended lower bound is (2n choose n) ≥ 2^{2n}/(2n), which still yields the claimed Ω(B/log n) bound.
[Section 4.3 and Lemma 4.3] The symbol S is used both for the key set and for the number of distinct bucket sizes S = 2B^{2/3}+1 in Lemma 4.3 and its application; this is confusing and should be renamed in one of the two roles.
[Proof of Lemma 4.7] The word 'indecator' should be 'indicator' in the paragraph comparing the indicator random variables of D_hash and D_ind.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reduction found; the result is a new combination of independent prior results, with a sketched parameter generalization in Appendix B as the main correctness risk rather than circularity.

full rationale

The derivation is not circular. The main theorem is obtained by (i) partitioning the universe with a bounded-independence permutation family, (ii) encoding each bucket with a spillover representation, and (iii) concatenating these representations with a new augmented-retrieval construction. The two externally sourced building blocks are [Yu20, Lemma 28] for per-bucket spillover encoding and [LLYZ24, Lemma 5.1] for a bijective hash family. Both are peer-reviewed prior results by overlapping authors, but neither assumes the target theorem: [Yu20] provides near-optimal encodings for poly-log-sized sets, and [LLYZ24] provides a permutation family with load concentration in a different setting. They are independent support, not inputs whose renaming produces the conclusion. The entropy comparison in Lemma 4.7 is self-contained: p(s) is defined as the marginal bucket-size probability, and the proof bounds E_h sum_i (log 1/p(s_i) + log C(V,s_i)) <= log C(U,n)+O(log n) by the standard fact that the independent distribution maximizes entropy under fixed marginals; no fitted parameter is later relabeled as a prediction. The genuinely weak point is Appendix B: Lemma B.1 is asserted as a modified version of [LLYZ24, Lemma 5.1], and the proof says it can be easily generalized to L-s = O(log B), with epsilon = Omega(sqrt(log L/(L-s))). The full argument is not given, and the case of non-power-of-two U and exact bucket sizes is not spelled out. This is an omitted proof, not a circular step: Lemma 4.6 is not definitionally identical to the cited lemma, and its failure would break the word-RAM hash encoding, but that would be a correctness gap rather than a reduction of the result to its own inputs. Accordingly, no circularity step is recorded; the self-citation reliance is noted but does not make the derivation circular.

Assumptions & free parameters 3 free parameters · 7 assumptions · 0 invented entities

The central claim relies mainly on standard probabilistic and algebraic tools plus two black boxes from prior work, the Yu20 spillover representation and the LLYZ24 hash family. It introduces no new physical or information-theoretic entities; all parameters are algorithm design choices.

free parameters (3)

B (bucket size) = poly log n, chosen as a sufficiently large power of log n
Hand-chosen parameter controlling bucket concentration, redundancy, and the validity of Claim 4.9. The proof requires B to be large enough that M_min dominates the right-hand side of Eq. (1).
epsilon (redundancy exponent) = arbitrary constant > 0, taken small
Exponent in the n^ε lookup table and hash encoding. Any positive constant works by choosing B large and using Lemma 5.6; it is not fitted to data.
t (sample count in random matrix) = 10 log n
Number of random entries per row in Lemma 3.3. Any sufficiently large constant multiple of log n would work; the choice makes the union bound in Appendix A go through.

assumptions (7)

standard math Schwartz-Zippel lemma over finite fields
Used in Lemma 3.3 and Lemma 5.5 to show that random evaluations of nonzero polynomials are nonzero with high probability.
standard math Hall's marriage theorem
Used in Appendix A to show the sampled pattern matrix has a perfect matching with high probability, which implies its determinant polynomial is nonzero.
standard math Chernoff bounds for poly-log-wise independent random variables [SSS95]
Used in Section 5 and Appendix B to show bucket loads concentrate within B ± Δ_i with high probability under bounded-independence hashing.
standard math Prime gap theorem [SQ92]: a prime exists in [n, n + n^(7/11)]
Used in Lemma 4.4 to bound the redundancy of rounding spill universes K(s) up to the next prime P(s).
domain assumption Word RAM model with word size w = Θ(log n)
The query algorithm operates on words of this size; the whole construction is stated within this model.
domain assumption Universe and value ranges U ∈ [2n, poly n], σ ∈ [1, poly n]
The theorem only claims this range; outside it, the constant-time and poly-log-redundancy bounds may fail.
ad hoc to paper Bounded-independence permutation family from [LLYZ24] works after modification
Lemma 4.6 is a modified version of [LLYZ24, Lemma 5.1] with a sketched proof; the word RAM result depends on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal Static Dictionary with Worst-Case Constant Query Time." pith.science (2026). https://pith.science/paper/AR6SNPWP

@misc{pith2026241210655,
  author       = {Pith},
  title        = {Pith review of: Optimal Static Dictionary with Worst-Case Constant Query Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AR6SNPWP}},
  note         = {Machine review of arXiv:2412.10655}
}

abstract

In this paper, we design a new succinct static dictionary with worst-case constant query time. A dictionary data structure stores a set of key-value pairs with distinct keys in $[U]$ and values in $[\sigma]$, such that given a query $x\in [U]$, it quickly returns if $x$ is one of the input keys, and if so, also returns its associated value. The textbook solution to dictionaries is hash tables. On the other hand, the (information-theoretical) optimal space to encode such a set of key-value pairs is only $\text{OPT} := \log\binom{U}{n}+n\log \sigma$. We construct a dictionary that uses $\text{OPT} + n^{\epsilon}$ bits of space, and answers queries in constant time in worst case. Previously, constant-time dictionaries are only known with $\text{OPT} + n/\text{poly}\log n$ space [P\v{a}tra\c{s}cu 2008], or with $\text{OPT}+n^{\epsilon}$ space but expected constant query time [Yu 2020]. We emphasize that most of the extra $n^{\epsilon}$ bits are used to store a lookup table that does not depend on the input, and random bits for hash functions. The "main" data structure only occupies $\text{OPT}+\text{poly}\log n$ bits.

Figures

Figures reproduced from arXiv: 2412.10655 by the authors.

**Figure 1.** Sparsifying a row By combining the construction of each A(i) (and setting other undefined entries to zero), we obtain the matrix A, where each row in A contains at most 3 non-zero entries. Furthermore, for any i ∈ [N + m], we can easily compute the non-zero entries in Ai,∗ in constant time, allowing the algorithm to answer each query in constant time. Finally, since A is obtained by performing some elementary operat… view at source ↗

**Figure 2.** Storing all spills of type s. (1) First, we convert part of mfix from base 2 w to base P (s) using Theorem 4.5, getting m (s) conv; we also “round up” the universe of spills from [K(s) ] to [P (s) ]. (2) Next, we build the augmented retrieval by Corollary 3.2 using m (s) conv as augmented elements, getting the representation of this data structure m (s) retr. (3) Finally, we convert it back to binary words using The… view at source ↗

**Figure 3.** Tree of blocks with h = 4 levels. Every rectangle represents a block on the tree, in which the hatched area represents the supplementary columns of a block, and the gray area represents the locations of non-zero entries in the matrix. For each level-i block u, let δu denote the difference between the number of columns and the number of valid rows in u’s subtree. We point out that δu ∈ [0, 2∆i ] with high probability… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Gaussian elimination on matrix M. (a) The matrix is partitioned into 3×3 blocks, where they correspond to row sets Q0, Q1, Q2 from top to bottom, and column sets C1, C2, C0 from left to right. The third column set C0 consists of the 2∆i supplementary columns of block u…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 28 canonical work pages

[1]

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]

Karp, Marek Karpinski, Michael Luby, and David Zuckerman

Johannes Bl \"o mer, Malik Kalfane, Richard M. Karp, Marek Karpinski, Michael Luby, and David Zuckerman. An XOR -based erasure-resilient coding scheme. 1995

work page 1995
[3]

Ian Munro

Andrej Brodnik and J. Ian Munro. Membership in constant time and almost-minimum space. SIAM J. Comput. , 28(5):1627--1640, 1999

work page 1999
[4]

Are bitvectors optimal? SIAM J

Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, and Srinivasan Venkatesh. Are bitvectors optimal? SIAM J. Comput. , 31(6):1723--1744, 2002

work page 2002
[5]

Cormen, Charles E

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition . MIT Press, 2009

2009
[6]

Larry Carter and Mark N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci. , 18(2):143--154, 1979

work page 1979
[7]

Changing base without losing space

Yevgeniy Dodis, Mihai P a tra s cu, and Mikkel Thorup. Changing base without losing space. In Proc. 42nd ACM Symposium on Theory of Computing (STOC) , pages 593--602, 2010

work page 2010
[8]

Constant-time retrieval with O( m) extra bits

Martin Dietzfelbinger and Stefan Walzer. Constant-time retrieval with O( m) extra bits. In Proc. 36th International Symposium on Theoretical Aspects of Computer Science (STACS) , pages 24:1--24:16, 2019

work page 2019

Show all 36 references

[9]

Fredman, J \'a nos Koml \'o s, and Endre Szemer \'e di

Michael L. Fredman, J \'a nos Koml \'o s, and Endre Szemer \'e di. Storing a sparse table with O(1) worst case access time. Journal of the ACM , 31(3):538--544, June 1984

1984
[10]

Fich and Peter Bro Miltersen

Faith E. Fich and Peter Bro Miltersen. Tables should be sorted (on random access machines). In Proc. 4th International Workshop on Algorithms and Data Structures (WADS) , pages 482--493, 1995

1995
[11]

Implicit O(1) probe search

Amos Fiat and Moni Naor. Implicit O(1) probe search. SIAM J. Comput. , 22(1):1--10, 1993

1993
[12]

Schmidt, and Alan Siegel

Amos Fiat, Moni Naor, Jeanette P. Schmidt, and Alan Siegel. Non-oblivious hashing. J. ACM , 39(4):764--782, 1992

1992
[13]

Cell probe lower bounds for succinct data structures

Alexander Golynski. Cell probe lower bounds for succinct data structures. In Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 625--634, 2009

2009
[14]

On representatives of subsets

Peter Hall. On representatives of subsets. Journal of The London Mathematical Society (Second Series) , pages 26--30, 1935

1935
[15]

Efficient minimal perfect hashing in nearly minimal space

Torben Hagerup and Torsten Tholey. Efficient minimal perfect hashing in nearly minimal space. In Proc. 18th Symposium on Theoretical Aspects of Computer Science (STACS) , volume 2010 of Lecture Notes in Computer Science , pages 317--326. Springer, 2001

2010
[16]

Nearly tight lower bounds for succinct range minimum query

Mingmou Liu. Nearly tight lower bounds for succinct range minimum query. Preprint arXiv:2111.02318, February 2022

2022 arXiv
[17]

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
[18]

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
[19]

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
[20]

Lower bounds for static dictionaries on RAMs with bit operations but no multiplication

Peter Bro Miltersen. Lower bounds for static dictionaries on RAMs with bit operations but no multiplication. In Proc. 23rd International Colloquium on Automata, Languages and Programming (ICALP) , pages 442--453, 1996

1996
[21]

On data structures and asymmetric communication complexity

Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. J. Comput. Syst. Sci. , 57(1):37--49, 1998

1998
[22]

Randomized Algorithms

Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms . Cambridge University Press, 1995

1995
[23]

Private vs

Ilan Newman. Private vs. common random bits in communication complexity. Inf. Process. Lett. , 39(2):67--71, 1991

1991
[24]

Low redundancy in static dictionaries with constant query time

Rasmus Pagh. Low redundancy in static dictionaries with constant query time. SIAM Journal on Computing , 31(2):353--363, January 2001

2001
[25]

On the cell probe complexity of membership and perfect hashing

Rasmus Pagh. On the cell probe complexity of membership and perfect hashing. In Proc. 33rd ACM SIGACT Symposium on Theory of Computing (STOC) , pages 425--432, 2001

2001
[26]

Succincter

Mihai P a tra s cu. Succincter. In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 305--313, 2008

2008
[27]

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
[28]

A Chebychev's type of prime number theorem in a short interval II

Lou Shituo and Yao Qi. A Chebychev's type of prime number theorem in a short interval II . Hardy-Ramanujan Journal , Volume 15:1--33, January 1992

1992
[29]

Schmidt and Alan Siegel

Jeanette P. Schmidt and Alan Siegel. The spatial complexity of oblivious k -probe hash functions. SIAM J. Comput. , 19(5):775--786, 1990

1990
[30]

Schmidt, Alan Siegel, and Aravind Srinivasan

Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-Hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics , 8(2):223--250, May 1995

1995
[31]

Simple tabulation, fast expanders, double tabulation, and high independence

Mikkel Thorup. Simple tabulation, fast expanders, double tabulation, and high independence. In Proc. 54th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 90--99, 2013

2013
[32]

Storing a sparse table

Robert Endre Tarjan and Andrew Chi - Chih Yao. Storing a sparse table. Commun. ACM , 22(11):606--611, 1979

1979
[33]

Bit-probe lower bounds for succinct data structures

Emanuele Viola. Bit-probe lower bounds for succinct data structures. SIAM J. Comput. , 41(6):1593--1604, 2012

2012
[34]

New sampling lower bounds via the separator

Emanuele Viola. New sampling lower bounds via the separator. In Proc. 38th Computational Complexity Conference (CCC) , pages 26:1--26:23, 2023

2023
[35]

Should tables be sorted? J

Andrew Chi - Chih Yao. Should tables be sorted? J. ACM , 28(3):615--628, 1981

1981
[36]

Nearly optimal static Las Vegas succinct dictionary

Huacheng Yu. Nearly optimal static Las Vegas succinct dictionary. In Proc. 52nd ACM SIGACT Symposium on Theory of Computing (STOC) , pages 1389--1401, 2020

2020

Pith tools

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

[1] [1]

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] [2]

Karp, Marek Karpinski, Michael Luby, and David Zuckerman

Johannes Bl \"o mer, Malik Kalfane, Richard M. Karp, Marek Karpinski, Michael Luby, and David Zuckerman. An XOR -based erasure-resilient coding scheme. 1995

work page 1995

[3] [3]

Ian Munro

Andrej Brodnik and J. Ian Munro. Membership in constant time and almost-minimum space. SIAM J. Comput. , 28(5):1627--1640, 1999

work page 1999

[4] [4]

Are bitvectors optimal? SIAM J

Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, and Srinivasan Venkatesh. Are bitvectors optimal? SIAM J. Comput. , 31(6):1723--1744, 2002

work page 2002

[5] [5]

Cormen, Charles E

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition . MIT Press, 2009

2009

[6] [6]

Larry Carter and Mark N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci. , 18(2):143--154, 1979

work page 1979

[7] [7]

Changing base without losing space

Yevgeniy Dodis, Mihai P a tra s cu, and Mikkel Thorup. Changing base without losing space. In Proc. 42nd ACM Symposium on Theory of Computing (STOC) , pages 593--602, 2010

work page 2010

[8] [8]

Constant-time retrieval with O( m) extra bits

Martin Dietzfelbinger and Stefan Walzer. Constant-time retrieval with O( m) extra bits. In Proc. 36th International Symposium on Theoretical Aspects of Computer Science (STACS) , pages 24:1--24:16, 2019

work page 2019