{"id":"6fd5b85e-83ad-48d2-a7f3-77bfe9329b70","arxiv_id":"2608.08013","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Fixed-offset open addressing has constant expected insertion cost at load factor up to 35.74%, and quadratic probing up to 37.61%.","lead":"This paper proves that quadratic probing and every fixed probing pattern have constant expected insertion time when the table is up to about 36% full, improving an earlier 8.9% bound. It introduces a counting structure called a witness forest to bound collision patterns, bringing theory closer to the load factors that real hash tables use.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Uncertified numerical root computation for D(z) bears the 37.61% quadratic-probing claim; an error in q_1..q_15 or root isolation would break Theorem 4.1 without affecting the analytic 35.74% result.","rationale":"The paper's main analytic result, Theorem 1.1, is supported by a self-contained chain of inequalities: Lemma 3.1-3.4 are structural and symbolic, and the algebra leading to the 35.74% threshold is clean. I checked Lemma 3.4's counting and the cancellations in the proof of Theorem 1.1; no hidden flaw appears. The geometric-domination wording in Theorem 1.1 is stronger than what the proof explicitly shows (only expectation), but a tail bound follows by the same sum with a /s factor, so this is not load-bearing. The genuinely load-bearing weakness is Section 4's numerical claim. The polynomial D(z)'s smallest-modulus zero determines the exponential growth rate of the tree counts through the closed form H(z)=(1+S(z)-sqrt(D(z)))/2. Since S is derived from q_i, any error in enumeration or in root-finding changes ρ and hence β. The paper provides no verifiable certificate: q_i are listed to 15 digits, but no polynomial coefficients, no root multiplicities, and no interval bounds. This matches the reader's weakest_assumption exactly. Because the 37.61% figure is the headline improvement for quadratic probing and the high-probability corollary depends on it, the conditional verdict is appropriate; an independent verification of the numerical data would lift the condition.","tokens_in":15700,"tokens_out":53369,"duration_ms":542115,"concrete_test":"Run the published enumeration code and an independent reimplementation (e.g., a backtracking search over plane trees with heap-ordered labels, checking realizability via Lemma 3.2 for r_i=i^2) to verify q_1..q_15; then, from these exact integers, construct S(z) and D(z) and use high-precision interval root isolation (e.g., 100-digit verified arithmetic in Sage/Mathematica) to confirm that the zero of smallest modulus is a simple positive real root ρ with 1/(eρ)<1.42473 and no other roots of smaller modulus. If both pass, Theorem 4.1's 37.61% bound is established; otherwise it is not.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The advertised improvement for quadratic probing (Theorem 4.1, α≤0.3761) depends on the numerically asserted value ρ≈0.2582, the smallest-modulus zero of D(z)=(1-S(z))^2-4z, where S(z) is built from the exact counts q_1..q_15 of realizable enhanced witness trees. The paper lists the q_i and cites a GitHub repository but gives no certificate: no derivation of S, no root-finding parameters, no error bounds, and no proof that the nearest zero is simple and no odd-multiplicity zero is closer. Because β=1.42473 is justified solely by 1/(eρ)<β, and because the q_i are enormous (q_15≈9.4e17), a single enumeration bug or a missed smaller-modulus root would invalidate the 37.61% claim. The analytic 35.74% theorem (Theorem 1.1) is unaffected, as it relies only on Lemma 3.3/3.4, which are fully symbolic.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15950,"tokens_out":17872,"duration_ms":184554,"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":[{"comment":"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.","section":"Section 4, Eqs. (4)-(5) and the table of q_i"},{"comment":"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":"Corollary 1.2 and Theorem 4.1"},{"comment":"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.","section":"Section 4, step from exponential growth to β=1.42473"}],"minor_comments":[{"comment":"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":"Theorem 1.1"},{"comment":"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":"Section 3.2, reindexing"},{"comment":"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.","section":"Section 4 and footnote 11"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The analytic core of the paper—Theorem 1.1 with the 35.74% threshold—appears sound and is a strong contribution. The main risk is the uncertified numerical part behind Theorem 4.1. The paper's own acknowledgment that some proof steps were suggested by generative AI is not a problem per se, but it strengthens the need for a human-verifiable certificate for the q_i enumeration and the singularity computation. If the authors provide the requested certificate or remove the numerical claim, the paper would be publishable. The appendix on linear probing is a nice pedagogical addition but is secondary to the main contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nI 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.\n\nWho 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.","headline":"Theorem 1.1 is the real result; the 37.61% claim needs a numerical certificate.","tokens_in":16442,"tokens_out":2145,"would_cite":true,"duration_ms":21926,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P20","68W40","68P05","05A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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%.","keywords":["open addressing","quadratic probing","hash tables","witness forest","fixed-offset probing","expected insertion cost","load factor","generating functions"],"falsifier":"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.","tokens_in":15509,"feed_emoji":"🔑","tokens_out":7977,"duration_ms":77188,"temperature":0.7,"pith_summary":"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.","feed_headline":"Quadratic probing proven constant-time up to 37.6% load","feed_subtitle":"A witness-forest proof raises the guaranteed load for quadratic probing from 8.9% to 37.6%.","key_machinery":"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.","core_discovery":"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\\%$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the previous best bound (8.9%) and the witness-string method that the witness forest refines, serving as the baseline the new results must beat.","marker":"[KX24]"},{"why":"Provides the Exponential Growth Formula and the Catalan generating function identity used to solve the recurrence for witness-tree counts.","marker":"[FS09]"},{"why":"Establishes that for quadratic probing with suitable table size, the first many probe offsets are distinct, which is needed to transfer Theorem 1.1 to quadratic probing in Corollary 1.2.","marker":"[HD72]"},{"why":"Provides constructions of quadratic probe sequences with distinct first n/2 or n probes, used to remove the failure probability in Corollary 1.2.","marker":"[Bat75]"}],"fun_headline_variants":["Quadratic probing proven constant-time up to 37.6% load","Open addressing gets constant-time guarantee up to 35.7% load","Witness forests boost open addressing load limit to 35.7%","New proof raises open addressing load bound from 8.9% to 35.7%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic probing proven constant-time up to 37.6% load","Open addressing gets constant-time guarantee up to 35.7% load","Witness forests boost open addressing load limit to 35.7%","New proof raises open addressing load bound from 8.9% to 35.7%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000714,"raw_usage":{"total_tokens":3210,"prompt_tokens":942,"completion_tokens":2268,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":558,"completion_tokens_details":{"reasoning_tokens":2193}},"tokens_in":558,"tokens_out":2268,"duration_ms":16428,"temperature":1.0,"reasoning_tokens":2193,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:35:42.150791+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}