{"id":"be640914-24aa-4fa7-8ff9-7a416b2db09e","arxiv_id":"2607.13247","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In smoothed quadratic probing, anti-Robin Hood ordering achieves O(log ε^{-1}) expected query time while Robin Hood ordering degrades to Θ(ε^{-1/2}); almost all random fixed-offset degree-2 probing schemes are optimal under anti-Robin Hood.","lead":"Quadratic probing is a standard way to store data in hash tables, but its performance has resisted proof for fifty years. This paper studies a smoothed random version and finds that a 'poor-get-poorer' policy (anti-Robin Hood) gives near-optimal searches while the classic Robin Hood policy makes things worse; it also proves that almost every quadratic-like fixed-offset scheme is optimal under anti-Robin Hood.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Abstract's Θ(log ε^{-1}) for smoothed anti-Robin Hood is unsupported: only O(log ε^{-1}) is proved; the Ω(log ε^{-1}) lower bound is for fixed-offset schemes only. Table 1 correctly says O, so the abstract's matching claim overstates what is proven.","rationale":"The reader's verdict is CONDITIONAL, and my review agrees with that disposition. The central fixed-offset result (Theorem 3.3) and the Robin Hood upper/lower bounds are substantial, carefully argued contributions; I found no internal inconsistency in their proofs. The single load-bearing concern is the abstract's Θ(log ε^{-1}) claim for smoothed anti-Robin Hood probing, which is stronger than anything proved in the body: the upper bound is O(log ε^{-1}), and the only matching lower bound is for fixed-offset schemes, not for the per-key smoothed model. The paper's own Table 1 correctly lists O(log ε^{-1}) for smoothed anti-Robin Hood, making the abstract's Θ an internal overclaim. This does not undermine the main fixed-offset existence theorem or the Robin Hood lower bounds, so the paper should be accepted conditionally on correcting the abstract (or proving the missing lower bound). The reader's separate concern about the smoothed model being a proxy for actual quadratic probing is real but less load-bearing, since the paper explicitly disclaims analysis of the exact quadratic sequence; I therefore focus on the more concrete Θ-versus-O gap, with which the reader's rationale agrees.","tokens_in":44333,"tokens_out":23263,"duration_ms":233056,"concrete_test":"Settle the missing smoothed lower bound analytically: adapt Theorem 5.4 to per-key smoothed degree-d probing. For each j, define K_j so that a key activates about j offsets up to K_j, and let q_j be the expected fraction of slots free in the K_j-reveal. Attempt to prove a recurrence q_{j+1} ≥ q_j(1−q_j) using Harris's inequality on the independent activation bits, then derive Pr[pc(x) > j] ≥ Ω(1/j). If this recurrence can be established, the abstract's Θ(log ε^{-1}) is justified. If it cannot—or if a Monte Carlo check at n=2^20, ε=2^{-10} with mean successful probe complexity below 3 log2(1/ε) contradicts the polynomial tail—then the correct statement is O(log ε^{-1}) and the abstract should be revised to match Table 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract claims that, at load 1−ε, smoothed quadratic probing with anti-Robin Hood ordering achieves expected query time Θ(log ε^{-1}), matching the conjectured behavior of regular quadratic probing. The body does not prove this. Theorem 3.1 and Corollary 3.18 give only the upper bound O(log ε^{-1}) for smoothed anti-Robin Hood probing. The matching lower bound, Theorem 5.4, is stated and proved only for fixed-offset schemes, where all keys share one increasing offset sequence and a synchronous round-by-round insertion argument applies. Smoothed degree-d probing uses independent per-key activation bits, so Theorem 5.4 does not transfer directly; the lower-bound proof's shared-round structure (and its use of Harris's inequality on monotone events in the shared sequence) is not available in the per-key smoothed model. Thus the 'Θ' in the abstract is an overclaim: the paper proves O(log ε^{-1}) for smoothed anti-Robin Hood, and the matching Ω(log ε^{-1}) remains open for that model. The paper itself is internally inconsistent here—Table 1 lists the smoothed quadratic anti-Robin Hood query time as O(log ε^{-1}), not Θ(log ε^{-1}). This is the most load-bearing concern because it is the headline quantitative claim about the smoothed model, but it does not affect the fixed-offset Theorem 3.3 or the Robin Hood lower bounds, both of which appear well-supported. The correct fix is either to prove the missing smoothed lower bound or to downgrade the abstract's Θ to O.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper revisits quadratic probing through two randomized models: smoothed degree-d probing, where each key activates positive offset k independently with probability k^{-(d-1)/d}, and random fixed-offset degree-d probing, where all keys share a single random offset sequence r_j drawn uniformly from [αj^d, α(j+1)^d). The main formal results are: (i) for anti-Robin Hood ordering, an expected query-time upper bound O(log ε^{-1}) for d ≥ 2 and O(ε^{1-2/d}) for d < 2 at load 1−ε, including a simultaneous-all-(n,ε) version for fixed-offset sequences (Theorem 3.3); (ii) for Robin Hood ordering in smoothed probing, E[disp(x)] = O(ε^{-1}) and E[pc(x)] = O(ε^{-1/d}) (Theorem 4.1); and (iii) lower bounds, including a total-displacement lower bound, a smoothed Robin Hood lower bound Ω(ε^{-1/d}), and a logarithmic lower bound Ω(log ε^{-1}) for every fixed-offset anti-Robin Hood scheme (Theorem 5.4). The abstract goes further and claims Θ(log ε^{-1}) for smoothed anti-Robin Hood, but the body proves only O(log ε^{-1}) in that model; the matching lower bound is proved only for fixed-offset schemes.","tokens_in":44645,"tokens_out":15733,"duration_ms":147307,"significance":"If the main claims are correct, this is a substantial advance on a half-century-old problem. In particular, Theorem 3.3 gives, via the probabilistic method, fixed-offset polynomial probing sequences that, under anti-Robin Hood ordering, achieve the conjectured-optimal O(log ε^{-1}) expected query time simultaneously over all admissible load factors and table sizes, and Theorem 5.4 shows this is optimal among all fixed-offset anti-Robin Hood schemes. The proof machinery—local concentration bounds, the negative-feedback loop for short displacements, the drift/coupling arguments, the Robin Hood frontier process, and the technique of deriving lower bounds from upper-tail estimates—is original and is presented in considerable detail. The fixed-offset results and the Robin Hood lower bounds appear well supported. The paper is also careful to separate what is proved from what remains open for the exact quadratic sequence, although some headline phrasing blurs this distinction. The main issues are that the abstract and parts of the introduction overclaim the smoothed anti-Robin Hood Θ result, and one insertion-time corollary is internally inconsistent with the paper's own query-time bound.","major_comments":[{"comment":"The abstract states that smoothed quadratic probing with anti-Robin Hood ordering achieves expected query time Θ(log ε^{-1}), and Section 1.1 says the smoothed degree-d tradeoffs are tight for d ≤ 2. The body does not prove this. Corollary 3.18 gives only O(log ε^{-1}) for smoothed degree-d anti-Robin Hood, and Table 1 correctly lists O, not Θ, for this row. The matching lower bound, Theorem 5.4, is proved only for fixed-offset schemes, where all keys share one increasing offset sequence and the proof uses a synchronous round structure plus Harris's inequality on monotone events in the shared sequence; neither ingredient transfers to the per-key independent activation model of smoothed probing. Consequently the Θ(log ε^{-1}) claim for the smoothed model is an overclaim, and the claim that the tradeoffs are tight for d ≤ 2 in the smoothed setting is not supported by Corollary 5.3 or Corol","section":"Abstract, Section 1.1, Table 1, Corollary 3.18, Theorem 5.4"},{"comment":"Corollary 4.2 states that the amortized expected insertion time under Robin Hood smoothed degree-d probing is O(ε^{-1}). This is inconsistent with Theorem 4.1, which gives E[pc(x)] = O(ε^{-1/d}), and with the paper's own conversion rule (1), f(ε) = -d/dε g(ε). If g(ε) = E[pc] = Θ(ε^{-1/d}), the derivative is Θ(ε^{-1-1/d}), not Θ(ε^{-1}); if one differentiates E[disp] = Θ(ε^{-1}), one gets Θ(ε^{-2}). Table 1 and the introduction correctly list Θ(ε^{-1-1/d}) (e.g., Θ(ε^{-3/2}) for d = 2). Corollary 4.2 as written is therefore an error and should be corrected to Θ(ε^{-1-1/d}).","section":"Section 4, Corollary 4.2, Eq. (1), Table 1"},{"comment":"The framing of the 'Fall of Robin Hood' as a statement about quadratic probing itself is stronger than what is proven. The separation between Robin Hood and anti-Robin Hood is proven in the smoothed model (Theorem 4.1 and Corollary 3.18), and the anti-Robin Hood optimality for fixed-offset schemes is proven in Theorem 5.4, but the exact quadratic probe sequence remains unanalyzed. The paper is admirably explicit about this in the abstract and Section 1.1, yet the title and the introductory discussion of questions (1)–(3) present the conclusions as answers for quadratic probing. This should be rephrased so that the model dependence is prominent in the headline statements, not only in the technical sections.","section":"Section 1.1, Abstract"}],"minor_comments":[{"comment":"The statement that stable degree-d probing takes Ω(ε^{-1}) time for negative queries is asserted without proof or citation. If it is a known result, a reference should be supplied; if it is a folklore fact, a one-sentence argument would help.","section":"Section 1.1, first bullet"},{"comment":"The table is internally consistent with the body, but it would be helpful to mark explicitly which rows are Θ and which are only O for the smoothed anti-Robin Hood model, given the discrepancy between the abstract and Table 1.","section":"Table 1"},{"comment":"The proof of (26) is terse for the case of ε bounded away from zero. It is true that a positive constant lower bound holds, but the exposition would be clearer if the Poisson approximation were used directly, or if the constant were tracked explicitly.","section":"Section 5.1, Lemma 5.1"}],"recommendation":"major_revision","confidential_remarks":"The fixed-offset anti-Robin Hood results and the Robin Hood lower bounds are strong and appear sound. The main blocker is the unproven Θ(log ε^{-1}) claim for the smoothed anti-Robin Hood model, which is stated in the abstract and used in the introduction's 'tightness' claims, plus the inconsistent Corollary 4.2. These are fixable by rephrasing or by adding the missing lower bound; I would not recommend rejection because the core technical contributions are valuable and the errors are local to the presentation of the results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a serious paper, worth refereeing, but the abstract oversells one result. The fixed-offset anti-Robin Hood theorem (Thm 3.3) is the real centerpiece and looks well supported. The smoothed-model results are also solid as upper bounds, but the Θ(log ε^{-1}) in the abstract for smoothed anti-RH is not proven — only O(log ε^{-1}) appears in the body (Cor 3.18), and the matching lower bound (Thm 5.4) holds for fixed-offset schemes, not for the per-key smoothed model. Table 1 already says O, so the abstract is simply inconsistent with the paper's own summary.\n\nThe negative-feedback-loop argument is genuinely new and gives the first provably optimal query-time guarantees for a broad class of quadratic-probing-like tables under anti-Robin Hood. The drift-bound probabilistic-method construction of a single offset sequence that works for all ε and n is elegant. The lower-bound technique that starts from the upper-tail bounds and forces a first-moment lower bound is a nice trick. The Robin Hood frontier process is well executed and gives the Θ(ε^{-1/d}) result for smoothed degree-d probing, which matches the lower bound.\n\nSoft spots: besides the abstract overclaim, the smoothed extension of Thm 3.1 is somewhat compressed — Lemma 3.17 is stated and the reader is told the rest follows, but a few details are left out. The paper is also honest that the smoothed model is a proxy; the actual quadratic probing sequence remains unanalyzed. That's fine, but it means the \"Fall of Robin Hood\" conclusion is about the smoothed model, not about regular quadratic probing. The relevance to practice is therefore indirect, though the paper frames this appropriately.\n\nSend it to review. The authors should be asked to fix the abstract and ideally to add a short discussion that the smoothed lower bound is open. If they can't prove the lower bound, the Θ should become O and the open problem should be stated explicitly. The fixed-offset results are important enough that this should not be desk-rejected.","headline":"A serious theory paper with a real fixed-offset result and a genuine smoothing-based separation, but the abstract overclaims a Θ(log ε^{-1}) for smoothed anti-Robin Hood that the body only proves as O.","tokens_in":45238,"tokens_out":2881,"would_cite":true,"duration_ms":26089,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P05","68P20","68W20","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Quadratic probing becomes optimal if the least-travelled key wins","keywords":["quadratic probing","anti-Robin Hood ordering","smoothed analysis","open addressing","probabilistic method","expected query time","hash table"],"falsifier":"Simulate deterministic quadratic probing (offset sequence 0,1,4,9,16,...) under anti-Robin Hood ordering at load 1−ε for ε = 0.1, 0.01, 0.001 and measure the expected successful-query time. If the growth is closer to ε⁻¹/² rather than log ε⁻¹, the smoothed-versus-deterministic transfer fails. Conversely, finding one degree-2 fixed-offset sequence for which the expected query time grows faster than O(log ε⁻¹) would contradict the 'almost every' claim of Theorem 3.3.","tokens_in":44067,"feed_emoji":"🗂️","tokens_out":5098,"duration_ms":45737,"temperature":0.7,"pith_summary":"The paper tries to settle a half-century-old question about quadratic probing by changing one design choice: the collision-ordering rule. It argues that when collisions are resolved by favouring the key that has travelled the least (anti-Robin Hood ordering), essentially every quadratic-probing-like scheme achieves the conjectured ideal: expected query time O(log ε⁻¹) and amortized insertion time O(ε⁻¹) at load factor 1−ε. In contrast, the widely used Robin Hood rule, which favours the most-travelled key, provably loses a factor of √ε, with expected query time Θ(ε⁻¹/²) in the smoothed model. The results are obtained through a smoothed variant of quadratic probing and then extended by the probabilistic method to almost every fixed-offset degree-d probing sequence, with the honest caveat that the exact quadratic sequence 0,1,4,9,... remains unanalyzed.","feed_headline":"Quadratic probing becomes optimal if the least-travelled key wins","feed_subtitle":"Almost every quadratic-style table reaches O(log 1/ε) query time; Robin Hood lags behind.","key_machinery":"The argument rests on three pieces. First, a concentration framework for local intervals: in a table with anti-Robin Hood ordering, the number of free slots in any interval of K slots depends only on keys hashing into a nearby window and changes by at most one when a single key is added, yielding exponential tail bounds. Second, a negative-feedback loop: if many keys survive past displacement K, then the K-reveal must contain many free slots in the next interval, and a typical key probes enough of them that the chance it survives to displacement 5K drops by a constant factor; this forces the tail of displacements to decay like K^{-1/2} (degree 2) and yields the O(log ε⁻¹) bound by summing ov","core_discovery":"The central claim is that anti-Robin Hood ordering rescues quadratic-style probing. For random fixed-offset degree-d probing with d≥2, the paper proves (Theorem 3.3) that with probability 1−δ over the choice of the shared offset sequence, the resulting table supports worst-case expected query time O(log ε⁻¹) simultaneously for every table size n and every slack ε above a logarithmic threshold, with amortized insertion time O(ε⁻¹). This matches the long-conjectured performance of quadratic probing and is best possible for any fixed-offset anti-Robin Hood table. Separately, for smoothed degree-d probing with Robin Hood ordering (Theorem 4.1), the paper proves expected displacement O(ε⁻¹) and e","pith_inferences":["A testable consequence: in simulation, deterministic quadratic probing (offsets 1,4,9,...) with anti-Robin Hood ordering should show near-logarithmic expected successful query times at high load; if it instead exhibits Θ(ε⁻¹/²) scaling, the smoothed model is not a faithful proxy.","The negative-feedback-loop mechanism is not tied to polynomial offsets; it may transfer to other structured probe families, potentially yielding optimal anti-Robin Hood tables with even more cache-friendly offsets.","The probabilistic-method result suggests an explicit derandomization problem: construct a single fixed-offset degree-2 sequence, ideally as close to squares as possible, that provably satisfies the O(log ε⁻¹) bound.","The Robin Hood frontier process could be reused to analyze other history-independent insertion policies where the priority rule is monotone in displacement."],"forward_implications":["There exist concrete quadratic-probing-like hash tables with provably optimal O(log ε⁻¹) expected query time and O(ε⁻¹) amortized insertion time at load 1−ε, under anti-Robin Hood ordering.","Since the bound is tight for any fixed-offset anti-Robin Hood scheme, degree 2 is the smallest probing degree that fully escapes linear-probing clustering.","Robin Hood ordering is shown to be the wrong choice for quadratic-style probing: it provably degrades query time to Θ(ε⁻¹/²) in the smoothed model.","The smoothed analysis identifies smoothed quadratic anti-Robin Hood probing as the best scheme among the considered options, and motivates studying it further.","If the smoothed model faithfully reflects real quadratic probing, the long-conjectured O(log ε⁻¹) behavior is not only plausible but generic among nearby probe sequences."],"fun_headline_variants":["Anti-Robin Hood ordering yields optimal quadratic probing query time","Almost every quadratic-style table hits O(log 1/ε) with anti-Robin Hood","Robin Hood loses: anti-ordering gives optimal quadratic probing","Anti-Robin Hood makes quadratic probing optimal in expectation","For quadratic probing, the anti-Robin Hood ordering wins"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The paper's headline separation—Robin Hood falling to Θ(ε⁻¹/²) while anti-Robin Hood reaches O(log ε⁻¹)—is proved in a smoothed model in which each key independently samples its offsets, and the exact quadratic probing sequence remains unanalyzed; if that smoothed model is not a faithful proxy, the separation may not transfer to actual quadratic probing.","fun_headline_variants_meta":{"raw":{"variants":["Anti-Robin Hood ordering yields optimal quadratic probing query time","Almost every quadratic-style table hits O(log 1/ε) with anti-Robin Hood","Robin Hood loses: anti-ordering gives optimal quadratic probing","Anti-Robin Hood makes quadratic probing optimal in expectation","For quadratic probing, the anti-Robin Hood ordering wins"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000968,"raw_usage":{"total_tokens":4014,"prompt_tokens":862,"completion_tokens":3152,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":606,"completion_tokens_details":{"reasoning_tokens":3065}},"tokens_in":606,"tokens_out":3152,"duration_ms":29036,"temperature":1.0,"reasoning_tokens":3065,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T05:46:04.570367+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate deterministic quadratic probing (offset sequence 0,1,4,9,16,...) under anti-Robin Hood ordering at load 1−ε for ε = 0.1, 0.01, 0.001 and measure the expected successful-query time. If the growth is closer to ε⁻¹/² rather than log ε⁻¹, the smoothed-versus-deterministic transfer fails. Conversely, finding one degree-2 fixed-offset sequence for which the expected query time grows faster than O(log ε⁻¹) would contradict the 'almost every' claim of Theorem 3.3.","supporting_citations":[],"review_version":1}