{"id":"b599750e-66d2-42e3-a683-19e0e2a5fe6e","arxiv_id":"2501.11582","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Linear probing with tombstones has amortized expected insertion time Θ(x log^{1.5} x), with matching upper and lower bounds, resolving the open gap from FOCS 2021.","lead":"A new proof settles a long-open question about how fast insertions can be in a common type of hash table, showing the amortized time is nearly linear in the inverse load factor. The analysis also cracks a purely geometric problem about random dots and paths, and it explains why practical linear-probing tables behave well under churn.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Θ(x log^{1.5}x) linear-probing claims rest on unverified black-box lemmas from [4]; a hidden flaw in Lemmas 5.1/5.2/5.5/5.8 would invalidate Theorems 1.3–1.4 even though the path-surplus bound may stand.","rationale":"The paper's main technical novelty is the path-surplus analysis in Section 3, which is self-contained and appears internally consistent; I found no fatal flaw there. The linear-probing application, however, leans on four cited results from [4] that map crossing numbers to operation times and reduce to hovering workloads. These lemmas are load-bearing for Theorems 1.3 and 1.4: without them, Proposition 5.3 cannot be turned into operation-cost bounds. Because the paper does not verify these lemmas and the parameter regime here is specific (β ≤ x, R = n/β), this is the least secure point of the central claim. The reader's weakest-assumption identification is accurate. A conditional acceptance — with verification of the cited lemmas as a condition — is the appropriate verdict. If the lemmas check out, the paper can be accepted as is.","tokens_in":42906,"tokens_out":31753,"duration_ms":323787,"concrete_test":"Independently re-derive Lemmas 13 and 14 and Proposition 7 of [4] (the sources of Lemmas 5.1, 5.2, 5.5, 5.8) from first principles in this paper's parameter regime. Specifically: (i) prove that E[time per insertion] = Θ(x + (1 + n/R)E[c_i]) with the exact constants needed for Theorem 1.3; (ii) prove that the hovering-workload reduction changes Σ c_i by at most O(nx) under load factor at most 1 − 1/x. If either step requires an assumption not stated in the present paper, the linear-probing theorems must be revised or re-proved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central insertion-time theorems (Theorem 1.3 for ordered and Theorem 1.4 for unordered probing) are not derived end-to-end in this paper: they inherit four conversion lemmas from Bender et al. [4] — Lemma 5.1 and 5.2 (crossing numbers to/from per-operation time), Lemma 5.5 (crossing number equals surplus minus free slots), and Lemma 5.8 (reduction to hovering workloads). Proposition 5.3, the quantitative heart of the linear-probing analysis, assumes all four. The paper cites 'Lemmas 13 and 14 of [4]' and 'Proposition 7 of [4]' without reproducing their proofs or checking their hypotheses in the exact regime used here (1 ≤ β ≤ x, R = n/β, load factor reaching 1 − 1/x). If, for example, Lemma 5.8's O(nx) slack fails when the initial table is not in the specific distribution assumed, or if Lemma 5.1's (1 + n/R) factor has a different constant, the matching Θ(x log^{1.5}x + βx) bound collapses even though the path-surplus bound Θ(m log^{0.75}m) is self-contained and plausible.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper resolves the path surplus problem, proving that the expected maximum surplus of a monotonic path through an m-by-m grid with independent blue and red Poisson dots is Θ(m log^{0.75} m), and then transfers this result to linear probing. The authors derive matching upper and lower bounds of Θ(x log^{1.5} x) for the amortized expected insertion/deletion time in ordered linear probing with tombstones and rebuild windows, and they obtain analogous bounds for classical unordered linear probing under an average-case workload. The main technical work is a new lower-bound construction based on a recursive random walk and an upper bound using frame decompositions, potential functions, and an entropy-compression argument.","tokens_in":43174,"tokens_out":32044,"duration_ms":325894,"significance":"If the technical gaps discussed below are repaired, this is a significant advance: the path surplus problem is settled with a clean Θ(m log^{0.75} m) bound, and the paper gives the first tight asymptotic characterization of the amortized insertion time for linear probing with tombstones. The path-surplus upper bound is a substantial and largely self-contained contribution, and the idea of isolating three 'core facts' to transfer the analysis from the Poisson path-surplus setting to insertion surpluses is elegant. The linear-probing results are conditional on several lemmas from Bender et al. [4]; this is a legitimate dependency rather than a circularity, but the authors should verify that all hypotheses of those lemmas are met in the exact parameter regime used here.","major_comments":[{"comment":"The proof of Proposition 4.7 has an independence gap. In the modified insertion-surplus process, Core Fact 1 (Lemma 4.4) establishes independence only for vertical strips. Lemma 3.10, which is used verbatim in the transfer, decomposes the maximum transitional gain into a sum over j of random variables X_j that are argued to be independent because each depends on the dots in a strip between consecutive level-ℓ diagonals. These strips are not vertical, and in the insertion-surplus process a single Poissonized x-column can contribute dots to more than one such diagonal strip (for example, a key that is inserted at time i and deleted at time i' yields two dots in the same column at different times). The independence assertion in Lemma 3.10 therefore does not follow from Lemma 4.4. The authors need either to prove the needed independence for diagonal strips directly in the modified process, or to rework the frame decomposition so that it only relies on vertical-strip independence.","section":"Section 4.1, Lemmas 4.4 and 3.10, Eq. (12)"},{"comment":"The tail bound on the sum ∑_ℓ A_{ℓ,s}K_ℓ is not justified as written. The proof states that this sum is bounded above by a binomial random variable with mean s/4, but A_{ℓ,s} is the event F_ℓ ≤ s + βs/8, and F_ℓ depends on the same sequence of failed deletions K_ℓ. The summands are therefore not independent and are not stochastically dominated by the claimed binomial merely because each conditional mean is at most (s+βs/8)/n. This step is load-bearing for Proposition 6.3 and hence for Theorem 1.4. A martingale or coupling argument is needed to justify the claimed 2^{-Ω(s)} decay.","section":"Section 6.1, Lemma 6.5, Eq. (36)"}],"minor_comments":[{"comment":"The display for t and the subsequent asymptotic bounds are garbled. With the intended t = (x^2/(qβ)) log^{1.5} x, the lower bound should read Ω((x/(β√q)) log^{1.5} x − (x/(qβ)) log^{1.5} x), which yields the claimed Ω(x log^{1.5} x / β) after summing over s. Please correct the typesetting and the intermediate inequalities.","section":"Lemma 5.6"},{"comment":"In the definition of surplus(O, [j−t,t]), the interval should be [j−t, j], consistent with the surrounding notation.","section":"Corollary 4.12"},{"comment":"The sentence 'This proves (21), which then implies (18) and (19)' should refer to (18) and (20), since (19) is proved separately by direct calculation.","section":"Lemma 3.13"},{"comment":"The bound |C_q| ≤ 2^{O(q)+ℓ} does not match the previously stated unary encoding length O(‖Δ(F)‖_1 + 2^ℓ). The correct bound is |C_q| ≤ 2^{O(q + 2^ℓ)}; the subsequent argument still works when α is sufficiently large, but the display should be fixed.","section":"Lemma 3.14"},{"comment":"The claim that the partial smoothing step 'does not change surplus(P)' is not immediate for arbitrary monotone paths and for dots lying on the path boundary. Please add a formal argument or state the convention used for points on the path.","section":"Lemma 4.1"},{"comment":"The notation P_0 is used in the telescoping sum near the end of the proof but is not defined; it should denote the set of rigid paths at level 0.","section":"Lemma 3.8"},{"comment":"There is a typo in 'wort-case'; it should be 'worst-case'.","section":"Corollary 5.4"}],"recommendation":"major_revision","confidential_remarks":"The path-surplus core is strong and likely correct, and the paper contains a genuinely novel technical framework. My two major comments concern the transfer from path surplus to linear probing: the independence issue in Section 4.1 and the stochastic-domination claim in Section 6.1. Both are localized and appear fixable, so I am recommending major revision rather than rejection. The reliance on Bender et al. [4] for Lemmas 5.1, 5.2, 5.5, and 5.8 is a standard dependency, but I would encourage the authors to restate the precise hypotheses and verify them for 1 ≤ β ≤ x and R = n/β, since the matching Θ(x log^{1.5} x + βx) claim would collapse if any of those lemmas does not apply in this regime."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version. The path surplus problem is genuinely cracked: the Θ(m log^{0.75} m) bound, both the recursive lower-bound construction and the potential-function upper bound, looks like new mathematics and the proof is self-contained. The insertion-time theorems are a sharper transfer from Bender et al.'s crossing-number machinery, and given that machinery they do close the open gap with Θ(x log^{1.5} x).\n\nThe paper earns credit for two things beyond the statement. First, the lower-bound construction via a random recursive path that becomes a martingale walk is elegant, and Lemma 3.1 (disjoint critical regions) is a clean key. Second, the potential functions Φ and Ψ together with the entropy-compression argument in Lemma 3.8 are a serious technical step, and the unordered-probing extension is not a trivial corollary. The core facts in Section 3.2 are explicit and reused cleanly in the insertion-surplus setting.\n\nThe soft spot is exactly the stress-test note. Theorems 1.3 and 1.4 are not derived end-to-end here: Lemmas 5.1, 5.2, 5.5, and 5.8 are quoted from Bender et al. [4] with references to their proofs, and the paper does not re-derive them or check that their hypotheses hold in the exact regime (β ≤ x, R = n/β, load factor reaching 1 − 1/x). That is a normal and explicit dependency in this line of work, not a circularity — the path surplus bound does not depend on it — but it does mean the headline claim is conditional on the prior lemmas being correct in the needed generality. I'd want a referee to specifically verify that Lemmas 9/10/13/14 and Proposition 7 of [4] apply without hidden slack when called with these parameters. The lower-bound workload in Lemma 5.6 also has a 'set q to a large constant' step that deserves checking, though it looks sound.\n\nOverall, this is a strong paper for a theory audience. The path-surplus result alone is publishable, and the linear-probing consequence is significant if the black-box dependencies hold. I'd send it to a serious referee rather than desk reject, and I'd cite it in future work on linear probing.","headline":"The path-surplus result is the real deal; the linear-probing theorems close the FOCS'21 gap but lean on black-box lemmas from [4].","tokens_in":43738,"tokens_out":2652,"would_cite":true,"duration_ms":29677,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W40","60C05","68P05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Linear probing's amortized high-load insertion cost is $\\Theta(x \\log^{1.5} x)$, with matching upper and lower bounds.","keywords":["linear probing","hash tables","amortized analysis","path surplus","tombstones","anti-clustering","random walks","high load factor"],"falsifier":"Run the path-surplus experiment for $m = 2^8, 2^{10}, \\dots, 2^{18}$ and compare the observed maximum surplus against $c m \\log^{0.75} m$; if the growth rate is not within a constant factor of that curve, the central geometric claim is wrong. A second check is to implement ordered linear probing with tombstones at load factor $1 - 1/x$ with rebuild window $n/\\log^{1.5} x$ and measure the amortized expected insertion time, which should grow as $\\Theta(x \\log^{1.5} x)$.","tokens_in":42701,"feed_emoji":"📐","tokens_out":12658,"duration_ms":113632,"temperature":0.7,"pith_summary":"Linear-probing hash tables were long believed to have expected insertion time $\\Theta(x^2)$ at load factor $1 - 1/x$. This paper proves, with matching upper and lower bounds, that the amortized expected insertion/deletion time of an ordered linear-probing table with tombstones is $\\Theta(x \\log^{1.5} x)$ when the rebuild window is chosen optimally, while queries cost $\\Theta(x)$. The combinatorial engine is the path-surplus problem: the maximum over monotone paths of blue-minus-red dots beneath the path in a random $m \\times m$ grid, which the paper determines to be $\\Theta(m \\log^{0.75} m)$. The same tight bounds are extended to classical unordered linear probing under the average-case workload of deleting random elements and inserting new ones, showing that the anti-clustering effect is not an artifact of ordering.","feed_headline":"Linear probing's high-load cost settles at Θ(x log^{1.5}x)","feed_subtitle":"A random path-surplus bound of Θ(m log^{0.75}m) sets the optimal rebuild window.","key_machinery":"The load-bearing object is the path-surplus problem: place $\\mathrm{Pois}(m^2)$ blue and $\\mathrm{Pois}(m^2)$ red dots uniformly in $[0,m]^2$, and define the surplus of a monotone path as the number of blue dots minus red dots beneath it. The lower bound builds a path by recursively splitting a segment and shifting its midpoint by $\\pm w_L/\\sqrt{\\log m}$ according to the surplus of a thin rectangle $R_L$; the rectangles at distinct tree nodes are disjoint, so the induced random walk has independent steps and reaches depth $\\Theta(\\log m)$ with constant probability. The upper bound discretizes paths by the diagonal lines they cross at scales $d_\\ell = m/2^\\ell$, then bounds the surplus gain at each level minus two potential functions, the transition potential $\\Phi$ and the frame potential $\\Psi$, whose sums over all levels are $O(m \\log^{0.75} m)$. This geometric bound is transferred to insertion surplus through Poissonization, smoothing, and rescaling, and then to linear probing through crossing-number identities of the form $c_s = \\max_{i