4 papers
Private Prediction via Shrinkage
Chao Yan
We study differentially private prediction introduced by Dwork and Feldman (COLT 2018): an algorithm receives one labeled sample set and then answers a stream of unlabeled quer…
An ptimal Differentially Private Learner for Concept Classes with VC Dimension 1
Chao Yan
We present the first nearly optimal differentially private PAC learner for any concept class with VC dimension 1 and Littlestone dimension . Our algorithm achieves the sample co…
Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems
Kobbi Nissim, Eliad Tsfadia, Chao Yan
We study the sample complexity of differentially private optimization of quasi-concave functions. For a fixed input domain , Cohen et al. (STOC 2023) proved that any g…
Computationally Differentially Private Inner Product Protocols Imply Oblivious Transfer
Iftach Haitner, Noam Mazor, Jad Silbak +2
In distributed differential privacy, multiple parties collaborate to analyze their combined data while each party protects the confidentiality of its data from the others. Interest…