10 papers
Differentially Private Verification of Distribution Properties
Elbert Du, Cynthia Dwork, Pranay Tankala +1
A recent line of work initiated by Chiesa and Gur and further developed by Herman and Rothblum investigates the sample and communication complexity of verifying properties of distr…
Supersimulators
Cynthia Dwork, Pranay Tankala
We prove that every randomized Boolean function admits a supersimulator: a randomized polynomial-size circuit whose output on random inputs cannot be efficiently distinguished from…
Efficient and Private Property Testing via Indistinguishability
Cynthia Dwork, Pranay Tankala
Given a small random sample of -bit strings labeled by an unknown Boolean function, which properties of this function can be tested computationally efficiently? We show an equiv…
The Importance of Being Smoothly Calibrated
Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar +1
Recent work has highlighted the centrality of smooth calibration [Kakade and Foster, 2008] as a robust measure of calibration error. We generalize, unify, and extend previous resul…
Efficient Calibration for Decision Making
Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar +1
A decision-theoretic characterization of perfect calibration is that an agent seeking to minimize a proper loss in expectation cannot improve their outcome by post-processing a per…
From Pseudorandomness to Multi-Group Fairness and Back
Cynthia Dwork, Daniel Lee, Huijia Lin +1
We identify and explore connections between the recent literature on multi-group fairness for prediction algorithms and the pseudorandomness notions of leakage-resilience and graph…