{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiall7wo7mioetuzcx2olin2exq2xhkwpxeirzrlfovmizq7maxvwm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mk2qk6t4a7d2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.19158v1",
  "publishedAt": "2026-04-22T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Ron Kupfer"
  ],
  "textContent": "**Authors:** Ron Kupfer\n\nWe 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"
}