Parity Tests with Ties
This is an incremental extension of an existing algorithm to a more general setting (inputs with ties), relevant to researchers in randomized algorithms and computational geometry.
The paper extends the Ting-Yao randomized maximum-finding algorithm to handle inputs with ties, using parity tests simulated by O(log |B|) ordinary polynomial tests, increasing depth from O((log n)^2) to O((log n)^3) while maintaining O(n^{-c}) failure probability.
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$.