Nikolov-Ullman Pure-DP Query Release Conjecture
Prior state unknown→proved
information-theoretic; a polynomial-time implementation remains open
SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review
theoretical-computer-science / Differential privacy
Nikolov-Ullman Pure-DP Query Release Conjecture
Nikolov and Ullman asked, as Open Problem 1 on DifferentialPrivacy.org, whether $k$ statistical queries over a universe of size $T$ can be released under pure differential privacy at the square-root error rate that the known lower bounds suggest, rather than the cube-root rate of the classical small-database method. They can: for every $n$ and $\varepsilon > 0$ there is an $\varepsilon$-differentially private mechanism with expected error $O(\min\{1, \sqrt{\log(2T)\log(2k)/(\varepsilon n)}\})$.
20Significance / 100
1Frontier events
0Verification tasks
0Recorded attempts
Temporal state
Current frontier
No reconciled state yet.
Append-only history
Frontier timeline
Research memory
Claims and attempts
Scoped claims
Nikolov and Ullman asked, as Open Problem 1 on DifferentialPrivacy.org, whether $k$ statistical queries over a universe of size $T$ can be released under pure differential privacy at the square-root error rate that the known lower bounds suggest, rather than the cube-root rate of the classical small-database method. They can: for every $n$ and $\varepsilon > 0$ there is an $\varepsilon$-differentially private mechanism with expected error $O(\min\{1, \sqrt{\log(2T)\log(2k)/(\varepsilon n)}\})$.
information-theoretic; a polynomial-time implementation remains open
Recorded attempts
Evidence graph
Connected research record
No public relationships recorded yet.