Abstract
dc:description.abstractInsights derived from individuals' data have become indispensable across numerous domains, raising concerns about the leakage of private information contained in said data. Differential privacy (Dwork, McSherry, Nissim, Smith `06) has emerged as a widely studied and deployed framework for analyses that publish summary statistics, as it offers rigorous privacy guarantees while aiming to maintain data utility. In this thesis, we design differentially private algorithms, accompanied with theoretical utility guarantees, for three foundational data tasks: (1) counting connected components in a network, (2) counting distinct items in turnstile streams, and (3) testing conditional independence. These tasks are fundamental building blocks for more complex data analyses, but previously, have been studied either in restricted settings, or not all, through the lens of privacy. Despite the widespread adoption of differential privacy, its application to complex data structures such as networks and streams and sophisticated statistical techniques such as hypothesis testing remains under-explored. Our work contributes to these settings, where new challenges to practical differential privacy arise. For network and stream datasets, these challenges are due to the strong interdependence amongst datapoints themselves and between the datapoints and the output. In hypothesis testing, the introduction of noise to achieve privacy significantly affects the validity of statistical tests, especially with small sample sizes. We show that, in the worst-case, strong lower bounds apply to the utility of differentially private algorithms for all of our tasks. We overcome such lower bounds by adopting the approach of instance-based guarantees, where the error of our algorithm is bounded based on a specific parameter of the input dataset. The privacy noise is adapted to the hardness of the dataset at hand, where easier instances correspond to lower values of said parameter. We provide novel technical contributions in all three stages of our algorithmic design: the careful identification of parameters that are expected to be low for natural inputs and enable bypassing the worst-case lower bounds; the design of families of low-sensitivity, efficiently computable candidate functions, based on the specified parameter, that approximate the desired statistics; and, developing methods to select the optimal function from these candidates. This strategy enhances the practicality of differential privacy across the three settings we examine.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Computer Science
- Grantor
- Boston University
- Year dc:date.issued
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Kalemaj, Iden
- Advisor dc:contributor.advisor
-
- Raskhodnikova, Sofya
- ORCID dc:identifier.orcid
Subjects
dc:subject × 5Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53110