Lifting theorems enable input ties in parity-tested algorithms
Parity Tests under Ties: A One-Test Lifting Theorem
Data Structures and AlgorithmsComputational Complexity
Summary
Finding the largest or top few items usually depends on comparing their values, often assuming all inputs are different. When some inputs tie, existing methods struggle because the math becomes undefined or complicated. The authors show a new way to handle ties that only slightly increases the number of basic tests needed. This technique ensures algorithms for finding maximums or top-k selections work reliably even when multiple values are equal.
What this means in practice
- •For algorithm engineers: Design reliable maximum and top-k selection algorithms that handle tied inputs without increasing error rates or complexity significantly.
- •For data processing teams: Implement fast and robust order-selection computations in datasets where duplicate values occur frequently without sacrificing accuracy.
A theory result. No direct application yet.
Authors
Ron Kupfer
Abstract
In the unrestricted polynomial decision-tree model, only the number of polynomial sign tests is charged. A parity test asks for the sign of a product of pairwise differences. Such tests underlie low-depth randomized algorithms for maximum finding and top-$k$ selection, but their usual analysis assumes distinct inputs because a tie makes the product vanish. We give a black-box lifting theorem that removes this assumption. After $O(\log n)$ polynomial tests determine the number of nonzero pairwise differences, every subsequent parity test is simulated by one polynomial test, consistently with a fixed lexicographic tie-breaking order. The simulator is an elementary symmetric polynomial in masked first and second powers of all pairwise differences. Thus a depth-$D$ parity-test tree on distinct inputs becomes a polynomial decision tree of depth $D+O(\log n)$ on arbitrary inputs, with no increase in randomized pointwise error for order-selection problems. We obtain maximum finding in depth $O(\log n[\log n+\log(1/δ)])$ with error $δ$, and top-$k$ selection in depth $O(\log^2 n+k\log n)$ with inverse-polynomial error, both without any promise on ties.