Imagine you're running a restaurant chain and you want to figure out what dishes are most popular across all locations. Each manager sends you a tally of what sold that week. The catch: you promised every manager that their specific report can never be reverse-engineered from the final menu analysis. That's person-level differential privacy — and the fundamental question is: how many managers do you need before you can accurately reconstruct the overall popularity distribution, while keeping every individual manager's contribution hidden? This paper answers that question with matching upper and lower bounds — and crucially, does so with algorithms that actually run in polynomial time. Previous work had established the information-theoretic minimum number of users needed, but the algorithms that achieved those bounds were computationally intractable. Others had polynomial-time algorithms but with suboptimal sample complexity. Kamath, Majid, Moitra, Mouzakis, and Ullman close this gap for both pure (ε,0)-DP and approximate (ε,δ)-DP, producing poly-time algorithms whose user requirements match the theoretical floor up to log factors. The core technical engine is a new degree-6 sum-of-squares (SoS) estimator for learning distributions from untrusted batches. The problem reduces to robust statistics: each user's batch of m samples can be thought of as a potentially corrupted report, and the privacy mechanism introduces further noise. The key innovation is constructing a 'trace-bounded diagonal majorizer' for the gap between the empirical covariance of repaired batch averages and the multinomial covariance predicted by their mean. This certificate is the load-bearing piece — it preserves the mean-dependent variance structure of multinomial data, which is what yields the tight robust rate of O(η√(log(1/η)/m)). The proof that clean data actually admit this certificate is where the heavy math lives. The authors use semidefinite-programming duality combined with a new application of the symmetric form of Grothendieck's inequality due to Friedland and Lim. This is not a routine application — Grothendieck's inequality is a classical tool in functional analysis that bounds bilinear forms, and deploying its stronger symmetric variant to certify covariance structure in a robust estimation context is genuinely novel. The privacy guarantee comes through a now-standard reduction: if you have a robust estimator with a computable 'score function,' you can convert it into a differentially private algorithm via propose-test-release or exponential mechanism style reductions. The SoS certificate provides exactly the score the reduction needs. The sample complexity under pure DP is n = Õ(k/(α²m) + k/(α√m·ε) + k/ε), and under approximate DP with δ = 2^{-Θ(k)}, the total collapses to Õ(k) for fixed accuracy, privacy, and batch size. The authors also prove a statistical query lower bound showing you cannot uniformly beat this error rate with polynomial SQ resources. This is a strong negative result — it says the algorithmic template they're using (and that most natural algorithms use) is essentially squeezed: you can't do better without fundamentally different computational primitives. The SQ lower bound is the 'you are here' sign for the field. This is a full version of a SODA 2027 paper, which means it survived one of the top venues in theoretical computer science. The result is clean, the contribution is well-defined, and the tools are interesting beyond this specific problem. The SoS estimator and the Grothendieck inequality application will likely see reuse in adjacent robust estimation and privacy problems.
