{"id":"0dc27d16-9a1c-4f45-a99a-62c6a1cf9f9d","arxiv_id":"2501.02305","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Open-addressed hash tables without reordering can achieve O(1) amortized and O(log 1/delta) worst-case expected probe complexity, and greedy schemes achieve O(log^2 1/delta), disproving Yao's conjecture.","lead":"This paper builds hash tables that find stored items with far fewer memory probes than previously believed possible, even when items are never moved after insertion. It also disproves a 40-year-old conjecture by Yao and proves matching lower bounds for the new bounds.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the greedy lower bound's unstated monotonicity is true and easily supplied, so the central claim stands.","rationale":"The paper's central claim is that greedy open addressing can achieve worst-case expected probe complexity O(log^2 1/δ) and that every greedy scheme requires Ω(log^2 1/δ), refuting Yao's conjecture. The upper bound (funnel hashing) is a concrete, parameter-free construction with a coherent proof. The lower bound rests on Lemma 8 and Lemma 9. The reader correctly identifies Lemma 8's monotonicity assertion as the least-supported step, since the paper states it without proof. I verified that the assertion is true: greedy insertion means the insertion cost of a key is the index of the first empty slot in its probe sequence, and since the occupied set only grows, this index is stochastically nondecreasing. Thus the threshold argument in Lemma 8 is valid. I also checked the more delicate additive decomposition in Lemma 9. The concern would be double-counting: the earlier insertion's expected cost is a total-cost lower bound, while the induction adds a second-layer cost for probes to the then-empty set. The resolution is that at the chosen load point, the then-empty slots are all free, so every probe that lands there is immediately successful; hence the earlier expected cost is essentially one plus the expected number of probes to the already-occupied set S. Greedy monotonicity then implies the final insertion's expected probes to S are at least that quantity, so adding the compressed-table lower bound is legitimate. The remaining issues are typographical or constant-related (e.g., the C bucket size can be taken as a sufficiently large constant multiple of log log n), and they do not threaten the asymptotic theorems. The proofs are intricate and not machine-checked, which justifies the reader's MODERATE confidence, but I do not see a load-bearing gap.","tokens_in":19049,"tokens_out":30430,"duration_ms":310736,"concrete_test":"Add to Section 4 a formal coupling proof of Lemma 8: for any greedy scheme, couple insertions j and j+1 by giving both the same random probe sequence and coupling the occupied sets so O_j ⊆ O_{j+1}; the first-free index is then nondecreasing, so E[q_j] ≤ E[q_{j+1}]. This single inserted lemma closes the only identified gap; if the coupling failed for any valid greedy distribution, Theorem 4 would need rework, but it does not fail.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After re-deriving the key steps, I found no load-bearing flaw in Theorem 4's proof. The reader's flagged assumption in Lemma 8 — that q_j is monotone — is not proved in the text, but it is correct: in a greedy scheme, for a fixed probe sequence, the first free slot under a superset of occupied slots cannot appear earlier. Coupling the (j+1)-st insertion with the j-th insertion using the same probe sequence gives q_j ≤ q_{j+1}. Lemma 9's recursive second-layer-cost argument is also sound: for the insertion at the chosen load point, every probe that lands in the then-empty set U succeeds, so its expected cost is one plus the expected number of probes to the occupied set S; by the same superset-monotonicity, the final insertion's expected probes to S dominate that quantity, so adding the compressed-table cost to the first-layer cost does not double-count. Minor issues (e.g., 'ci log n' for 'ci log δ^-1', C bucket-size constants) are presentation-level and do not affect the asymptotic claims.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies open-addressed hash tables that do not reorder inserted elements. It presents two new schemes: elastic hashing, which achieves O(1) amortized and O(log 1/δ) worst-case expected probe complexity without reordering, and funnel hashing, a greedy scheme achieving O(log^2 1/δ) worst-case expected probe complexity. It claims matching lower bounds, including a lower bound of Ω(log^2 1/δ) for all greedy schemes, thereby disproving Yao's 1985 conjecture that uniform probing is optimal in the worst-case expected sense. The paper also gives lower bounds for arbitrary non-reordering schemes: Ω(log 1/δ) worst-case expected and Ω(log^2 1/δ + log log n) high-probability worst-case. The proofs combine decoupling arguments for elastic hashing, a layered bucket structure for funnel hashing, and inductive/compression arguments for lower bounds.","tokens_in":19296,"tokens_out":40010,"duration_ms":339088,"significance":"If the main theorems are correct, the paper resolves a longstanding open problem and provides tight bounds for a basic data-structure question. The conceptual contributions — decoupling insertion probes from search probes and the layered funnel construction — are interesting and likely to influence subsequent work on hashing and load balancing. The paper also makes good use of external benchmarks: Yao's theorem, Vöcking's theorem, and the power-of-two-choices theorem are invoked appropriately. However, the written proofs contain several nontrivial errors and missing justifications, especially in the lower-bound sections, so the results are not yet fully verified in the present form.","major_comments":[{"comment":"The proof of Lemma 8 has two problems. First, the monotonicity of q_j is asserted without proof; it is true for greedy schemes via a coupling argument, but since this is load-bearing for the lower bound, it must be stated and proved. Second, the displayed inequality E[Σ q_j] ≥ Σ_{i} (n/2^i) q_{(1-1/2^i)n} is in the wrong direction for a nondecreasing sequence. For example, with n=8, q_1=...=q_3=0, q_4=...=q_8=10, the right side is 70 while the left side is 50. The intended argument requires the reverse inequality, obtained by partitioning the insertions into intervals [(1-1/2^{i-1})n, (1-1/2^i)n] and upper-bounding each q_j by the value at the right endpoint. As written, the proof does not establish Lemma 8, and Lemma 8 is essential for Theorem 4.","section":"Section 4, Lemma 8"},{"comment":"In the final paragraph of the proof, the text says the final insertion must perform 'at least ci log n expected probes' to find slots not in S; this should be ci log δ^{-1}. More importantly, the claim is not immediate from Lemma 8 and needs a proof: for a fixed probe sequence, the index of the first free slot at the final load is at least the index at the time of the (1 - 1/2^i)n-th insertion, so the number of probes landing in S is at least the corresponding number at that earlier time. Without this coupling argument, the additive lower bound on the total cost is unjustified.","section":"Section 4, Lemma 9"},{"comment":"The chain '2c = |{Hi : i∈[2c]}| = |{Hi : i∈[2c]}∩[n]| = E[|{Hi : i∈[2c]}∩[n]|]' is invalid: 2c is an upper bound on the number of distinct probes, not an equality, and the intermediate object is random. The correct argument is '2c ≥ E[|{Hi : i∈[2c]}|] ≥ Σ_j q_j', which then yields c = Ω(log δ^{-1}). The intended conclusion is correct, but the proof as written does not go through.","section":"Section 5.2, Theorem 5 proof"},{"comment":"There is a reversed inequality in the derivation of the bound on E[|t_i ∩ ∪_{j>i} H^c(k_j)|]. The text concludes |t_i| - |t_i|(nδ/|s_i|)^{1/8} < |t_i|/2 from (nδ/|s_i|)^{1/8} < 1/2, but if a < 1/2, then |t_i|(1-a) > |t_i|/2. Thus the claimed upper bound E[...] < |t_i|/2 does not follow; the preceding expression is close to |t_i| when |s_i| >> nδ. Since Claim 11 is necessary for Theorem 6, this is a load-bearing gap that needs a genuinely reworked proof, not just a typo fix.","section":"Section 5.3, Claim 11"},{"comment":"The amortized expected probe complexity analysis is not justified. The text asserts that the total expected probe complexity across all keys is at most |A1|·c log δ^{-1} + |A2|·2c log δ^{-1} + ... , but it does not prove a bound on the number of keys that reach each A_i. A key can fail in A_i even after A_i is full, so the number of attempts to A_i is not obviously O(|A_i|); an argument along the lines of 'the number of failures from A_i is at most the number of insertions that arrive after A_i is filled, which is geometrically decreasing' is needed. Without this, the O(log δ^{-1}) amortized claim in Theorem 2 is not established.","section":"Section 3, proof of Theorem 2 (amortized bound)"}],"minor_comments":[{"comment":"In the paragraph after the Chernoff bound, the text says the first 0.27m insertions 'can fill array A_{i+2}'; this should be A_{i+1}, since Case 3 depends on A_{i+1} being 75% full.","section":"Section 2, Lemma 2"},{"comment":"The McDiarmid exponent is written as exp(-|Ai| O(β^2 δ^2)), but the preceding calculation yields exp(-|Ai| O(δ^2/β^2)). The asymptotic conclusion n^{1-o(1)} is unchanged, but the exponent should be corrected.","section":"Section 3, Lemma 5"},{"comment":"The text says an insertion into C checks 'at most 2 log log n slots', but the probe sequence alternates between two buckets each of size 2 log log n, so the worst-case number of checked slots is 4 log log n. The asymptotic O(log log n) statement is unaffected.","section":"Section 3, A_{α+1} implementation"},{"comment":"The symbol L_j is used both for a set of locations and for individual locations L_i; this makes equations such as 'E[|Li∩vj|]' confusing. Please use separate notation for the set and for individual locations.","section":"Section 5.2, notation"}],"recommendation":"major_revision","confidential_remarks":"The main claims are likely correct and the paper is important, but the number of proof errors is higher than typical. The errors in Lemma 8 and Claim 11 are not mere typos: they invalidate the written proofs of Theorem 4 and Theorem 6. I would like to see a careful audit of all inequalities before resubmission; the proof of Claim 11 may require a new argument rather than a local fix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The central result here is genuinely new and important: greedy no-reordering hash tables have worst-case expected search cost Theta(log^2 1/delta), not Theta(1/delta), which settles Yao's 1985 conjecture in the unexpected direction. The upper bound (funnel hashing) is simple once you see it: geometrically shrinking blocks of buckets, ending in a special small table. The matching lower bound is the harder piece, and it is mostly sound.\n\nWhat the paper does well: elastic hashing is a genuinely clever decoupling of insertion probes from search probes, and it gives the first no-reordering scheme with O(1) amortized and O(log 1/delta) worst-case expected search cost, together with a matching general lower bound. The lower-bound technology—compressing the table after freezing a set S and applying Yao again—is clean. Credit where due: the authors also handle related work honestly, citing multilevel adaptive hashing and filter hashing as precursors for the funnel structure and using their own earlier work only for context.\n\nSoft spots, in proportion: the text is sloppy in places. Lemma 8 asserts monotonicity of expected insertion costs q_j without proof. It is true—for greedy insertion, fixing a probe sequence, a superset of occupied slots cannot move the first free slot earlier—but as written it is an unsupported step in a lower bound that carries the whole section. Lemma 9 is also compressed: the induction over n and the \"second-layer cost\" argument requires the reader to fill in that the compressed table is a valid greedy open-addressing instance and that S is conditioned correctly. I checked this and it goes through, but it is not referee-ready as written. There are local typos (A_{i+2} vs A_{i+1}, \"ci log n\" for \"ci log 1/delta\"), and the delta > O(1/n) / delta > O(1/n^{o(1)}) conditions are stated informally. None of this undermines the asymptotic claims.\n\nBottom line: this deserves serious peer review. It changes the landscape for open addressing, and the proofs are credible. With a cleanup of Lemmas 8 and 9 and a notation pass, it should be accepted. I would bring it to a reading group and would cite it.","headline":"Settles Yao's conjecture with matching bounds; the central claims hold up and the paper deserves a serious referee after a cleanup pass.","tokens_in":19786,"tokens_out":1597,"would_cite":true,"duration_ms":17089,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P20","68W40","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves tight bounds for open-addressed hash tables that never reorder items, showing a greedy scheme reaches O(log² δ⁻¹) worst-case expected probes and settling the classical conjecture that uniform probing is optimal.","keywords":["open addressing","hash tables","probe complexity","uniform hashing","greedy algorithms","worst-case expected complexity","no reordering","Yao conjecture"],"falsifier":"Fix any greedy open-addressing scheme, set δ = 2⁻ᵏ, and measure the expected probe count of the final insertion for k = 10, 20, 30, … with n large (say n = 2²⁰k). If the measured sequence is eventually below c·k² for every constant c, Theorem 4 is false; if funnel hashing itself is measured, the sequence should track Θ(k²), confirming the claimed exponent.","tokens_in":18875,"feed_emoji":"🔍","tokens_out":11693,"duration_ms":115484,"temperature":0.7,"pith_summary":"This paper shows that open-addressed hash tables can be made much faster than the classic uniform-probing design without ever moving already-inserted keys. One non-greedy scheme, elastic hashing, achieves O(1) amortized expected search cost and O(log δ⁻¹) worst-case expected search cost at load factor 1−δ. A greedy scheme, funnel hashing, achieves O(log² δ⁻¹) worst-case expected search cost, and the authors prove matching lower bounds: no greedy scheme can do better, and no no-reordering scheme can keep all keys below Ω(log² δ⁻¹ + log log n) with high probability. Together the upper and lower bounds disprove the long-standing conjecture that uniform probing is optimal for worst-case expected search cost, and they settle the optimal worst-case expected cost for greedy no-reordering tables at Θ(log² δ⁻¹).","feed_headline":"Greedy hashing hits its true cost: O(log² δ⁻¹) worst-case probes","feed_subtitle":"Matching lower bounds show no greedy or no-reordering scheme can do better, settling a 1985 conjecture about uniform probing.","key_machinery":"The load-bearing device is a two-dimensional probe sequence folded into one dimension by the injection φ(i,j) = O(i·j²), so a probe at row i and column j costs about i·j² probes. Elastic hashing uses this map to let an insertion probe far down a near-full array and then snap back to an earlier position in a less-full array, decoupling the number of probes made while inserting from the search probe complexity of the key. Funnel hashing instead groups the array into geometrically shrinking subarrays A₁,...,A_α plus a special final array A_{α+1}; a key tries one constant-size block in each subarray in order, and the final array uses a two-choice scheme with buckets of size O(log log n). The lower bounds run on the same structure: they use the monotonicity of expected greedy insertion costs and a compressed-table induction to force each level of slack to contribute a constant to the final insertion's expected cost, producing the sum ∑_{j=1}^{log δ⁻¹} c·j = Θ(log² δ⁻¹).","core_discovery":"The paper establishes tight bounds for open addressing without reordering. For greedy algorithms, it constructs funnel hashing, which splits the array into geometrically decreasing subarrays and probes one constant-size block in each, then falls back to a small two-choice final array; this gives worst-case expected probe complexity O(log² δ⁻¹) and, with high probability, O(log² δ⁻¹ + log log n). The matching lower bound shows the final insertion in any greedy scheme must take Ω(log² δ⁻¹) expected probes, so Θ(log² δ⁻¹) is the optimal worst-case expected search cost in the greedy setting. For non-greedy schemes, elastic hashing decouples probing during insertion from the position chosen, yielding O(1) amortized and O(log δ⁻¹) worst-case expected search cost, with a matching Ω(log δ⁻¹) lower bound for worst-case expected cost and a matching Ω(log² δ⁻¹ + log log n) high-probability lower bound. The consequence is that uniform probing is not optimal in the worst-case sense, and that open addressing can avoid the coupon-collector bottleneck without reordering.","pith_inferences":["An extension left implicit is whether the Θ(log² δ⁻¹) greedy optimum persists under adversarial key orders; the lower-bound proofs in Section 5 assume random keys and i.i.d. probe sequences, so an adversary choosing the key sequence could behave differently.","The decoupling idea in elastic hashing—probing many slots that the insertion does not use—may carry over to other allocation problems with coupon-collector bottlenecks, such as load balancing, by charging wasted probes to the insert operation rather than to the subsequent search.","The lower-bound constants in Lemmas 8 and 9 are not optimized; computing the actual constant c for small δ would give practitioners a sense of the crossover where funnel hashing beats double hashing in practice."],"forward_implications":["Greedy open addressing has optimal worst-case expected search cost Θ(log² δ⁻¹), so uniform probing's Θ(δ⁻¹) worst-case behavior is avoidable even with greedy insertions.","Open addressing without reordering can have constant amortized expected search cost, so reordering is not necessary to beat the coupon-collector bottleneck in amortized terms.","Funnel hashing guarantees with probability 1 − 1/poly(n) that every insertion probes O(log² δ⁻¹ + log log n) slots, and this high-probability worst-case bound is optimal among all no-reordering schemes.","Negative queries in greedy open-addressed tables have the same expected time as insertions, so funnel hashing also gives O(log² δ⁻¹) expected time for unsuccessful searches."],"supporting_citations":[{"why":"Supplies the classical amortized lower bound Ω(log δ⁻¹) used as Proposition 7, and is the uniform-hashing paper whose optimality conjecture is disproved.","marker":"[21]"},{"why":"Defines the standard uniform-probing model and the baseline Θ(log δ⁻¹) amortized and Θ(δ⁻¹) worst-case behavior that the paper improves on.","marker":"[13]"},{"why":"Supplies the heavily-loaded balanced-allocations theorem used to show the final two-choice subarray in funnel hashing never overflows with high probability.","marker":"[5]"},{"why":"Supplies the lower bound on maximum bin load for d-choice allocation used to prove the Ω(log log n) component of the high-probability lower bound.","marker":"[20]"},{"why":"Provides the proof template that the high-probability lower bound for no-reordering schemes mirrors, combining the Ω(log² δ⁻¹) and Ω(log log n) arguments.","marker":"[3]"}],"fun_headline_variants":["Funnel hashing achieves optimal open addressing without reordering","No-reordering hash tables reach optimal worst-case search","Yao's 1985 conjecture falls to elastic hashing","Optimal probe counts for hash tables without reordering","Funnel hashing: optimal open addressing, no reordering"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower bound for greedy schemes rests on Lemma 8's assertion that the expected cost of the j-th insertion is monotonically nondecreasing as the table fills; the paper states this follows from greedy behavior but does not prove it, and if this monotonicity failed the threshold argument would not go through.","fun_headline_variants_meta":{"raw":{"variants":["Funnel hashing achieves optimal open addressing without reordering","No-reordering hash tables reach optimal worst-case search","Yao's 1985 conjecture falls to elastic hashing","Optimal probe counts for hash tables without reordering","Funnel hashing: optimal open addressing, no reordering"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00063,"raw_usage":{"total_tokens":2875,"prompt_tokens":874,"completion_tokens":2001,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":1920}},"tokens_in":490,"tokens_out":2001,"duration_ms":15699,"temperature":1.0,"reasoning_tokens":1920,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:16:30.000406+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix any greedy open-addressing scheme, set δ = 2⁻ᵏ, and measure the expected probe count of the final insertion for k = 10, 20, 30, … with n large (say n = 2²⁰k). If the measured sequence is eventually below c·k² for every constant c, Theorem 4 is false; if funnel hashing itself is measured, the sequence should track Θ(k²), confirming the claimed exponent.","supporting_citations":[{"cited_title":"Uniform hashing is optimal","cited_arxiv_id":null,"evidence_quote":"Supplies the classical amortized lower bound Ω(log δ⁻¹) used as Proposition 7, and is the uniform-hashing paper whose optimality conjecture is disproved."},{"cited_title":"Balanced allocations: the heavily loaded case","cited_arxiv_id":null,"evidence_quote":"Supplies the heavily-loaded balanced-allocations theorem used to show the final two-choice subarray in funnel hashing never overflows with high probability."},{"cited_title":"How asymmetry helps load balancing","cited_arxiv_id":null,"evidence_quote":"Supplies the lower bound on maximum bin load for d-choice allocation used to prove the Ω(log log n) component of the high-probability lower bound."}],"review_version":1}