# On Differentially Private Linear Algebra

arXiv: https://arxiv.org/abs/2411.03087 · HTML: https://mlsanity.com/paper/2411.03087/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2024.

## Built on by (most cited first, 4 of 4)

- [Private Geometric Median in Nearly-Linear Time](https://mlsanity.com/paper/2505.20189/) (2025)
- [Fast-MWEM: Private Data Release in Sublinear Time](https://mlsanity.com/paper/2602.03732/) (2026)
- [Computationally Efficient Replicable Learning of Parities and Applications](https://mlsanity.com/paper/2602.09499/) (2026)
- [Private Component-by-Component Learning](https://mlsanity.com/paper/2610.05102/) (2026)

## Abstract (arXiv)

We introduce efficient differentially private (DP) algorithms for several linear algebraic tasks, including solving linear equalities over arbitrary fields, linear inequalities over the reals, and computing affine spans and convex hulls. As an application, we obtain efficient DP algorithms for learning halfspaces and affine subspaces. Our algorithms addressing equalities are strongly polynomial, whereas those addressing inequalities are weakly polynomial. Furthermore, this distinction is inevitable: no DP algorithm for linear programming can be strongly polynomial-time efficient.