65 citations · 230 across the 37 of their papers we have counts for
41 papers
Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
Mark Bun, Joao F. Doriguello, John Kallaugher +1
We study the one-way communication complexity of the -Boolean Hidden Partition problem. Here, Alice is given an -bit string and Bob is given disjoint blocks of its ind…
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…
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…