{"id":"586b68ee-1b8d-4c33-b966-095766ad971f","arxiv_id":"2508.19785","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"RiffleSort sorts n elements with persistent random comparison errors (p<1/4) in O(n log n) time with O(log n) maximum and O(n) total dislocation, with matching lower bounds.","lead":"A new sorting algorithm, RiffleSort, sorts n items in O(n log n) time while keeping each item within O(log n) places of its true position and with only O(n) total displacement, even when every comparison has a small chance of being wrong and the error is permanent. The paper also argues these guarantees are optimal for error probability below 1/4.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.7's Hoeffding step conditions on the good/happy event while still treating the persistent score-comparison variables as independent; those same variables helped determine that event, so the conditional independence and the resulting w.h.p. bounds are unsupported.","rationale":"The paper's central claim is that RiffleSort achieves O(n log n) time, O(log n) maximum dislocation, and O(n) total dislocation with high probability for persistent random comparison faults with p < 1/4. The upper-bound proof flows through Theorem 5.20, whose most delicate part is BasketSort's analysis. Lemma 5.7 is the first place where persistent comparison outcomes are reused under a conditioning event: the sequence S_w is error-dependent, and 'good'/'happy' are properties of that sequence. The proof nevertheless asserts that the X_z variables are independent after conditioning. That assertion is not justified by the model and is load-bearing: Lemmas 5.9, 5.10, 5.12, and 5.15 depend on it, and Theorem 3.5 depends on them. This is an internal proof gap rather than a disagreement with the existing literature. I am not claiming the theorem is false; a well-chosen unconditional reformulation may repair the argument. The proposed test directly checks whether such a repair exists. Because the reader already marked the paper CONDITIONAL for essentially this same gap, my read does not move the verdict.","tokens_in":48971,"tokens_out":11994,"duration_ms":148609,"concrete_test":"Independently re-derive Lemma 5.7 without invoking conditional independence: fix the actual random history of BasketSort, compute E[X_z | history] and the conditional dependence among the eX_z, and verify that the sum eX is stochastically dominated by a binomial with the same Hoeffding tail. Equivalently, write the conditioning event E as a function of the persistent pair outcomes and show whether Pr(X_z=1, X_z'=1 | E) = Pr(X_z=1|E)Pr(X_z'=1|E) for every pair of variables whose outcomes were used to form S_w. Then propagate the resulting bound through Lemmas 5.9 and 5.10, dividing by Pr(E) at each induction step; if the final failure probability still has the form O(m^{-3}) at w = Θ(log m), the concern is resolved, otherwise Theorem 5.20 requires a new proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the proof of BasketSort's per-round ranking guarantee. In Lemma 5.7, after conditioning on the event E that all elements in B+ are good and all elements in B are happy, the proof says 'all the X_z are independent random variables' and applies Hoeffding. But the X_z are functions of persistent pairwise comparison outcomes, and these same outcomes were used in earlier rounds to produce the sequence S_w whose properties define E. Under the persistent model each pair's outcome is fixed once and is not resampled, so Pr(· | E) is a conditional distribution in which the X_z are generally not independent; Hoeffding's inequality does not apply as written. This is not cosmetic: Theorem 5.20 explicitly allows the input sequence to be chosen as a function of the errors, and in RiffleSort the sequence handed to BasketSort is produced by earlier error-dependent rounds. Lemmas 5.9, 5.10, 5.12, and 5.15 all reuse this step, so the maximum-dislocation and total-dislocation guarantees of BasketSort, and therefore of RiffleSort (Theorem 3.5), rest on it. A possible repair is to replace the conditional bound by an unconditional tail bound and divide by Pr(E); but Lemma 5.15's induction uses windows where Pr(E) may be only 1 - O(1/w^2), so the correction factor is not obviously absorbed. The paper does not provide such a derivation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies sorting n elements under persistent random comparison faults, where each pair's outcome is wrong with probability at most p and comparing the same pair repeatedly returns the same result. The main contribution is RiffleSort, a randomized O(n log n)-time sorting algorithm that, for p < 1/4, returns a sequence with maximum dislocation O(log n) and total dislocation O(n) with high probability. The algorithm combines two subroutines: NoisySearch, which approximates the rank of an external element in an almost-sorted sequence in O(log n) time, and BasketSort, which reduces the maximum and total dislocation of an approximately sorted sequence in O(m d) time. The paper also proves lower bounds showing that no algorithm can achieve maximum dislocation o(log n) with high probability or total dislocation o(n) in expectation, and it sketches a time lower bound. A derandomized variant is given under a lower bound q > 0 on the error probability. The main technical work is in Section 5, where BasketSort is analyzed through successive window-shrinking rounds; the analysis uses a conditional independence step in Lemma 5.7 that is currently not justified.","tokens_in":49332,"tokens_out":10290,"duration_ms":120034,"significance":"If the main theorem is correct, the paper settles the complexity of approximate sorting under persistent random comparison faults for p < 1/4, improving the previous best O-tilde(n sqrt n) time and giving matching dislocation lower bounds. The proposed BasketSort subroutine is a genuinely new technique, and the NoisySearch subroutine is a natural and useful primitive. The paper is largely self-contained, with explicit constants in the construction and a clear separation of the max- and total-dislocation analyses. The lower-bound section uses an elegant swap argument. However, the central probabilistic claim in BasketSort's Lemma 5.7 is load-bearing and is not fully justified; as written, the proof applies Hoeffding's inequality to variables that are treated as independent conditional on an event that depends on those very variables. This gap must be addressed before the guarantees of Theorem 5.20 and hence Theorem 3.5 can be considered established.","major_comments":[{"comment":"Lemma 5.7 conditions on the event E that all elements in B+ are good and all elements in B are happy, and then states 'all the X_z are independent random variables' before applying Hoeffding's inequality. Unconditionally the X_z are independent because comparison outcomes for distinct pairs are independent. But E is a property of the sequence S_w, and S_w is itself produced by earlier rounds of BasketSort from the persistent comparison outcomes, including outcomes involving x, y, and the elements z. Thus Pr(· | E) is a conditional distribution in which the X_z need not be independent; the same persistent outcome can influence both E and X_z. The paper gives no argument that the conditional law factors, and Theorem 5.20 explicitly allows the input sequence S to be chosen as a function of the errors, while in RiffleSort the sequence handed to BasketSort is error-dependent. This step is loa","section":"5.2, Lemma 5.7"},{"comment":"The abstract and introduction claim that O(n log n) time is optimal, and the phrase 'settles the time complexity' is used. However, the time lower bound is only sketched in the introduction: it asserts that a sequence with maximum dislocation d = O(log n) can be converted to a perfectly sorted sequence in O(n/log n · ((log n)(log log n))) = o(n log n) time. No formal reduction or theorem is stated or proved in the paper; Section 6 proves only the max-dislocation and total-dislocation lower bounds. Since the claimed time optimality is part of the paper's central contribution, the reduction should be formalized. A standard heap-of-size-d+1 argument sorts any sequence with max dislocation d in O(n log d) comparisons, which would give O(n log log n) for d = O(log n), so the claim is likely true, but it needs a proof in the manuscript.","section":"1.1 / 3"}],"minor_comments":[{"comment":"The text 'Sort4' should be 'Sort'; the superscript '4' appears to be a formatting artifact.","section":"Algorithm 2, line 7"},{"comment":"In the displayed equation after Equation (1), 'score(𝑦)− score(𝑦)' should read 'score(𝑦)− score(𝑥)'.","section":"5.2, proof of Lemma 5.7"},{"comment":"In the definition of a bad vertex, the second case should be 'i* > max I(u) + cd', not 'i* > max I(u) − cd'.","section":"4.4, Lemma 4.4"},{"comment":"The equality '69120/((1−ρ)(1−ρ^2)w^2) = 69120/((1−ρ)^3 w^2)' is not an equality; the right-hand side is an upper bound. The subsequent bound remains valid, but the equality symbol should be '≤'.","section":"5.3, Lemma 5.15"},{"comment":"In the proof of Lemma 5.18, 'τ_w(y) > τ_w(w)' should be 'τ_w(y) > τ_w(x)'.","section":"5.3, Lemma 5.18"}],"recommendation":"major_revision","confidential_remarks":"The main algorithmic idea is strong and the result is likely correct, but the conditional-independence gap in Lemma 5.7 is exactly the kind of issue that must be closed before publication; it affects the central theorem. I would also ask the authors to formalize the time lower-bound reduction rather than leaving it as an informal paragraph. If these points are fixed, the paper would be a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—here's my read on the RiffleSort paper. The headline: the result is the real thing if the analysis can be patched, but as written the proof of the main upper bound has a hole that the authors need to address.\n\nThe contribution is genuinely new: an O(n log n) time algorithm for persistent random comparison faults with p < 1/4, matching the comparison-based lower bound and achieving O(log n) max and O(n) total dislocation. That's a significant step past the previous O~(n sqrt n) algorithm. The two subroutines, NoisySearch and BasketSort, look clever, and the derandomization section is a nice extra. The lower bounds for max and total dislocation in Section 6 are clean and I think they're correct.\n\nThe soft spot is Lemma 5.7. The proof conditions on the event that all elements in B+ are good and those in B are happy, then says 'all the X_z are independent random variables' and applies Hoeffding. That step is not justified. The X_z are built from persistent comparison outcomes, and the same outcomes were used in earlier rounds to construct the sequence S_w that defines the conditioning event. Conditional on E, the X_z are generally not independent, so Hoeffding does not apply as written. This is load-bearing: Lemmas 5.9, 5.10, 5.12, and 5.15 all rely on it, hence so do the max and total dislocation guarantees of BasketSort and the main theorem. The paper does not provide a substitute argument, and the natural repair—unconditional tail bound divided by Pr(E)—is not obviously absorbed because some of the relevant windows have failure probability around 1/w^2.\n\nThere's also a smaller issue: the time lower bound that justifies 'optimal' is only sketched in the introduction, not proved. That's less serious since the upper bound is the hard part, but the title overstates what is actually established.\n\nWorth a serious referee? Yes. This is an important question in the area, and the gap seems fixable. But I would not rely on the theorem as stated until the conditional-independence step is repaired. If you're working on noisy sorting, keep this on the radar; don't cite the upper bound as proven yet.","headline":"Important result, but the main upper-bound proof has a load-bearing conditional-independence gap in Lemma 5.7 that needs a fix before the optimality claim is fully supported.","tokens_in":49829,"tokens_out":3492,"would_cite":false,"duration_ms":42717,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P10","68W20","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Persistent comparison faults — where re-asking a pair always returns the same possibly wrong answer — do not slow down sorting: O(n log n) time, O(log n) per-element error, for p < 1/4.","keywords":["persistent random comparison faults","approximate sorting","dislocation","noisy binary search","comparison sorting lower bound","high-probability bounds","derandomization","randomized algorithms"],"falsifier":"Run BasketSort on n = 10^4 or more elements with p just below 1/4 and track a fixed pair (y,z) whose comparison helped build the sequence S_w and is then reused in a later round's basket scoring. Measure the reported order of that pair conditional on both elements landing in the same later-round scoring neighborhood B or B+: if the conditional frequency departs from the unconditional error probability p beyond sampling error, the independence assumption behind Lemma 5.7 fails and the per-round tail bounds need re-derivation; if it stays at p, the assumption survives. A cheaper proxy is to meas","tokens_in":48875,"feed_emoji":"🔀","tokens_out":24680,"duration_ms":197698,"temperature":0.7,"pith_summary":"This paper claims that approximately sorting under persistent random comparison faults is no harder, asymptotically, than sorting with perfect comparisons, at least when each comparison errs with probability p < 1/4. The RiffleSort algorithm runs in O(n log n) worst-case time and, with high probability, returns a sequence in which every element sits within O(log n) positions of its true rank, with total dislocation O(n). The paper also proves these guarantees cannot be improved: no algorithm can achieve maximum dislocation o(log n) with high probability, no algorithm can achieve expected total dislocation o(n), and any o(n log n)-time algorithm with O(log n) maximum dislocation would contradict the classical comparison-sorting lower bound. If correct, this settles the time, maximum-dislocation, and total-dislocation complexity of the problem simultaneously for the error range p < 1/4. Since persistent errors model settings where re-asking a question returns the same biased answer (crowdsourced votes, noisy sensors, repeated rank queries), the message is that this kind of noise costs nothing asymptotically.","feed_headline":"O(n log n) sorting survives permanent comparison errors","feed_subtitle":"A new algorithm caps every element's displacement at O(log n), matching no-error sorting speed.","key_machinery":"NoisySearch builds two noisy binary search trees over even- and odd-indexed blocks of the sequence; each tree vertex carries left/right pointers that slide outward per test, so a query element is never compared twice with the same list element, and a majority-vote test over k neighbors decides the walk's next step. The walk on the tree containing the element's true rank drifts toward it, the other times out or lands nearby, so the returned rank is within O(d) in O(log n) time. BasketSort partitions a sequence with dislocation at most w into baskets of size w, scores each element against its neighbors, reorders by scores, and repeats with a shrinking window w (rate ρ = 1/2 + (4pq+5(p-q))/(1-p","core_discovery":"RiffleSort sorts in O(n log n) time with O(log n) maximum and O(n) total dislocation, with high probability, for persistent random comparison faults with p < 1/4. It grows a sorted core in doubling batches: NoisySearch inserts each batch in O(log n) time per element without ever re-comparing the same pair, and BasketSort re-compacts it to logarithmic maximum dislocation. The matching lower bound uses an instance-swapping coupling: elements whose true ranks differ by h are inverted by every algorithm with probability at least (1/2)(p/(1-p))^{2h-1}, giving an Ω(log n) maximum-dislocation floor and an Ω(n) expected total-dislocation floor. So RiffleSort is simultaneously optimal in all three me","pith_inferences":["The instance-swapping coupling behind the lower bound is a general template: it shows the Ω(log n) and Ω(n) floors are intrinsic to persistent noise, not artifacts of RiffleSort's design, and the same coupling could quantify dislocation-versus-probability tradeoffs at finite n, which the paper only states asymptotically.","NoisySearch's never-reuse-a-comparison discipline (its pointers slide to fresh proxy elements) is what makes O(log n) search possible under persistence; the same trick is a candidate building block for other persistent-fault primitives the paper does not discuss, such as approximate selection, median finding, or priority queues.","The p < 1/4 barrier lives entirely in BasketSort's geometric shrinking-rate constraint. A repair routine that avoids geometric shrinking — for instance, adapting the window size to locally observed dislocation — is the most direct route toward the paper's stated open problem of handling every p < 1/2 in O(n log n) time.","The paper's implied constants are large (a crude bound on alpha is below 34000(1-p)/(1-2p)^2), so for practical n the asymptotic O(log n) dislocation is not obviously attained; a simulation of BasketSort at p near 1/4, comparing the empirical tail of Lemma 5.7's score-inversion event against exp(-w kappa(p,q,rho)), would show where the real threshold sits."],"forward_implications":["Persistent random comparison faults at rate p < 1/4 add no asymptotic cost: RiffleSort's O(n log n) worst-case time matches the classical comparison-based bound that holds even with error-free comparisons.","The dislocation bounds are on proven floors: no algorithm can force maximum dislocation below Ω(log n) with high probability, nor expected total dislocation below Ω(n), regardless of running time.","The failure probability of RiffleSort is at most O(log n / (n sqrt n)), so the guarantees hold with polynomially high probability in n.","The two subroutines are reusable primitives: NoisySearch answers approximate rank queries in O(log n) time for any constant p < 1/2, and BasketSort re-compacts any sequence of m elements with dislocation at most w in O(m w) time to O(log m) maximum and O(m) total dislocation.","When comparison errors have probability at least a constant q > 0 and the input order is independent of the errors, a derandomized version achieves the same bounds deterministically by harvesting random bits from the comparison noise."],"supporting_citations":[{"why":"Defines the maximum-likelihood-permutation benchmark and first proves O(log n) maximum and O(n) total dislocation in this persistent-fault model; these are the dislocation targets RiffleSort attains.","marker":"[10]"},{"why":"Supplies the noisy binary search tree machinery for non-persistent faults that NoisySearch adapts, and sets the O(n log n) sorting target.","marker":"[15]"},{"why":"The previous fastest algorithm for this model, with roughly n sqrt n time and O(log n) maximum dislocation; this is the baseline RiffleSort's running time supersedes.","marker":"[19]"},{"why":"The first poly-time algorithm achieving O(log n) maximum dislocation with high probability for p ≤ 1/20 in the persistent model.","marker":"[23]"},{"why":"Provides the gambler's-ruin absorption formula used to bound the probability that a random walk on a noisy tree reaches a bad leaf in Lemma 4.9.","marker":"[16]"},{"why":"Supplies the hypergeometric tail bound used in the urn experiment of Lemma 3.2 that controls dislocation after simultaneous batch insertion.","marker":"[30]"}],"fun_headline_variants":["Permanent comparison errors? Still sort in optimal O(n log n)","Optimal sorting speed despite persistent comparison faults","First O(n log n) sorter with log dislocation under persistent noise","Matching no-error speed: sorting with permanent errors solved"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"BasketSort's analysis treats each element-pair comparison as a fresh independent coin flip every time it is used inside a round, even though the sequence being re-sorted was built in earlier rounds from some of the same persistent pair outcomes; the paper does not prove that conditioning on the round's all-good-and-all-happy event leaves those reused outcomes unbiased, and if it biases them the per-round concentration bounds lose their foundation.","fun_headline_variants_meta":{"raw":{"variants":["Permanent comparison errors? Still sort in optimal O(n log n)","Optimal sorting speed despite persistent comparison faults","First O(n log n) sorter with log dislocation under persistent noise","Matching no-error speed: sorting with permanent errors solved"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000362,"raw_usage":{"total_tokens":1888,"prompt_tokens":942,"completion_tokens":946,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":686,"completion_tokens_details":{"reasoning_tokens":877}},"tokens_in":686,"tokens_out":946,"duration_ms":9755,"temperature":1.0,"reasoning_tokens":877,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T15:29:33.676986+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run BasketSort on n = 10^4 or more elements with p just below 1/4 and track a fixed pair (y,z) whose comparison helped build the sequence S_w and is then reused in a later round's basket scoring. Measure the reported order of that pair conditional on both elements landing in the same later-round scoring neighborhood B or B+: if the conditional frequency departs from the unconditional error probability p beyond sampling error, the independence assumption behind Lemma 5.7 fails and the per-round tail bounds need re-derivation; if it stays at p, the assumption survives. A cheaper proxy is to meas","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the maximum-likelihood-permutation benchmark and first proves O(log n) maximum and O(n) total dislocation in this persistent-fault model; these are the dislocation targets RiffleSort attains."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the noisy binary search tree machinery for non-persistent faults that NoisySearch adapts, and sets the O(n log n) sorting target."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The previous fastest algorithm for this model, with roughly n sqrt n time and O(log n) maximum dislocation; this is the baseline RiffleSort's running time supersedes."},{"cited_title":"Woodruff","cited_arxiv_id":null,"evidence_quote":"The first poly-time algorithm achieving O(log n) maximum dislocation with high probability for p ≤ 1/20 in the persistent model."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the gambler's-ruin absorption formula used to bound the probability that a random walk on a noisy tree reaches a bad leaf in Lemma 4.9."},{"cited_title":"Hypergeometric tail inequalities: ending the insanity","cited_arxiv_id":"1311.5939","evidence_quote":"Supplies the hypergeometric tail bound used in the urn experiment of Lemma 3.2 that controls dislocation after simultaneous batch insertion."}],"review_version":1}