pith. sign in

arxiv: 2411.03087 · v1 · pith:3HE7HQV4new · submitted 2024-11-05 · 💻 cs.DS

On Differentially Private Linear Algebra

Haim Kaplan , Yishay Mansour , Shay Moran , Uri Stemmer , Nitzan Tur This is my paper
classification 💻 cs.DS
keywords linearalgorithmsefficientaddressingaffinedifferentiallyequalitiesinequalities
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Solving Positive Linear Programs with Differential Privacy

    cs.DS 2026-04 unverdicted novelty 6.0

    Differentially private solvers for positive LPs that approximate solutions with bounded constraint violations and improve on prior instance-dependent and new data-independent guarantees.

  2. Solving Positive Linear Programs with Differential Privacy

    cs.DS 2026-04 unverdicted novelty 6.0

    Differentially private solvers for positive packing, covering, and mixed LPs that improve instance-dependent guarantees and add new data-independent bounds depending only on dimension.