Title: Optimal Private Halfspace Counting via Discrepancy
Speaker: Aleksandar Nikolov, Rutgers University
Date: Wednesday, March 7, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In the range counting problem we are given a set $P$ of $n$ points in $d$-dimensional Euclidean space, an integer weight $x_p$ for each point $p$ in $P$, and a collection ${\cal R}$ of ranges, i.e. subsets of $P$. Given a query range, the task is to output the sum of weights of the points belonging to that range. Range counting is a fundamental problem in computational geometry. We study $(\epsilon, \delta)$-differentially private algorithms for range counting. Our main results are for range spaces given by halfspaces, i.e.~the halfspace counting problem. We present an $(\epsilon, \delta)$-differentially private algorithm for halfspace counting in $d$ dimensions which achieves $O(n^{1-1/d})$ average squared error. We also show a matching lower bound of $\Omega(n^{1-1/d})$ for any $(\eps, \delta)$-differentially private algorithm. Both bounds are obtained using discrepancy theory. Our lower bound approach also yields a lower bound of $\Omega((\log n)^{d-1})$ average squared error for $(\epsilon, \delta)$-differentially private orthogonal range counting, the first known lower bound for this problem. Our upper bound methods yield $(\epsilon, \delta)$-differentially private algorithms for range counting with polynomially bounded shatter function range spaces. Joint work with S. Muthukrishnan. To appear in STOC 2012