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.
Note (2026-11-08): the abstract (Chen, Ding, Majid and McKelvie) says the efficient algorithms reach mean-squared error (1+o(1)) times the optimum, that for Bayesian mean estimation the excess risk is optimal among efficient algorithms 'within the low-degree framework' yet provably worse than an exponential-time algorithm, and that for linear regression there is a 'qualitatively similar lower bound'. The essay states the gap as an unconditional theorem about what polynomial-time computation cannot achieve; the abstract frames it within the low-degree framework. The three-way 'any two are easy' framing is the essay's own.
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.