We study the problem of computing a point in the convex hull, and the related problem of computing a separating hyperplane, under the constraint of differential privacy. Intuitively, differential privacy means that our output should be robust to small changes in the input (for example to adding or deleting a point). We study the minimum size of the input needed to achieve such a private computation (sample complexity) and its time complexity.
Even in one dimension the problem is non-trivial and we will first focus on this case. Several interesting open problems will be presented as well.
No previous background on differential privacy will be assumed.
Time & Location
Jan 27, 2020 | 02:15 PM
Freie Universität Berlin
Institut für Informatik
Room 005 (Ground Floor)