Near-Optimal Generalized Private Testing
Anamay Chaturvedi 1, Monika Henzinger 1, Jalaj Upadhyay 2 · 2026
Read Near-Optimal Generalized Private Testing by Anamay Chaturvedi 1, Monika Henzinger 1, Jalaj Upadhyay 2 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21601.txt.
Introduction
Anamay Chaturvedi and co-authors study near-optimal private testing. The analyst must take the first mechanism whose chance exceeds a threshold, while keeping privacy. This generalizes the private testing problem solved by the Sparse Vector Technique. They present the Generalized Thresholding Mechanism, pure epsilon-private for any sequence of methods, with lower bounds proving near-best accuracy and sample needs. It reduces private tuning from ongoing watch to batch settings, yielding the first private streaming methods for gains problems.
Catalog record
| CREATOR | Anamay Chaturvedi 1, Monika Henzinger 1, Jalaj Upadhyay 2 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 251471 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.21601