Bayesian estimation under differential privacy faces three competing demands: computational efficiency, statistical utility, and privacy protection. You can have any two easily. The question is what happens when you insist on all three simultaneously.
This paper reveals a computational-statistical gap in private Bayesian estimation. For Gaussian mean estimation and linear regression, they construct polynomial-time algorithms achieving near-Bayes-optimal error rates under privacy constraints. But these polynomial-time methods are provably suboptimal compared to exponential-time algorithms. There exist estimators with better statistical performance that no efficient algorithm can match — the gap is inherent, not a failure of technique.
The tools are sum-of-squares methods applied to non-robust estimators, extended with novel constraints based on short-flat decompositions. The result means that computation, utility, and privacy form a genuine three-way tradeoff: improving any one requires sacrificing another, and the sacrifice is quantifiable. The tradeoff isn't a frontier to be pushed — it's a theorem about what polynomial-time computation fundamentally cannot achieve under privacy constraints.