Talwar, Kunal

Privacy-Computation Trade-Offs in Private Repetition and Metaselection

2025 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

A Private Repetition algorithm takes as input a differentially private algorithm with constant success probability and boosts it to one that succeeds with high probability. These algorithms are closely related to private metaselection algorithms that …