Mark Bun

Available identifiers

List of research outcomes

Publication	Date of Publication	Type
Approximate degree lower bounds for oracle identification problems	2024-11-20	Paper
Differentially private confidence intervals for proportions under stratified random sampling	2024-05-29	Paper
Stability is stable: connections between replicability, privacy, and adaptive generalization	2024-05-08	Paper
Private and Online Learnability Are Equivalent	2023-04-27	Paper
The large-error approximate degree of \(\mathrm{AC}^0\)	2023-02-03	Paper
Approximate Degree in Classical and Quantum Computing	2023-01-11	Paper
Sign-rank can increase under intersection	2022-07-21	Paper
Sign-rank can increase under intersection	2022-03-29	Paper
The large-error approximate degree of \(\mathrm{AC}^0\)	2021-10-25	Paper
Approximate degree and the complexity of depth three circuits	2021-08-04	Paper
Private Hypothesis Selection	2021-07-22	Paper
The polynomial method strikes back: tight quantum query bounds via dual polynomials	2020-12-17	Paper
A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)	2020-08-25	Paper
Simultaneous private learning of multiple concepts	2020-02-07	Paper
Heavy Hitters and the Structure of Local Privacy	2019-12-02	Paper
Quantum algorithms and approximating polynomials for composed functions with shared inputs	2019-10-15	Paper
Towards Instance-Optimal Private Query Release	2019-10-15	Paper
The polynomial method strikes back: tight quantum query bounds via dual polynomials	2019-08-22	Paper
Composable and versatile privacy via truncated CDP	2019-08-22	Paper
Fingerprinting codes and the price of approximate differential privacy	2018-11-07	Paper
Make Up Your Mind: The Price of Online Queries in Differential Privacy	2018-07-16	Paper
Improved bounds on the sign-rank of \(\mathrm{AC}^0\)	2017-12-19	Paper
Weighted polynomial approximations: limits for learning and pseudorandomness	2017-08-31	Paper
Concentrated differential privacy: simplifications, extensions, and lower bounds	2016-12-21	Paper
Separating computational and statistical differential privacy in the client-server model	2016-12-21	Paper
Dual polynomials for collision and element distinctness	2016-11-01	Paper
Simultaneous private learning of multiple concepts	2016-04-15	Paper
Order-revealing encryption and the hardness of private learning	2016-03-23	Paper
Hardness amplification and the approximate degree of constant-depth circuits	2015-10-27	Paper
Fingerprinting codes and the price of approximate differential privacy	2015-06-26	Paper
Dual lower bounds for approximate degree and Markov-Bernstein inequalities	2015-06-09	Paper
Dual lower bounds for approximate degree and Markov-Bernstein inequalities	2013-08-06	Paper

Research outcomes over time

This page was built for person: Mark Bun