Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2604.19158 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908990737219584 |
|---|---|
| author | Kupfer, Ron |
| author_facet | Kupfer, Ron |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_19158 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Parity Tests with Ties Kupfer, Ron Computational Complexity 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$. |
| title | Parity Tests with Ties |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2604.19158 |