Parity Tests with Ties

Ron Kupfer

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…