From Ranking Quality to Query Complexity: Exact-AUC Minimax Recovery with Ordinal Predictions

We characterize the minimax adaptive-query complexity of every exact-AUC class in noiseless group testing with a known number of positives. For $s\ge 2$ positives among $d\ge 2s$ items, let $\Delta =s(d-s)\min \{AUC,1-AUC\}$. The complexity is $\Theta (\min \{\Delta ,s\}+s\log (1+\Delta /s^2))$ for $\Delta \ge 2$; the classes with $\Delta \in \{0,1\}$ are singletons and require no queries when AUC is known. The curve exhibits a regime in which candidate counting is insufficient: for $2\le \Delta \le s$, log-cardinality is $\Theta (\sqrt{\Delta })$, yet recovery requires $\Theta (\Delta )$ OR queries. We obtain matching lower bounds by constructing hard families at every prescribed rank sum. One explicit algorithm, given neither AUC nor a candidate class, attains all these class-wise rates up to universal constants and an additive constant. The characterization also identifies how ranking accuracy must scale with sparsity to permit $O(s)$ query budgets. Within the same exact-AUC class, however, supports recoverable by this algorithm in $O(s)$ queries can coexist with subfamilies requiring $\Omega (s\log s)$ queries in the worst case. Certified finite-class budgets and numerical constructions illustrate the query obstruction and the within-class separation.