A Simple Analysis of Quadratic Probing and Other Open Addressing Schemes

Chengzhang Wan; Seth Pettie; Yuhao Guo

REVIEW 3 major objections 4 minor 60 references

A Simple Analysis of Quadratic Probing and Other Open Addressing Schemes

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

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

Pith's one-line read Quadratic probing is proven to have constant expected insertion time for table load factors up to 37.61%, and any fixed offset sequence up to 35.74%.

desk verdict Theorem 1.1 is the real result; the 37.61% claim needs a numerical certificate. read the letter →

arxiv 2608.08013 v1 pith:ROE7T7P2 submitted 2026-08-08 cs.DS

Yuhao Guo , Seth Pettie , Chengzhang Wan This is my paper · ORCID

classification cs.DS MSC 68P2068W4068P0505A15

keywords openaddressingquadraticprobinghashtableswitnessforestfixed-offsetexpectedinsertioncostloadfactorgeneratingfunctions

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

Open addressed hash tables store elements in a flat array and probe successive slots until an empty one is found. This paper proves that if the probe offsets form any fixed permutation of the table, the expected time of an insertion is constant for table load factors up to $35.74\%$, and for quadratic probing specifically up to $37.61\%$. These are the first theoretical guarantees beyond the $8.9\%$ load factor established in a 2024 result, and they match the load factors at which quadratic probing is used in practice. The proof introduces a witness forest that records how probe sequences collide, then uses generating functions to count how many such forests are realizable under a random hash function. If the bounds are correct, standard quadratic probing is not merely empirically fast but provably constant-time at realistic loads.

What carries the argument

The central object is the witness forest. When element $u$ is inserted, each probe that lands on an occupied slot creates an edge from $u$ to the root of the tree containing the element occupying that slot, and labels that child with the occupying element. The forest satisfies three structural lemmas: ancestors are later-inserted elements, roots are unlabeled, and every element encountered during $u$'s probe sequence lies in $u$'s subtree. These properties let the analysis bound the probability of seeing a given tree: for any tree on $s$ elements, only $n(n-s)^{m+1-s}$ hash functions can realize it. The counting of realizable trees is done with an exponential generating function $G(z) = z/(1-G(z))$; the generic bound follows from the Catalan solution, and for quadratic probing the first 15 exact counts are plugged into a refined generating function $H(z)$, whose nearest singularity determines the improved load factor.

What would settle it

Recompute the exact values $q_1,\dots,q_{15}$ by an independent enumeration of realizable enhanced witness trees for quadratic probing and verify they match the paper's table; then compute the moduli of the zeros of $D(z)$ and check that the smallest one is a simple zero satisfying $1/(e\rho) \le 1.42473$. Any mismatch invalidates the $37.61\%$ claim. Alternatively, simulate quadratic probing with random hash functions at load factor $0.3761$: if the average insertion cost grows with $n$, the theorem is false.

Watch

Extended reading notes

Core claim

Formally, the paper claims that for any load factor $\alpha < \alpha^*$, where $\alpha^* \approx 0.357403$ is the unique solution in $[0,1]$ of $\frac{4}{e}\alpha e^{1-\alpha} = 1$, and any permutation $(r_0,\dots,r_{n-1})$ of the table slots, the cost of inserting a new element using the probe sequence $h(x)+r_i \bmod n$ is stochastically dominated by a geometric random variable with mean $O(1)$. For the quadratic probing sequence $r_i = i^2$, the bound improves to $\alpha \le 0.3761$ with failure probability $\exp(-\Omega(\sqrt n))$. These results extend a 2024 breakthrough that had proved constant expected insertion time only for $\alpha \le 8.9\%$.

Load-bearing premise

The sharper $37.61\%$ quadratic-probing bound rests on an unproved numerical assertion: that the smallest-modulus zero of $D(z)=(1-S(z))^2 - 4z$ is a simple square-root singularity and gives $\beta = 1.42473$, which depends on the computer-generated counts $q_1,\dots,q_{15}$. If that computation is wrong, the $37.61\%$ bound is not established, although the analytic $35.74\%$ theorem for any fixed offset sequence may still stand.

Editorial extensions

If this is right

Any fixed-offset open addressing scheme has constant expected insertion time for load factors below 35.74%, so the practical choice among probe sequences is not constrained by the lack of a theoretical guarantee.
Quadratic probing is provably constant-time up to 37.61% load, meaning hash tables using it can be filled to more than a third full without risking a blow-up in expected search time.
The witness-forest method gives a general recipe: exact enumeration of small realizable trees plus a generating-function recurrence yields refined load-factor bounds for any specific offset sequence.
For linear probing, the same framework recovers the known result that insertion cost is constant for any load factor bounded away from 1, as shown in Appendix A.
The failure probability for quadratic probing is exponentially small in $\sqrt{n}$, so the guarantee is essentially for every table large enough.

Reading between the lines

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

The cutoff at 15 for the exact enumeration is a computational choice, not a mathematical limit; using larger $k$ would likely push the proven quadratic-probing load factor above 37.61%, since the generic bound 35.74% is already exceeded by a small amount of exact data.
The witness-forest counting method might extend to other open-addressing disciplines such as Robin Hood hashing or to probe sequences chosen per key, though the collision-recording rule would need to be adapted to the displacement rule.
Because the analysis assumes uniformly random hash functions, a natural testable question is how much hash-function independence is required for the witness-forest counting to remain valid; the paper does not address that.
The 35.74% threshold for generic fixed-offset sequences is determined by the constant $4/e$ in the tree count; any improvement in the tree-count lemma for general permutations would immediately raise the threshold.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

First, the headline: the analytic 35.74% theorem is real and well-proven; the 37.61% quadratic probing number is a computational claim that currently lacks a certificate. Don't desk-reject it, but send it to a referee who will demand the missing verification.

The main innovation is the witness forest. It's a cleaner encoding than Kuszmaul-Xi's witness strings, and it immediately yields a constant expected insertion bound for any fixed-offset sequence at load factors below ~35.74%. The proof of Theorem 1.1 is genuinely self-contained: the bound uses a Catalan count and a generating function, and the threshold comes from solving (4/e) α e^{1-α}=1. No circular fitting. Lemma 3.3 and 3.4 are clear, and the expected-cost summation in the proof is direct and correct. This is a solid piece of work and a genuine advance over the 8.9% threshold.

The soft spots are exactly where the reader's report puts them. Theorem 4.1, the 37.61% bound for quadratic probing, depends on the exact counts q_1..q_15 and on the claim that the smallest-modulus zero of D(z) is a simple square-root singularity with ρ≈0.2582. The paper lists the q_i and points to a GitHub repo, but there is no derivation of S(z), no root-finding parameters, no error bounds, and no proof that the relevant zero is simple and that no other zero is closer. A bug in the enumeration or a missed root would break that theorem. The analytic 35.74% result does not depend on this, so the paper's core contribution stands even if the computational part fails. Corollary 1.2 is also only sketched; the exp(-Ω(√n)) high-probability statement needs the transfer argument written out, not just asserted.

I also want to say something in the paper's favor: it is honest about its slack, and the AI acknowledgment is refreshing. The related work is thorough and the linear probing appendix is a nice sanity check.

Who should read this: anyone working on open addressing or witness tree methods. It deserves a serious referee. My recommendation: send it to review, but require a reproducible certificate for the numerical part and a fuller proof of Corollary 1.2 before publication. If the computation doesn't pan out, the paper is still worth publishing for Theorem 1.1 alone.

Referee Report

3 major / 4 minor

Summary. The paper introduces a witness forest for open-addressed hashing with fixed offset sequences. For any permutation (r_0,...,r_{n-1}), it proves (Theorem 1.1) that the expected cost of the (m+1)-th insertion is O(1) whenever the load factor satisfies (4/e) α e^{1-α} < 1, i.e., α < α* ≈ 0.357403. The proof combines a combinatorial bound on realizable labeled witness trees (Lemma 3.3) with a hash-function counting lemma (Lemma 3.4). For quadratic probing, the paper claims an improved threshold α ≤ 0.3761 (Theorem 4.1) by exactly enumerating small realizable enhanced witness trees (q_1,...,q_15), constructing the generating function H(z) = (1+S(z) - sqrt((1-S(z))^2 - 4z))/2, and numerically locating the smallest singularity ρ of the square root; the improved bound follows from β = 1.42473 > 1/(eρ). An appendix develops a witness-tree proof of the classical constant expected insertion time for linear probing at any load factor bounded away from 1. The analytic part of the paper is self-contained and gives a substantial improvement over the previous 8.9% bound of Kuszmaul and Xi. The numerical improvement for quadratic probing, however, depends on computational assertions that are not certified in the manuscript.

Significance. If the 35.74% bound is correct—and the symbolic proof appears sound—this is a significant theoretical advance for open addressing with fixed offset sequences, more than quadrupling the previously known constant load-factor threshold. The witness-forest counting method is simple, elegant, and likely to be reusable. The additional improvement to 37.61% for quadratic probing is notable but currently rests on an uncertified enumeration and a numerical singularity computation. The paper also credits the machine-checkable/reproducible aspects: the analytic derivations are explicit and the q_i are listed, and the appendix provides a clean alternative proof for linear probing. However, the numerical part is not yet at the standard of rigor expected for a claimed theorem; the analytic 35.74% result alone is a solid contribution, while the 37.61% claim needs a verifiable certificate.

major comments (3)

[Section 4, Eqs. (4)-(5) and the table of q_i] The advertised improvement from 35.74% to 37.61% is the entire content of Theorem 4.1, and it rests on three unchecked numerical assertions: (i) the exact values q_1,...,q_15, (ii) the claim that the zero of D(z) of minimum modulus is simple, and (iii) the value β=1.42473 used to infer α≤0.3761. The manuscript provides no algorithm for the enumeration, no explicit polynomial D(z), no root-isolation procedure, and no error bounds. A single bug in the enumeration (q_15 has 18 digits) or a missed smaller-modulus zero would invalidate Theorem 4.1. The argument must be made verifiable within the paper: include the enumeration procedure (or the complete list of generated trees), the polynomials Q, R, S and hence D(z), and a validated interval for ρ with a proof that no other zero has smaller modulus. Without this, the 37.61% bound is not established.
[Corollary 1.2 and Theorem 4.1] The statements 'with probability 1−exp(−Ω(√n))' in Corollary 1.2 and Theorem 4.1 are never formally defined or proved. The only explanation, 'Corollary 1.2 only relies on the fact that the first Ω(√n) elements of the probe sequence are distinct mod n', is not a proof. The probability space (over the hash function? over the insertion sequence?) and the event whose failure probability is exp(−Ω(√n)) must be specified. The expected-cost proof of Theorem 1.1 does not automatically yield such a high-probability guarantee; the authors must derive it from the witness-forest tail bound or state a weaker, unambiguous theorem.
[Section 4, step from exponential growth to β=1.42473] The text uses the Exponential Growth Formula to conclude [z^s]H(z)=O((1/ρ+ε)^s) for every ε>0, and then asserts β=1.42473>1/(eρ). The implicit constant in the O may depend on ε, and converting coefficient growth to the universal tree-count bound O(β^s s^s) also invokes Stirling's approximation with unspecified constants. To make the numerical threshold rigorous, the authors need explicit inequalities valid for all s with universal constants, for instance by combining a validated bound on finitely many coefficients with a crude tail bound for large s. As written, the step from asymptotics to the claimed universal bound is not fully justified.

minor comments (4)

[Theorem 1.1] Theorem 1.1 claims that the insertion cost is 'dominated by a geometric random variable with mean O(1)', but the proof only establishes E[cost]=O(1). The stronger stochastic-dominance claim follows from the same A_s bounds by noting P(cost ≥ s) ≤ ∑_{t≥s} A_t/t, with A_t ≤ e r^t for r=(4/e)αe^{1-α}<1, but this step is omitted. Adding it would align the theorem statement with the proof.
[Section 3.2, reindexing] In the proof of Theorem 1.1, after reindexing, the factor (n-s)^{m-s} should strictly be (n-s-1)^{m-s} because the original term contains (n-s)^{m+1-s} with s being the tree size and the root occupying one slot. The replacement by (n-s)^{m-s} is an overestimate and does not affect the argument, but the displayed equality is not exact; a brief note would avoid confusion.
[Section 4 and footnote 11] The GitHub repository cited in footnote 11 is not a substitute for a self-contained proof. In a journal submission, the numerical computation should be either described in full in the paper or provided as ancillary material with sufficient detail for independent verification.
[Throughout] There are a few presentation issues: the symbol ▷◁ is defined only in a footnote; the notation A[h(x)+r_i mod n] should be parenthesized consistently; and in the recurrence of Section 4 the use of s for both the total size and the subtree sizes is mildly confusing. These do not affect correctness.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the 35.74% threshold is solved from the derived inequality (4/e)αe^{1-α} < 1, and the 37.61% quadratic-probing bound rests on exact small-case enumeration plus a singularity analysis, not on fitting or self-citation.

full rationale

The derivation chain is self-contained. Theorem 1.1 obtains α* ≈ 0.357403 by solving (4/e)αe^{1-α} = 1, an inequality that emerges from Lemmas 3.3 and 3.4: Lemma 3.3 counts labeled witness trees via a Catalan bound with an exact cancellation, and Lemma 3.4 counts hash functions consistent with a given tree; neither lemma assumes the target load threshold. Section 4 improves the bound for quadratic probing by fixing exact enumeration counts q_1..q_15 of realizable enhanced witness trees, then using the recurrence (1) to construct H(z) and the Exponential Growth Formula to read off the growth rate from the smallest-modulus zero of D(z) = (1-S(z))^2 - 4z. The value β = 1.42473 is computed from ρ and then checked against the inequality βαe^{1-α} < 1; it is not chosen or fitted to make α = 0.3761 true. The claim that the smallest-modulus zero is simple is asserted without a certificate, and the q_i depend on code, so a numerical or enumeration error would invalidate Theorem 4.1; however, that is a verification gap, not circularity, because none of the inputs is logically equivalent to the conclusion being drawn. The AI acknowledgment and the paper's own discussion of slack identify places where the analysis overcounts, which are conservative approximations rather than hidden uses of the target result. No load-bearing step reduces by construction to a fitted parameter, a self-citation, or a renaming of the conclusion.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central theorem depends only on standard hashing model axioms and basic combinatorics. The improved quadratic probing bound additionally depends on a finite exact enumeration (k=15) and a numerical singularity computation that is not fully certified in the text.

free parameters (1)

k (exact enumeration truncation) = 15
The improved quadratic probing bound computes exact counts up to size k=15 and uses a recurrence beyond that; larger k would give a slightly better beta, so this is a computational choice rather than a fitted constant.

assumptions (5)

domain assumption Hash functions are uniformly random and independent for each key.
The entire expected-cost analysis is in this model; the theorem does not address adversarial hash functions. Invoked in Section 2.
domain assumption The fixed-offset sequence (r0,...,rn-1) is a permutation of [n] with r0=0.
Theorem 1.1 is stated for fixed-offset sequences; quadratic probing is handled separately because i^2 mod n may not be a permutation. Section 2.
domain assumption The first Omega(sqrt(n)) quadratic probing offsets are distinct modulo n.
Used to transfer the fixed-offset result to quadratic probing with failure probability exp(-Omega(sqrt(n))). Section 1.1 and Corollary 1.2.
standard math Exponential Growth Formula and Lagrange inversion as in Flajolet and Sedgewick.
Used in Section 4 and Appendix A to extract coefficient asymptotics and solve functional equations.
ad hoc to paper The smallest-modulus zero of D(z) is simple and correctly computed via the listed enumeration.
Unproved in text; the authors state they computed rho from D(z) but give no certificate. Load-bearing for the 37.61% bound. Section 4, equation (5).

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Simple Analysis of Quadratic Probing and Other Open Addressing Schemes." pith.science (2026). https://pith.science/paper/ROE7T7P2

@misc{pith2026260808013,
  author       = {Pith},
  title        = {Pith review of: A Simple Analysis of Quadratic Probing and Other Open Addressing Schemes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ROE7T7P2}},
  note         = {Machine review of arXiv:2608.08013}
}

abstract

In open addressed hashing, quadratic probing is attractive for striking a nice balance between having a high locality of reference and a low number of probes per search. However, these are empirical observations, not theoretical guarantees. Indeed, until recently, it was not known whether quadratic probing had constant expected insertion cost under any positive load factor $\alpha > 0$, even with uniformly random hash functions. In a recent breakthrough---albeit a numerically understated breakthrough---Kuszmaul and Xi (2024) proved that any fixed offset sequence (including quadratic probing) does, in fact, have constant expected insertion cost for load factors $\alpha \leq 8.9\%$. This is well below what we would like to prove, that quadratic probing has constant insertion cost for any load factor $\alpha < 1-\epsilon$ bounded away from 1. In this paper, we prove that open addressed hashing with any fixed offset sequence has constant expected insertion cost for load factors up to $35.74\%$, and that for quadratic probing in particular, we can increase the load factor to $37.61\%$. Our main innovation is a new type of witness forest for recording collisions among the probe sequences.

Figures

Figures reproduced from arXiv: 2608.08013 by the authors.

**Figure 1.** Top: the hash table A[0..31] after inserting 1, 2, . . . , 14 using quadratic probing, where ri = i 2 . Bottom: the corresponding witness forest, where the label ℓ(u) is written just above the node u. The hash values in this example are: h(8) = 0, h(1) = h(4) = h(5) = h(13) = 2, h(2) = h(7) = 23, h(9) = 6, h(3) = h(6) = h(14) = 15, h(10) = h(11) = 10, h(12) = 19. Lemma 3.1. Let F, ℓ be the witness forest and labelin… view at source ↗

**Figure 2.** Left: a witness tree that is realizable for quadratic probing, but not linear probing. Right: [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 57 canonical work pages

[1]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP) , series =

William Kuszmaul and Zoe Xi , title =. Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP) , series =. 2024 , url =

work page 2024
[2]

2009 , publisher=

Analytic combinatorics , author=. 2009 , publisher=

2009
[3]

Analysis of uniform hashing , author=. J. ACM , volume=

work page
[4]

Uniform hashing is optimal , author=. J. ACM , volume=. 1985 , publisher=

work page 1985
[5]

Proceedings of the 65th Annual

Optimal Bounds for Open Addressing Without Reordering , author=. Proceedings of the 65th Annual

work page
[6]

An occupancy discipline and applications , author=. SIAM J. Appl. Math. , volume=. 1966 , publisher=

work page 1966
[7]

Programming technique: An improved hash code for scatter storage , author=. Commun. ACM , volume=. 1968 , publisher=

work page 1968
[8]

Bender and Bradley C

Michael A. Bender and Bradley C. Kuszmaul and William Kuszmaul , title =. Proceedings of the 62nd Annual. 2021 , url =

work page 2021

Show all 60 references

[9]

Haim Mendelson and Uri Yechiali , title =. J. 1980 , url =

1980
[10]

Poblete and Alfredo Viola , title =

Philippe Flajolet and Patricio V. Poblete and Alfredo Viola , title =. Algorithmica , volume =. 1998 , url =

1998
[11]

Knuth , title =

Donald E. Knuth , title =. Algorithmica , volume =. 1998 , url =

1998
[12]

Proceedings of the 27th Annual International Conference on Current Trends in the Theory and Practice of Informatics (

Thomas Schickinger and Angelika Steger , title =. Proceedings of the 27th Annual International Conference on Current Trends in the Theory and Practice of Informatics (. 2000 , url =

2000
[13]

Moser and G

Robin A. Moser and G. A constructive proof of the general. J. 2010 , url =

2010
[14]

Distributed algorithms for the

Kai. Distributed algorithms for the. Distributed Comput. , volume =. 2017 , url =

2017
[15]

IBM Journal of Research and Development , year=

Addressing for Random-Access Storage , author=. IBM Journal of Research and Development , year=
[16]

Knuth , title =

Donald E. Knuth , title =
[17]

Bell and Charles H

James R. Bell and Charles H. Kaman , title =. Commun. 1970 , url =

1970
[18]

Balbine, Guy de , title =
[19]

Guibas and Endre Szemer

Leonidas J. Guibas and Endre Szemer. The Analysis of Double Hashing , booktitle =. 1976 , url =

1976
[20]

Guibas and Endre Szemer

Leonidas J. Guibas and Endre Szemer. The Analysis of Double Hashing , journal =. 1978 , url =

1978
[21]

Guibas , title =

Leonidas J. Guibas , title =. J. 1978 , url =

1978
[22]

Lueker and Mariko Molodowitch , title =

George S. Lueker and Mariko Molodowitch , title =. Combinatorica , volume =. 1993 , url =

1993
[23]

Knuth , title =

Ole Amble and Donald E. Knuth , title =. Comput. J. , volume =. 1974 , url =

1974
[24]

Proceedings of the 26th Annual

Pedro Celis and Per. Proceedings of the 26th Annual. 1985 , url =

1985
[25]

Robert A

F. Robert A. Hopgood and James H. Davenport , title =. Comput. J. , volume =. 1972 , url =

1972
[26]

Vladimir Batagelj , title =. Commun. 1975 , url =

1975
[27]

Bender and William Kuszmaul and Renfei Zhou , title =

Michael A. Bender and William Kuszmaul and Renfei Zhou , title =. Proceedings of the 65th Annual. 2024 , url =

2024
[28]

and Wilhelm G

Geza Schay Jr. and Wilhelm G. Spruth , title =. Commun. 1962 , url =

1962
[29]

Random Struct

Svante Janson , title =. Random Struct. Algorithms , volume =. 2001 , url =

2001
[30]

2009 , url =

Anna Pagh and Rasmus Pagh and Milan Ruzic , title =. 2009 , url =

2009
[31]

On the k -Independence Required by Linear Probing and Minwise Independence , journal =

Mihai P. On the k -Independence Required by Linear Probing and Minwise Independence , journal =. 2016 , url =

2016
[32]

The Power of Simple Tabulation Hashing , journal =

Mihai P. The Power of Simple Tabulation Hashing , journal =. 2012 , url =

2012
[33]

Twisted Tabulation Hashing , booktitle =

Mihai P. Twisted Tabulation Hashing , booktitle =. 2013 , url =

2013
[34]

Bercea and Lorenzo Beretta and Jonas Klausen and Jakob B

Ioana O. Bercea and Lorenzo Beretta and Jonas Klausen and Jakob B. Locally Uniform Hashing , booktitle =. 2023 , url =

2023
[35]

CoRR , volume =

Yang Hu and William Kuszmaul and Jingxun Liang and Stefan Walzer and Huacheng Yu and Renfei Zhou , title=. CoRR , volume =. 2026 , eprinttype =. 2607.13247 , archivePrefix=

2026 arXiv
[36]

Proceedings of the 65th Annual

Mark Braverman and William Kuszmaul , title =. Proceedings of the 65th Annual. 2024 , url =

2024
[37]

Rasmus Pagh and Flemming Friche Rodler , title =. J. Algorithms , volume =. 2004 , url =

2004
[38]

2009 , url =

Adam Kirsch and Michael Mitzenmacher and Udi Wieder , title =. 2009 , url =

2009
[39]

Proceedings of the Eighteenth Annual

Daniel Fernholz and Vijaya Ramachandran , title =. Proceedings of the Eighteenth Annual. 2007 , url =

2007
[40]

Martin Dietzfelbinger and Christoph Weidling , title =. Theor. Comput. Sci. , volume =. 2007 , url =

2007
[41]

Proceedings of the 19th Annual European Symposium on Algorithms (

Martin Dietzfelbinger and Michael Mitzenmacher and Michael Rink , title =. Proceedings of the 19th Annual European Symposium on Algorithms (. 2011 , url =

2011
[42]

Proceedings of the 37th International Colloquium on Automata, Languages, and Programming (

Martin Dietzfelbinger and Andreas Goerdt and Michael Mitzenmacher and Andrea Montanari and Rasmus Pagh and Michael Rink , title =. Proceedings of the 37th International Colloquium on Automata, Languages, and Programming (. 2010 , url =

2010
[43]

Spirakis , title =

Dimitris Fotakis and Rasmus Pagh and Peter Sanders and Paul G. Spirakis , title =. Theory Comput. Syst. , volume =. 2005 , url =

2005
[44]

2023 , url =

Stefan Walzer , title =. 2023 , url =

2023
[45]

Proceedings of the 30th Annual European Symposium on Algorithms (

Stefan Walzer , title =. Proceedings of the 30th Annual European Symposium on Algorithms (. 2022 , url =

2022
[46]

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (

Michael Mitzenmacher and Konstantinos Panagiotou and Stefan Walzer , title =. Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (. 2018 , url =

2018
[47]

Wormald , title =

Julie Anne Cain and Peter Sanders and Nicholas C. Wormald , title =. Proceedings of the Eighteenth Annual. 2007 , url =

2007
[48]

Nikolaos Fountoulakis and Megha Khosla and Konstantinos Panagiotou , title =. Comb. Probab. Comput. , volume =. 2016 , url =

2016
[49]

Random Struct

Nikolaos Fountoulakis and Konstantinos Panagiotou , title =. Random Struct. Algorithms , volume =. 2012 , url =

2012
[50]

2013 , url =

Nikolaos Fountoulakis and Konstantinos Panagiotou and Angelika Steger , title =. 2013 , url =

2013
[51]

Proceedings of the Twenty-Third Annual

Marc Lelarge , title =. Proceedings of the Twenty-Third Annual. 2012 , url =

2012
[52]

2025 , url =

Stefan Walzer , title =. 2025 , url =

2025
[53]

Frieze and P

Alan M. Frieze and P. Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables , journal =. 2012 , url =

2012
[54]

Frieze , title =

Tolson Bell and Alan M. Frieze , title =. Proceedings of the 65th Annual. 2024 , url =

2024
[55]

Frieze and Tony Johansson , title =

Alan M. Frieze and Tony Johansson , title =. Random Struct. Algorithms , volume =. 2019 , url =

2019
[56]

Lehman and Rina Panigrahy , title =

Eric P. Lehman and Rina Panigrahy , title =. Proceedings of the 17th Annual European Symposium on Algorithms (. 2009 , url =

2009
[57]

Proceedings of the 36th Annual

William Kuszmaul and Michael Mitzenmacher , title =. Proceedings of the 36th Annual. 2025 , url =

2025
[58]

Coloring random graphs online without creating monochromatic subgraphs , journal =

Torsten M. Coloring random graphs online without creating monochromatic subgraphs , journal =. 2014 , url =

2014
[59]

Fast Local Computation Algorithms , booktitle =

Ronitt Rubinfeld and Gil Tamir and Shai Vardi and Ning Xie , editor =. Fast Local Computation Algorithms , booktitle =. 2011 , url =

2011
[60]

Leonid Barenboim and Michael Elkin and Seth Pettie and Johannes Schneider , title =. J. 2016 , url =

2016

Pith tools

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

[1] [1]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP) , series =

William Kuszmaul and Zoe Xi , title =. Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP) , series =. 2024 , url =

work page 2024

[2] [2]

2009 , publisher=

Analytic combinatorics , author=. 2009 , publisher=

2009

[3] [3]

Analysis of uniform hashing , author=. J. ACM , volume=

work page

[4] [4]

Uniform hashing is optimal , author=. J. ACM , volume=. 1985 , publisher=

work page 1985

[5] [5]

Proceedings of the 65th Annual

Optimal Bounds for Open Addressing Without Reordering , author=. Proceedings of the 65th Annual

work page

[6] [6]

An occupancy discipline and applications , author=. SIAM J. Appl. Math. , volume=. 1966 , publisher=

work page 1966

[7] [7]

Programming technique: An improved hash code for scatter storage , author=. Commun. ACM , volume=. 1968 , publisher=

work page 1968

[8] [8]

Bender and Bradley C

Michael A. Bender and Bradley C. Kuszmaul and William Kuszmaul , title =. Proceedings of the 62nd Annual. 2021 , url =

work page 2021