Back to search

Boston University

New results on verifiable and differentially private data analysis

Abstract

dc:description.abstract

In 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 × 6

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53605

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Sivakumar, Satchit. New results on verifiable and differentially private data analysis. doctoral thesis, Boston University, 2026. https://hdl.handle.net/2144/53605