7 papers
Testing Distributions Against Bounded Distinguishers
Mark Bun, Rathin Desai, Renato Ferreira Pinto
Motivated by the challenge of testing distributions over high-dimensional or continuous domains, we study distribution testing with respect to bounded classes of distinguishers. A…
QMA Lower Bounds for Batch Verification via Approximate Degree
Mark Bun, Mandar Juvekar, Samuel King
We study batch verification in QMA query and communication complexity, where the goal is to understand how the resources needed to verify copies of a Boolean function depen…
Not All Learnable Distribution Classes are Privately Learnable
Mark Bun, Gautam Kamath, Argyris Mouzakis +1
We give an example of a class of distributions that is learnable up to constant error in total variation distance with a finite number of samples, but not learnable under $(\vareps…
Separating Oblivious and Adaptive Differential Privacy under Continual Observation
Mark Bun, Marco Gaboardi, Connor Wagaman
We resolve an open question of Jain, Raskhodnikova, Sivakumar, and Smith (ICML 2023) by exhibiting a problem separating differential privacy under continual observation in the obli…
Privately Learning Decision Lists and a Differentially Private Winnow
Mark Bun, William Fang
We give new differentially private algorithms for the classic problems of learning decision lists and large-margin halfspaces in the PAC and online models. In the PAC model, we giv…
Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release
Mark Bun, Marco Carmosino, Palak Jain +2
The technical literature about data privacy largely consists of two complementary approaches: formal definitions of conditions sufficient for privacy preservation and attacks that…