Parity Tests with Ties
Pith reviewed 2026-05-10 01:28 UTC · model grok-4.3
The pith
The Ting-Yao maximum-finding algorithm extends to inputs with possible ties by replacing each parity test with O(log |B|) ordinary polynomial tests.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We extend the Ting--Yao randomized maximum-finding algorithm to inputs that need not be pairwise distinct: each parity test P(i,B)=∏_{a∈B}(x_i-x_a):0 on B⊆[n]∖{i} is simulated by O(log |B|) ordinary polynomial tests, raising depth from O((log n)^2) to O((log n)^3) while preserving the O(n^{-c}) failure probability for every fixed c>0.
What carries the argument
Simulation of each parity test P(i,B) by O(log |B|) ordinary polynomial tests, which replaces the specialized test while controlling error.
If this is right
- The algorithm correctly identifies a maximum even when duplicate values appear in the input.
- The depth grows from O((log n)^2) to O((log n)^3).
- The failure probability stays O(n^{-c}) for every fixed constant c>0.
- Only ordinary polynomial tests are required after the simulation step.
Where Pith is reading between the lines
- The same simulation technique may allow parity-test-based procedures for other selection tasks to be adapted to inputs with duplicates.
- In parallel or distributed models where depth determines latency, the extra logarithmic factor remains the dominant cost introduced by ties.
Load-bearing premise
Replacing each parity test with O(log |B|) ordinary polynomial tests preserves the original failure-probability bound without introducing new error sources or extra assumptions on the input values.
What would settle it
An explicit input family containing many ties on which the simulated algorithm returns an incorrect maximum with probability exceeding O(n^{-c}) for some fixed c>0.
read the original abstract
We extend the Ting--Yao randomized maximum-finding algorithm [TY94] to inputs that need not be pairwise distinct: each parity test $P(i,B)=\prod_{a\in B}(x_i-x_a):0$ on $B\subseteq[n]\setminus\{i\}$ is simulated by $O(\log |B|)$ ordinary polynomial tests, raising depth from $O((\log n)^2)$ to $O((\log n)^3)$ while preserving the $O(n^{-c})$ failure probability for every fixed $c>0$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper extends the Ting-Yao randomized maximum-finding algorithm [TY94] to inputs that need not be pairwise distinct. Each parity test P(i,B)=∏_{a∈B}(x_i - x_a):0 on B⊆[n]∖{i} is simulated by O(log |B|) ordinary polynomial tests. This raises the depth from O((log n)^2) to O((log n)^3) while preserving the O(n^{-c}) failure probability for every fixed c>0.
Significance. If the simulation step is shown to preserve the original high-probability bounds without new error accumulation, the result provides a natural extension of [TY94] to multisets. The approach maintains the core randomized polynomial-test model and yields a concrete depth bound, which could be useful for comparison-based or algebraic decision-tree analyses of selection problems.
major comments (1)
- The central claim that the O(log |B|) simulation of each parity test preserves the overall O(n^{-c}) failure probability (for arbitrary fixed c) is load-bearing but lacks an explicit error-propagation argument in the provided abstract and high-level description. The original TY94 analysis relies on the exact semantics and error rates of parity tests; any probabilistic simulation (e.g., via random linear combinations or zero-testing) must bound the per-simulation discrepancy probability below n^{-c-O(1)} to absorb the O((log n)^3) total tests along any execution path. Without this calculation, the preservation statement remains unverified.
Simulated Author's Rebuttal
We thank the referee for the careful review and for noting the potential value of the extension for algebraic decision-tree analyses of selection. We address the sole major comment below.
read point-by-point responses
-
Referee: The central claim that the O(log |B|) simulation of each parity test preserves the overall O(n^{-c}) failure probability (for arbitrary fixed c) is load-bearing but lacks an explicit error-propagation argument in the provided abstract and high-level description. The original TY94 analysis relies on the exact semantics and error rates of parity tests; any probabilistic simulation (e.g., via random linear combinations or zero-testing) must bound the per-simulation discrepancy probability below n^{-c-O(1)} to absorb the O((log n)^3) total tests along any execution path. Without this calculation, the preservation statement remains unverified.
Authors: We agree that an explicit error-propagation argument is needed to make the preservation claim fully rigorous. The simulation replaces each parity test with O(log |B|) ordinary polynomial tests (via random linear combinations to test for a zero factor in the product). Each such simulation can be made to fail with probability at most n^{-c-3} by a constant-factor increase in repetitions inside the O(log |B|) budget. Because any execution path in the algorithm performs at most O((log n)^3) primitive tests, a union bound yields total simulation error O(n^{-c}). The original TY94 parameters can be adjusted by increasing the constant hidden in the O-notation to absorb this. We will add a short dedicated paragraph (or subsection) immediately after the simulation description that carries out this calculation in full detail. revision: yes
Circularity Check
No circularity: extension relies on external base algorithm with explicit simulation step
full rationale
The derivation starts from the external Ting-Yao algorithm [TY94] as a black-box and adds a simulation of each parity test P(i,B) by O(log |B|) ordinary polynomial tests. This raises depth to O((log n)^3) while claiming preservation of the O(n^{-c}) failure probability. No step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the base result is independent and the simulation is presented as an additive construction. The paper is self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The Ting-Yao algorithm [TY94] achieves O((log n)^2) depth and O(n^{-c}) failure probability on distinct inputs.
Reference graph
Works this paper leans on
-
[1]
Ting, Hing F. and Yao, Andrew C. , title =. Information Processing Letters , volume =. 1994 , doi =
work page 1994
- [2]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.