Differentially Private Algorithms for Packing and Covering Semidefinite Programs

We provide differentially private algorithms for solving packing and covering semidefinite programs (SDPs) under the privacy model where neighboring inputs differ by a single constraint. We give efficient polynomial-time algorithms for both packing and covering SDPs that achieve better utility than the state-of-the-art exponential-time algorithm of Song-Xue-Zhang (NeurIPS 2025), which is designed solely for covering SDPs. Our approach builds upon a variant of the dense Multiplicative Weights Update (MWU) framework, and leverages an oracle which computes approximate largest/smallest eigenvectors. The oracle is implemented via a differentially private power iteration, and may be of independent interest.