arXiv preprint ·
Parity Tests under Ties: A One-Test Lifting Theorem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A 51-Addition Alternative-Basis Kernel for Rank-23 $3\times3$ Matrix Multiplication
An EPTAS for Offline Temporary Tasks Assignment on Few Machines
The Fully Depolarizing Noise Conjecture for Entangled Physical States: A Twenty-Year Perspective
Quantum interaction can superactivate cheating under parallel repetition
Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.