Abstract: We give the first polynomial-time algorithm to estimate the mean of a d-dimensional probability distribution with bounded covariance from ~O(d) independent samples, subject to pure differential privacy. Prior algorithms for this problem either incur exponential running time, require Omega(d^{1.5}) samples, or satisfy only the weaker approximate differential privacy condition. Some interesting connections with robust statistics are uncovered along the way.No familiarity with most of the words in the title (differential privacy, sum of squares, etc.) is assumed. Based on joint work in STOC 2022 with Samuel B. Hopkins and Mahbod Majid. ArXiv preprint available at https://arxiv.org/abs/2111.12981.

Note the location is 114 Gates Hall. You may also attend via Zoom