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

CREATORAnamay Chaturvedi 1, Monika Henzinger 1, Jalaj Upadhyay 2
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE251471
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.21601

Browse the full library · About the Tower of Babel