Abstract
dc:description.abstractIn this thesis, we study two pillars of responsible data analysis: verifiability and privacy. Motivated by preventing the dissemination of wrong conclusions, verifiability ensures that the validity of a data analysis can be independently checked by third parties. Privacy preservation ensures that sensitive information about individuals is not revealed through the outputs of an analysis. The goal of this thesis is to improve our understanding of the statistical and computational resources required for verifiable data analysis, and to clarify the privacy–accuracy tradeoffs that arise when statistics must be continually released as data evolve. In the first part of the thesis, we start by studying replicability, an algorithmic stability notion introduced in recent work (Impagliazzo et al. 2022), which requires that the output of an analysis remain unchanged when the analysis is run on fresh data. We put forth a new treatment of replicability, not as an isolated quantity, but rather as part of a rich web of algorithmic stability notions including more widely studied notions like differential privacy (Dwork et al. 2016). We establish sample-optimal algorithmic transformations between these different stability notions. These connections give statistically optimal replicable algorithms for numerous problems for which no replicable algorithms were previously known. We also show that this unified approach to algorithmic stability is useful beyond replicability, using it to solve open problems in differential privacy, for example, proving new parameter amplification theorems for differential privacy. Next, motivated by the potentially large data requirements of verification by rerunning, we ask whether interaction with the data analyst can make verification more resource-efficient. For a broad class of distribution-testing problems, we construct interactive protocols in which a verifier uses only a small number of samples from the distribution and pairwise conditional-sampling queries, even though solving the same testing problem from scratch requires exponentially more samples and queries. To the best of our knowledge, this gives the first exponential separation between the sample complexity of interactive verification and verification by rerunning for such a broad and widely studied class of statistical tasks. The second part of the thesis studies differential privacy under continual observation, where an algorithm repeatedly releases outputs as a data stream evolves. We prove the first strong polynomial-in-T lower bounds on the error of differentially private algorithms for the continual release of three fundamental problems over streams of length T, thereby giving a polynomial in T separation between the error achievable in the single release and continual release model. The best separation between these models for any problem prior to this work was polylogarithmic in T. Our results expose a fundamental difference between single and continual release: low sensitivity of a function, which enables accurate release in the single release model of differential privacy, does not by itself guarantee accuracy in the continual release model. Motivated by these worst-case barriers, we develop a unified beyond-worst-case framework, giving algorithms whose accuracy is governed by task-specific parameters of the stream, instead of the stream length T. These parameters are often substantially smaller than T for realistic streams. We instantiate this framework appropriately to give state-of-the-art accuracy bounds for distinct-element counting, degree-histogram estimation, and triangle counting on dynamic streams. Thus, although error that is polynomial in the stream length T can be unavoidable in the worst case, substantially better accuracy can be obtained for many realistic streams.
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
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Sivakumar, Satchit
- Advisor dc:contributor.advisor
-
- Bun, Mark
Subjects
dc:subject × 6Rights
dc:rights- Statement dc:rights
-
- Attribution 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53605