Metraipolis › archive › dc_f3290ff0fe10

Parity Tests under Ties: A One-Test Lifting Theorem — arXiv:2609.32799

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.32799
License (as archived)
CC0-1.0
Archived
2026-10-08T00:18:57.098Z
SHA-256 of the archived text
54d55ca8eab146b016b3154873726963d20935fd99923a8588ef967b467ba978
Stable URL of this page
https://metraipolis.com/documento/dc_f3290ff0fe10

How to cite

Parity Tests under Ties: A One-Test Lifting Theorem — arXiv:2609.32799 — arXiv (en), https://arxiv.org/abs/2609.32799 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f3290ff0fe10 (Metraipolis archive dc_f3290ff0fe10, sha256 54d55ca8eab146b016b3154873726963d20935fd99923a8588ef967b467ba978)
BibTeX
@misc{dcf3290ff0fe10,
  title = {Parity Tests under Ties: A One-Test Lifting Theorem — arXiv:2609.32799},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.32799},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f3290ff0fe10; sha256 54d55ca8eab146b016b3154873726963d20935fd99923a8588ef967b467ba978},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.32799. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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/\delta)])$ with error $\delta$, and top-$k$ selection in depth $O(\log^2 n+k\log n)$ with inverse-polynomial error, both without any promise on ties.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.32799 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:56:21.760Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).