Calvin Lab Auditorium
In this talk, I will survey some fruitful connections between convex geometry and differential privacy for linear queries. The connection is established through a polytope that captures the sensitivity of a set of queries. I will describe several techniques on using the geometry of sensitivity polytope to bound (both upper and lower) the noise level needed to achieve DP. This leads to nearly optimal mechanisms for linear queries, under both pure and approximate privacy definition.