{"ID":2894133,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.12634","arxiv_id":"2507.12634","title":"Fast Order Statistics with Group Inequality Testing","abstract":"Suppose that a group test operation is available for checking order relations in a set, can this speed up problems like finding the minimum/maximum element, determining the rank of element, and computing order statistics? We consider a one-sided group inequality test to be available, where queries are of the form $u \\le_Q V$ or $V \\le_Q u$, and the answer is `yes' if and only if there is some $v \\in V$ such that $u \\le v$ or $v \\le u$, respectively. We restrict attention to total orders and focus on query-complexity; for min or max finding, we give a Las Vegas algorithm that makes $\\mathcal{O}(\\log^2 n)$ expected queries. We observe that rank determination can be solved with existing ``defect-counting'' algorithms, but also give a simple Monte Carlo approximation algorithm with expected query complexity $\\tilde{\\mathcal{O}}(\\frac{1}{δ^2} \\log \\frac{1}ε)$, where $1-ε$ is the probability that the algorithm succeeds and we allow a relative error of $1 \\pm δ$ for $δ\u003e 0$ in the estimated rank. We then give a Monte Carlo algorithm for approximate selection that has expected query complexity $\\tilde{\\mathcal{O}}(\\frac{1}{δ^4}\\log \\frac{1}{εδ^2} )$; it has probability at least $\\frac{1}{2}$ to output an element $x$, and if so, $x$ has the desired approximate rank with probability $1-ε$. Keywords: Order statistics, Group inequality testing, Randomized algorithms","short_abstract":"Suppose that a group test operation is available for checking order relations in a set, can this speed up problems like finding the minimum/maximum element, determining the rank of element, and computing order statistics? We consider a one-sided group inequality test to be available, where queries are of the form $u \\l...","url_abs":"https://arxiv.org/abs/2507.12634","url_pdf":"https://arxiv.org/pdf/2507.12634v2","authors":"[\"Adiesha Liyanage\",\"Brendan Mumey\",\"Braeden Sopp\"]","published":"2025-07-16T21:16:39Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}