Mark Bun | DeepAI

DeepAI AI Chat

Featured Co-authors

Zhiwei Steven Wu
90 publications
Shay Moran
56 publications
Kunal Talwar
44 publications
Gautam Kamath
43 publications
Vitaly Feldman
41 publications
Uri Stemmer
37 publications
Janardhan Kulkarni
35 publications
Marco Gaboardi
32 publications
Thomas Steinke
27 publications
Toniann Pitassi
25 publications
Jelani Nelson
22 publications

∙ 09/08/2023

The Complexity of Verifying Boolean Programs as Differentially Private

We study the complexity of the problem of verifying differential privacy...

0 Mark Bun, et al. ∙

∙ 06/13/2023

Continual Release of Differentially Private Synthetic Data

Motivated by privacy concerns in long-term longitudinal studies in medic...

0 Mark Bun, et al. ∙

∙ 03/22/2023

Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization

The notion of replicable algorithms was introduced in Impagliazzo et al....

0 Mark Bun, et al. ∙

∙ 03/07/2023

Approximate degree lower bounds for oracle identification problems

The approximate degree of a Boolean function is the minimum degree of re...

0 Mark Bun, et al. ∙

∙ 06/09/2022

Strong Memory Lower Bounds for Learning Natural Models

We give lower bounds on the amount of memory required by one-pass stream...

5 Gavin Brown, et al. ∙

∙ 07/22/2021

Multiclass versus Binary Differentially Private PAC Learning

We show a generic reduction from multiclass differentially private PAC l...

0 Mark Bun, et al. ∙

∙ 02/17/2021

Differentially Private Correlation Clustering

Correlation clustering is a widely used technique in unsupervised machin...

0 Mark Bun, et al. ∙

∙ 12/11/2020

When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?

Modern machine learning models are complex and frequently encode surpris...

18 Gavin Brown, et al. ∙

∙ 07/24/2020

Controlling Privacy Loss in Survey Sampling (Working Paper)

Social science and economics research is often based on data collected i...

0 Mark Bun, et al. ∙

∙ 07/11/2020

A Computational Separation between Private Learning and Online Learning

A recent line of work has shown a qualitative equivalence between differ...

0 Mark Bun, et al. ∙

∙ 07/10/2020

New Oracle-Efficient Algorithms for Private Synthetic Data Release

We present three new algorithms for constructing differentially private ...

0 Giuseppe Vietri, et al. ∙

∙ 03/01/2020

An Equivalence Between Private Classification and Online Prediction

We prove that every concept class with finite Littlestone dimension can ...

0 Mark Bun, et al. ∙

∙ 02/04/2020

Efficient, Noise-Tolerant, and Private Learning via Boosting

We introduce a simple framework for designing private boosting algorithm...

0 Mark Bun, et al. ∙

∙ 06/06/2019

Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation

The simplest and most widely applied method for guaranteeing differentia...

0 Mark Bun, et al. ∙

∙ 05/30/2019

Private Hypothesis Selection

We provide a differentially private algorithm for hypothesis selection. ...

0 Mark Bun, et al. ∙

∙ 03/01/2019

Sign-Rank Can Increase Under Intersection

The communication class UPP^cc is a communication analog of the Turing M...

0 Mark Bun, et al. ∙

∙ 11/09/2018

Towards Instance-Optimal Private Query Release

We study efficient mechanisms for the query release problem in different...

0 Jarosław Błasiok, et al. ∙

∙ 09/06/2018

Quantum algorithms and approximating polynomials for composed functions with shared inputs

We give new quantum algorithms for evaluating composed functions whose i...

0 Mark Bun, et al. ∙

∙ 11/13/2017

Heavy Hitters and the Structure of Local Privacy

We present a new locally differentially private algorithm for the heavy ...

0 Mark Bun, et al. ∙

∙ 10/25/2017

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

The approximate degree of a Boolean function f is the least degree of a ...

0 Mark Bun, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world