## Abstract

A range counting problem is specified by a set P of size |P| = n of points in ℝ ^{d}, an integer weight x _{p} associated to each point p ε P, and a range space R ⊆ 2 ^{P}. Given a query range R ε R, the output is R(x) = Σ _{pεR} x _{p}. The average squared error of an algorithm A is 1/|R|Σ _{RεR}((A(R, x) - R(x))) ^{2}. Range counting for different range spaces is a central problem in Computational Geometry. We study (ε, δ)-differentially private algorithms for range counting. Our main results are for the range space given by hyperplanes, that is, the halfspace counting problem. We present an (ε, δ)-differentially private algorithm for halfspace counting in d dimensions which is O(n ^{1-1/d}) approximate for average squared error. This contrasts with the Ω(n) lower bound established by the classical result of Dinur and Nissim on approximation for arbitrary subset counting queries. We also show a matching lower bound of Ω(n ^{1-1/d}) approximation for any (ε, δ)-differentially private algorithm for halfspace counting. Both bounds are obtained using discrepancy theory. For the lower bound, we use a modified discrepancy measure and bound approximation of (ε, δ)-differentially private algorithms for range counting queries in terms of this discrepancy. We also relate the modified discrepancy measure to classical combinatorial discrepancy, which allows us to exploit known discrepancy lower bounds. This approach also yields a lower bound of Ω((log n) ^{d-1}) for (ε, δ)-differentially private orthogonal range counting in d dimensions, the first known superconstant lower bound for this problem. For the upper bound, we use an approach inspired by partial coloring methods for proving discrepancy upper bounds, and obtain (ε, δ)-differentially private algorithms for range counting with polynomially bounded shatter function range spaces.

Original language | English (US) |
---|---|

Title of host publication | STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing |

Pages | 1285-1292 |

Number of pages | 8 |

DOIs | |

State | Published - 2012 |

Event | 44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States Duration: May 19 2012 → May 22 2012 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 44th Annual ACM Symposium on Theory of Computing, STOC '12 |
---|---|

Country/Territory | United States |

City | New York, NY |

Period | 5/19/12 → 5/22/12 |

## Keywords

- combinatorial discrepancy
- differential privacy
- range counting

## ASJC Scopus subject areas

- Software