Parity Tests with Ties

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 \mathrm{\mid }B\mathrm{\mid })$ 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$.