### DIMACS Theoretical Computer Science Seminar

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

See: http://paul.rutgers.edu/~yixinxu/theory-spring12.html