Parity Tests with Ties

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