本周日晚上 7:30 - 8:30，我们将在学堂 112 【线下】给大家带来计科 70 班吕欣学长的报告
吕欣：Privacy 101: Releasing the median of your data, privately
吕欣目前是 UC Berkeley 理论组的二年级博士生，导师是 Avishay Tal 和 Jelani Nelson。他的研究兴趣是理论计算机科学，近期正在研究的问题包括为伪随机性，计算复杂性和差分隐私。本次报告中，他将介绍差分隐私中的一个问题：给定 n 个 [1,M] 中的整数，如何在满足私密性的情况下报告其中一个既不是前 1/3 小，也不是前 1/3 大的整数。
【报告摘要】Say there is an array a[1…n] of integers from [1, M]. You are tasked to privately report an integer 1 <= y <= M such that y is sandwiched between n/3 smallest and largest elements of a[1…n]. Without privacy constraints, this problem is almost trivial. However, with privacy requirements (as per the Differential Privacy definition), it becomes much more challenging and interesting. In particular, it is impossible to release an approximate median when the inputs are arbitrary real numbers!
So, let us fix a finite range [1, M]. Still, in this case, it takes more than a decade for people to figure out the smallest number n = n(M) of data (up to lower-order factors), so that the problem is possible to solve. I will describe the upper and lower bounds for this basic task, and survey its connections to several other basic tasks in privacy-preserving data analysis.
欢迎全体同学参加~
Make IIIS Great Again!
