Open Problem Session
summary
Nine eight-minute open problems present concrete conjectures, partial results and explicit gaps: a private VC equivalence conjecture linking private uniform convergence, proper learning and the Littlestone/VC variants; a prediction-interface model with a proven upper bound using stability giving sample complexity ~1/√ε but a lower bound of 1/ε leaving a 1/√n vs 1/ε gap; a possible separation in local DP for interactive online linear queries; lower bounds showing exponential dependence on dimension for local Lipschitz filters; and a log‑log gap for Gaussian noise composition versus lower bounds for answering K queries.
AI-written summary · about
chapters (10)
- 0:00Introduction to open problems
- 1:02Private uniform convergence
- 10:41Differential private prediction
- 19:20Pure vs approximate local DP
- 29:08Constructing local filters
- 37:43Query release and log gaps
- 44:50Privacy in functional estimation
- 53:18Selection problem complexities
- 1:02:18Adaptive query strategy limits
- 1:12:33All-pairs graph distances
related talks
01h 03mSimons Institute Live Stream
01h 11mAlgorithms for Answering Linear Queries, Part II
39mVirtual talk by Jonathan Ullman (Northeastern)
01h 00mDifferential Privacy And The Complexity Of Simple Queries
01h 02mLarge-Scale Private Learning, Part I
01h 02mFormal Methods and Proofs of Privacy Properties, Part III
58mLarge-Scale Private Learning, Part III
33mHeterogeneity and Privacy in Modern Learning