Pith. sign in

REVIEW 2 major objections 5 minor 34 references

An Optimal Sorting Algorithm for Persistent Random Comparison Faults

T0 review · 2 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2508.19785 v1 pith:RSP2RUXV submitted 2025-08-27 cs.DS

Barbara Geissmann , Stefano Leucci , Chih-Hung Liu , Paolo Penna This is my paper
classification cs.DS MSC 68P1068W2060C05
keywords persistentrandomcomparisonfaultsapproximatesortingdislocationnoisybinarysearchlowerboundhigh-probabilityboundsderandomizationrandomizedalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [5.2, Lemma 5.7] 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
  2. [1.1 / 3] 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.
minor comments (5)
  1. [Algorithm 2, line 7] The text 'Sort4' should be 'Sort'; the superscript '4' appears to be a formatting artifact.
  2. [5.2, proof of Lemma 5.7] In the displayed equation after Equation (1), 'score(𝑦)− score(𝑦)' should read 'score(𝑦)− score(𝑥)'.
  3. [4.4, Lemma 4.4] In the definition of a bad vertex, the second case should be 'i* > max I(u) + cd', not 'i* > max I(u) − cd'.
  4. [5.3, Lemma 5.15] 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 '≤'.
  5. [5.3, Lemma 5.18] In the proof of Lemma 5.18, 'τ_w(y) > τ_w(w)' should be 'τ_w(y) > τ_w(x)'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: RiffleSort's upper bounds are proven in Sections 3–5 and the lower bounds in Section 6 are self-contained; self-citations to [17,18,19] are contextual and not load-bearing.

full rationale

The derivation chain is genuinely constructive. RiffleSort (Section 3) is built from two subroutines whose guarantees are stated as Theorem 4.10 and Theorem 5.20, and each of those theorems is proven in the current paper from the persistent-error probability model using Chernoff/Hoeffding bounds and explicit stopping-time arguments. The lower bounds in Section 6 are proven with a self-contained swapping/coupling argument (Lemma 6.1) leading to Theorems 6.2 and 6.3. The Ω(n log n) time lower bound is justified by the classical comparison-sorting lower bound, not by the authors' prior work. The paper's references to [17,18,19] are explicitly historical/contextual: it says the manuscript is an extended version of [17,18] and that BasketSort supersedes WindowSort [17], but the analysis of BasketSort, NoisySearch, and the lower bounds does not import a load-bearing conclusion from those citations. The only potentially serious issue identified by a skeptic is Lemma 5.7's use of independence ('all the X_z are independent random variables') after conditioning on the good/happy event; if that conditioning biases the persistent comparison outcomes, it is a correctness gap in a concentration step, not circularity: the lemma does not define its conclusion into its assumptions, no parameter is fitted to force the bound, and the theorem does not reduce to an input. Accordingly, no circular step satisfying the quoted-evidence standard can be exhibited.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the persistent-errors model, standard tail bounds, and an implicit independence assumption in BasketSort that is not established. There are no empirical fitted parameters or novel physical entities; the algorithmic constants (rho, k, c, alpha, beta) are internal design parameters derived from p and q, not free degrees of freedom.

assumptions (4)
  • domain assumption Comparison errors for distinct pairs are independent and persistent; each pair has a fixed error probability in [q,p].
    Defined in Section 2; this is the error model under study.
  • standard math Standard Chernoff, Hoeffding, and hypergeometric tail bounds are applicable to the constructed random variables.
    Used throughout Sections 3-5 and Appendix A for concentration arguments.
  • domain assumption The input sequence to RiffleSort may be chosen as a function of the errors, but shuffling removes this dependence.
    Assumed in Section 2 and implemented in Algorithm 1 line 1.
  • ad hoc to paper In BasketSort, persistent comparison outcomes used in a round behave as independent Bernoulli variables conditional on the previous rounds' good/happy event.
    Implicit in Lemma 5.7 ('all the X_z are independent random variables'); it is load-bearing and not proven, because persistent outcomes may have been reused across rounds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Optimal Sorting Algorithm for Persistent Random Comparison Faults." pith.science (2026). https://pith.science/paper/RSP2RUXV

@misc{pith2026250819785,
  author       = {Pith},
  title        = {Pith review of: An Optimal Sorting Algorithm for Persistent Random Comparison Faults},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RSP2RUXV}},
  note         = {Machine review of arXiv:2508.19785}
}
abstract

We consider the problem of sorting $n$ elements subject to persistent random comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (small) probability $p$, and comparing the same pair of elements multiple times always yields the same result. Sorting perfectly in this model is impossible, and the objective is to minimize the dislocation of each element in the output sequence, i.e., the difference between its position in the sequence and its true rank. In this paper, we present the first $O(n\log n)$-time sorting algorithm that guarantees both $O(\log n)$ maximum dislocation and $O(n)$ total dislocation with high probability when $p<\frac{1}{4}$. This settles the time complexity sorting with persistent comparison errors in the given range of $p$ and shows that comparison errors do not increase its computational difficulty. Indeed, $\Omega(n\log n)$ time is necessary to archive a maximum dislocation of $O(\log n)$ even without comparison errors. Moreover, we prove that no algorithm can guarantee a maximum dislocation of $o(\log n)$ with high probability, nor a total dislocation of $o(n)$ in expectation. To develop our sorting algorithm, we solve two related sub-problems, which might be of independent interest. More precisely, we show that $O(\log n)$ time suffices to find a position in which to insert a new element $x$ in an almost-sorted sequence $S$ of $n$ elements having dislocation at most $d=\Omega(\log n)$, so that the dislocation of $x$ in the resulting sequence is $O(d)$ with high probability (which can be equivalently thought as the problem of estimating the rank of $x$ in $S$). We also show that the maximum (resp. total) dislocation of an approximately sorted sequence $S$ of $n$ elements can be lowered to $O(\log n)$ (resp. $O(n)$) in $O(nd)$ time, w.h.p., where $d$ is an upper bound on the maximum dislocation of $S$.

Figures

Figures reproduced from arXiv: 2508.19785 by the authors.

Figure 1
Figure 1. An example of the noisy tree 𝑇0. On the left side, the shared pointers 𝐿(·) and 𝑅(·) are shown. Notice how 𝐿(𝑟) (and, in general, all the 𝐿(·) pointers on the leftmost side of the tree) points to the special −∞ element. Good vertices are shown in black while bad vertices are white. Notice that, since 𝑖 ∗ ∈ 𝐼(𝑤), we have 𝑇 ∗ = 𝑇0 and hence all the depicted vertices are either good or bad. 4.2 Construction of Noisy Bi… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

34 extracted references · 32 canonical work pages

  1. [1]

    Raghavendra Addanki, Sainyam Galhotra, and Barna Saha. 2021. How to Design Robust Algorithms using Noisy Comparison Oracle. Proceedings of the VLDB Endowment 14, 10 (2021), 1703–1716

    work page 2021

  2. [2]

    Nir Ailon, Moses Charikar, and Alantha Newman. 2008. Aggregating inconsistent information: Ranking and clustering. J. ACM 55, 5 (2008), 1–27

    work page 2008

  3. [3]

    Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, and Jelani Nelson. 2016. Sorting and selection with imprecise comparisons. ACM Transactions on Algorithms 12, 2 (2016), 19

    work page 2016

  4. [4]

    Noga Alon. 2006. Ranking Tournaments. SIAM Journal on Discrete Mathematics 20, 1 (2006), 137–142

    work page 2006

  5. [5]

    Noga Alon, Daniel Lokshtanov, and Saket Saurabh. 2009. Fast FAST. InProceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP09) . 49–58

    work page 2009

  6. [6]

    Michael Ben-Or and Avinatan Hassidim. 2008. The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well). In Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS08) . 221–230

    work page 2008

  7. [7]

    Lorenzo Beretta, Franco Maria Nardini, Roberto Trani, and Rossano Venturini. 2023. An Optimal Algorithm for Finding Champions in Tournament Graphs. IEEE Transactions on Knowledge and Data Engineering 35, 10 (2023), 10197–10209

    work page 2023

  8. [8]

    Enrico Bianchi and Paolo Penna. 2021. Optimal clustering in stable instances using combinations of exact and noisy ordinal queries. Algorithms 14, 2 (2021), 55

    work page 2021

Show all 34 references
  1. [9]

    Matthew Weinberg

    Mark Braverman, Jieming Mao, and S. Matthew Weinberg. 2016. Parallel algorithms for select and partition with noisy comparisons. In Proceedings of the Forty-eighth48th Symposium on Theory of Computing (STOC16) . 851–862

    2016

  2. [10]

    Mark Braverman and Elchanan Mossel. 2008. Noisy sorting without resampling. , 268-276 pages

    2008

  3. [11]

    Daniel G Brown. 2011. How I wasted too long finding a concentration inequality for sums of geometric variables. (2011). https://cs.uwaterloo.ca/~browndg/negbin.pdf

    2011

  4. [12]

    Pierre Charbit, Stéphan Thomassé, and Anders Yeo. 2007. The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments. Combinatorics, Probability and Computing 16, 1 (2007), 1–4

    2007

  5. [13]

    Ferdinando Cicalese. 2013. Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information . Springer. 36

    2013

  6. [14]

    Peter Damaschke. 2016. The Solution Space of Sorting with Recurring Comparison Faults. In Proceedings of the 27th International Workshop on Combinatorial Algorithms (IWOCA16) . 397–408

    2016

  7. [15]

    Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. 1994. Computing with Noisy Information. SIAM J. Comput. 23, 5 (1994), 1001–1018

    1994

  8. [16]

    William Feller. 1957. An introduction to probability theory and its applications (2 ed.). John Wiley & Sons

    1957

  9. [17]

    Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. 2017. Sorting with Recurrent Comparison Errors. In Proceedings of the Twenty-Eighth International Symposium on Algorithms and Computation (ISAAC17) . 38:1–38:12

    2017

  10. [18]

    Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. 2019. Optimal Sorting with Persistent Comparison Errors. In Proceedings of the Twenty-seventh European Symposium on Algorithms (ESA19) . 49:1–49:14

    2019

  11. [19]

    Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. 2020. Optimal Dislocation with Persistent Errors in Subquadratic Time. Theory Comput. Syst. 64, 3 (2020), 508–521

    2020

  12. [20]

    Yuzhou Gu and Yinzhan Xu. 2023. Optimal Bounds for Noisy Sorting. In Proceedings of the 55th Symposium on Theory of Computing (STOC23). 1502–1515

    2023

  13. [21]

    Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. 2020. Noise-tolerant, reliable active classification with comparison queries. In Proceedings of 33-rd Conference on Learning Theory (COLT20) . PMLR, 1957–2006

    2020

  14. [22]

    Claire Kenyon-Mathieu and Warren Schudy. 2007. How to rank with few errors. In Proceedings of the Thirty-nineth Symposium on Theory of Computing (STOC07) . 95–103

    2007

  15. [23]

    Woodruff

    Rolf Klein, Rainer Penninger, Christian Sohler, and David P. Woodruff. 2011. Tolerant algorithms. In Proceedings of the Nineteenth European Symposium on Algorithms (ESA11) . 736–747

    2011

  16. [24]

    Donald Ervin Knuth. 1998. The art of computer programming, Volume II: Seminumerical Algorithms, 3rd Edition . Addison-Wesley. 12–15 pages. https://www.worldcat.org/oclc/312898417

    1998

  17. [25]

    Spielman, Alexander S

    Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein, and Xifan Yu. 2025. Statistical Inference of a Ranked Community in a Directed Graph. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025 , Michal Koucký and...

    2025

  18. [26]

    Spielman, and Xifan Yu

    Dmitriy Kunisky, Daniel A. Spielman, and Xifan Yu. 2024. Inference of rankings planted in random tournaments.CoRR abs/2407.16597 (2024). https://doi.org/10.48550/ARXIV.2407.16597 arXiv:2407.16597

    2024 doi arXiv

  19. [27]

    Andrzej Pelc. 2002. Searching games with errors - fifty years of coping with liars. Theoretical Computer Science 270, 1-2 (2002), 71–109

    2002

  20. [28]

    Alfréd Rényi. 1961. On a problem of information theory. MTA Mat. Kut. Int. Kozl. B 6 (1961), 505–516

    1961

  21. [29]

    Rivest, Albert R

    Ronald L. Rivest, Albert R. Meyer, Daniel J. Kleitman, Karl Winklmann, and Joel Spencer. 1980. Coping with Errors in Binary Search Procedures. J. Comput. System Sci. 20, 3 (1980), 396–404

    1980

  22. [30]

    Matthew Skala. 2013. Hypergeometric tail inequalities: ending the insanity. CoRR abs/1311.5939 (2013). arXiv:1311.5939 [math.PR] https://arxiv.org/abs/1311.5939

    2013 arXiv

  23. [31]

    Stanislav M. Ulam. 1976. Adventures of a Mathematician. 37 Algorithm 3: RandomSubset(𝐴,ℎ) 1 if𝐴 =∅ then return∅; 2 𝑥← An element chosen u.a.r. from𝐴; 3 𝐵← a set obtained by selecting each element of𝐴\{𝑥} independently with probability 1/2; 4 if|𝐵|≤ ℎ− 1 then 5 return𝐵∪{𝑥}∪ Ran...

    1976

  24. [32]

    Otherwise, when𝐵 contains at leastℎ elements, the algorithm returns a subset of sizeℎ that is recursively sampled from𝐵 (notice that it might be |𝐵| =ℎ)

    Then, if|𝐵| is smaller thanℎ, the algorithm returns a set containing𝑥, all the elements in𝐵, and all the elements in a subset of sizeℎ−|𝐵|− 1 that is recursively sampled from𝐴\(𝐵∪{𝑥}). Otherwise, when𝐵 contains at leastℎ elements, the algorithm returns a subset of sizeℎ that i...

  25. [33]

    Hence, with probability at least 1− 22 √ 𝑁 log𝑁 , there are at most log𝑁 such groups and the size of𝐴′ in the first call of the𝑖-th such group is at most( 1 2)𝑖−1( √ 𝑁+ 1)

    Then, with a probability of at least 1−22 √ 𝑁 , we have that within a group of⌈2 √ 𝑁⌉ small calls, either the recursion reaches the final call, or the size of the input sets becomes at most|𝐴′|/2. Hence, with probability at least 1− 22 √ 𝑁 log𝑁 , there are at most log𝑁 such gr...

  26. [34]

    We can use a tail bound for negative binomial random variables (see, e.g., [11]) to obtain Pr Í𝑁 𝑖 𝑡𝑖 > 2𝑐𝜂 ≤ exp(−𝑐 2𝜂(1− 1 𝑐)2) for any𝑐 > 1. Since, for sufficiently large values of 𝑁 , there are at most𝜂 = 4⌈ √ 𝑁⌉ log𝑁 recursive calls of RandomSubset(𝐴,ℎ) withℎ > 0, each of...

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.